2020-2021:teams:legal_string:王智彪:后缀平衡树
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:王智彪:后缀平衡树 [2021/07/15 17:59] 王智彪 |
2020-2021:teams:legal_string:王智彪:后缀平衡树 [2021/07/16 13:38] (当前版本) 王智彪 |
||
|---|---|---|---|
| 行 179: | 行 179: | ||
| 注意到因为父亲编号必小于自己的编号，我们这次需要正向插入，因为儿子节点是一个字符串的首字符相当于刚才讲的插入操作的不会改变已有排序顺序的字符，所以要正向插入。我们还需要改变比较规则，首字母一样时比较父亲的 $val$ 值，再一样返回下标的比较结果。 | 注意到因为父亲编号必小于自己的编号，我们这次需要正向插入，因为儿子节点是一个字符串的首字符相当于刚才讲的插入操作的不会改变已有排序顺序的字符，所以要正向插入。我们还需要改变比较规则，首字母一样时比较父亲的 $val$ 值，再一样返回下标的比较结果。 | ||
| + | |||
| + | <hidden 代码> | ||
| <code cpp> | <code cpp> | ||
| 行 201: | 行 203: | ||
| </code> | </code> | ||
| + | </hidden> | ||
| + | |||
| + | 2.[[https://www.luogu.com.cn/problem/P5212]] | ||
| + | |||
| + | 给定一个字符串 $init$ ，要求支持两个操作（强制在线）： | ||
| + | |||
| + | 1.在字符串的后面插入一个字符串 操作符号为 $ADD$ | ||
| + | |||
| + | 2.询问字符串 $s$ 在当前字符串中作为连续子串出现了几次 操作符号为 $QUERY$ | ||
| + | |||
| + | 每个给定的字符串要进行解码操作，维护一个变量 $mask$ ，初始值为 $0$ 。给了一个解码函数，解码之后的字符串才是真的字符串。 $mask$ 要和每次查询的值进行异或之后才是新的 $mask$ 值。 | ||
| + | |||
| + | 数据范围： $|init|≤6×10^{5},Q≤6×10^{5}$， 询问总长度 $≤3×10^{6}$ 。保证字符串中只出现 $A$ 和 $B$ 。个别测试点给 $3s$ 。 | ||
| + | |||
| + | 插入字符的操作显然属于后缀平衡树的范畴，复杂度 $O(3·10^{6}logn)$ 。 | ||
| + | |||
| + | 对于询问一个字符串在另一个字符串出现了多少次的问题，我们可以将其转化成这个字符串在大字符串中是多少个字符串的前缀的后缀/后缀的前缀。因为字符集是 $A$ 和 $B$ ，我们将原来的字符串末尾加个 $C$ 。再在这颗平衡树中求一个排名，将倒数第二位减一，再求一个排名，二者之差就是这个字符串出现了多少次，但是注意：这颗平衡树相当于倒过来的字符串，于是我们要把输入的串倒过来，再在后面补，比较的时候再倒过来就好了。比较的时候暴力就可以了，复杂度也是 $O(3·10^{6}logn)$ ，可以通过本题。 | ||
| + | |||
| + | <hidden 代码> | ||
| + | |||
| + | <code cpp> | ||
| + | |||
| + | inline int comp(int x,int y) { | ||
| + | if(s[x]>s[y]||s[x]==s[y]&&trp[x-1].val>trp[y-1].val) return 1; | ||
| + | else if(s[x]==s[y]&&trp[x-1].val==trp[y-1].val) return 0; | ||
| + | else return -1; | ||
| + | } | ||
| + | |||
| + | |||
| + | |||
| + | bool check(int pos) { | ||
| + | for(int i=1,j=pos;tmps[i];i++,j--) { | ||
| + | if(tmps[i]<s[j]) return true; | ||
| + | else if(tmps[i]>s[j]) return false; | ||
| + | } | ||
| + | } | ||
| + | |||
| + | int get_rnk(int pos) { | ||
| + | if(!pos) return 1; | ||
| + | else if(check(pos)) return get_rnk(trp[pos].lson); | ||
| + | return get_rnk(trp[pos].rson)+trp[trp[pos].lson].size+trp[pos].cnt; | ||
| + | } | ||
| + | |||
| + | |||
| + | |||
| + | int main() { | ||
| + | scanf("%d",&n); | ||
| + | scanf("%s",s+1); | ||
| + | int len=strlen(s+1); | ||
| + | for(int i=1; i<=len; i++) ins(root,i,1,INF); | ||
| + | for(int i=1; i<=n; i++) { | ||
| + | scanf("%s",opt+1); | ||
| + | if(opt[1]=='A') { | ||
| + | scanf("%s",tmps+1); | ||
| + | int L=strlen(tmps+1); | ||
| + | int tmplen=len; | ||
| + | len+=L; | ||
| + | decodeWithMask(tmps+1,mask,L); | ||
| + | for(int j=tmplen+1; j<=len; j++) { | ||
| + | s[j]=tmps[j-tmplen]; | ||
| + | ins(root,j,1,INF); | ||
| + | } | ||
| + | } else { | ||
| + | scanf("%s",tmps+1); | ||
| + | int L=strlen(tmps+1); | ||
| + | decodeWithMask(tmps+1,mask,L); | ||
| + | for(int j=1; j<=L/2; j++) { | ||
| + | char tmpc = tmps[j]; | ||
| + | tmps[j] = tmps[L-j+1]; | ||
| + | tmps[L-j+1] = tmpc; | ||
| + | } | ||
| + | tmps[L+2]='\0'; | ||
| + | tmps[L+1]='C'; | ||
| + | int pos = get_rnk(root); | ||
| + | tmps[L]--; | ||
| + | int pos1 = get_rnk(root); | ||
| + | int result = pos-pos1; | ||
| + | printf("%d\n",result); | ||
| + | mask=mask^result; | ||
| + | } | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | |||
| + | </code> | ||
| + | |||
| + | </hidden> | ||
2020-2021/teams/legal_string/王智彪/后缀平衡树.1626343185.txt.gz · 最后更改: 2021/07/15 17:59 由 王智彪
