题目名称 2623. [HZOI 2016][GDOI2016模拟3.14] hashit
输入输出 hahaha.in/out
难度等级 ★★★
时间限制 1000 ms (1 s)
内存限制 128 MB
测试数据 10 简单对比
题目来源 2017-03-02
开放分组 全部用户
提交状态
分类标签
后缀数组 平衡树
通过:7, 提交:35, 通过率:20%
Gravatarliumy 100 0.086 s C++
Gravatar_Itachi 100 0.270 s C++
Gravatar6666 100 0.365 s C++
Gravatar6666 100 0.369 s C++
Gravatar6666 100 0.374 s C++
Gravatar半汪 100 0.376 s C++
Gravatar半汪 100 0.412 s C++
Gravatar6666 100 0.415 s C++
Gravatar小一米 100 0.425 s C++
GravatarLucida 100 0.507 s C++
关于 hashit 的讨论
hash it?
has hit?
ha shit?
Gravatarsplay
2017-03-02 18:56 1楼
写一颗勤勉删除+旋转的替罪羊是很痛苦的。。
Gravatar_Itachi
2017-03-07 21:37 2楼
Gravatar半汪
2017-03-03 16:25 3楼
回复 @_Itachi :
学Treap
Gravatar半汪
2017-03-07 21:42 4楼
回复 @半汪 :
我能说我替罪羊树是现学的,在做这道题之前只A过两遍普通平衡树,而且都是惰性删除的,强行YY勤勉删除再写出来真心很累啊!
Gravatar_Itachi
2017-03-08 07:17 5楼
回复 @_Itachi :
谁告诉你替罪羊树能旋转了……
我怀疑你的删除复杂度是错的
GravatarAntiLeaf
2017-03-08 07:38 6楼
回复 @AntiLeaf :
啊哦!好像假如你能够造出每次都让我删除根节点的数据,我的复杂度就渣了。。不过你事先不知道我的alpha是多少,除非捆绑评测然后每个点中加几个卡不同的alpha值的替罪羊的数据,否则也是卡不动的。
Gravatar_Itachi
2017-03-08 08:00 7楼
GravatarAntiLeaf
2017-03-08 14:28 8楼
set的比较真多!这让hash很尴尬啊
GravatarFoolMike
2017-03-10 14:46 9楼
回复 @FoolMike :
Mike就是强啊
Gravatar半汪
2017-03-10 14:49 10楼

2623. [HZOI 2016][GDOI2016模拟3.14] hashit

★★★   输入文件:hahaha.in   输出文件:hahaha.out   简单对比
时间限制:1 s   内存限制:128 MB

【题目描述】

你有一个字符串S,一开始为空串,要求支持两种操作

1.在S后面加入字母c

2.删除S最后一个字母

现在有Q个操作,问每次操作后S有多少个不同的子串

Q<=1e5

【输入格式】

第一行输入一个M,表示操作个数

第二行给出一个长度为M的字符串,每个字符代表一次操作,如果为小写字母则表示在S后面插入该字母,如果是‘-’表示删除最后一个字母

【输出格式】

输出N个数,第i行表示第i次操作之后S有多少个不同的子串

【样例输入】

10
m-nk--z-p-

【样例输出】

1
0
1
3
1
0
1
0
1
0

【来源】

【GDOI 2016 模拟3.14】