差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:王智彪:后缀平衡树 [2021/07/15 17:40]
王智彪创建
+++ 2020-2021:teams:legal_string:王智彪:后缀平衡树 [2021/07/16 13:38] (当前版本)
王智彪
@@ 行 164: / 行 164: @@
 ===== 代码练习 =====
+.[[https://www.luogu.com.cn/problem/P5353]]
+给定一个以 $n$ 个节点的树，保证对于 $2$ 到 $n$ 的每个节点，其父亲的编号均小于自己的编号。
+每个节点上有一个字符，一个点代表的字符串是从这个点到根的简单路径上经过的所有的字符连起来组成的字符串。
+需要我们将这些字符串按照字典序排序，对于一样的字符串，优先比较他们父亲代表的字符串的大小，还是一样就按照他们的编号大小进行排序。
+输入包含节点数 $n$ ，以及从 $2$ 到 $n$ 每个结点的父亲编号，最后输入一个字符串，第 $i$ 个字符代表 编号为 $i$节点上的字符。
+输出：按照字符串排名从小到大输出节点编号
+注意到我们只是说后缀平衡树可以满足字符的插入和删除，但是并不是只能解决一个字符串从后向前的插入问题，对于这种树上排序，后缀平衡树大有用武之地。
+注意到因为父亲编号必小于自己的编号，我们这次需要正向插入，因为儿子节点是一个字符串的首字符相当于刚才讲的插入操作的不会改变已有排序顺序的字符，所以要正向插入。我们还需要改变比较规则，首字母一样时比较父亲的 $val$ 值，再一样返回下标的比较结果。
+<hidden 代码>
+<code cpp>
+inline int comp(int x,int y) {
+	if(s[x]>s[y]||s[x]==s[y]&&trp[fa[x]].val>trp[fa[y]].val) return 1;
+	else if(s[x]==s[y]&&trp[fa[x]].val==trp[fa[x]].val&&x>y) return 1;
+	//else if(s[x]==s[y]&&trp[fa[x]].val==trp[fa[x]].val&&x==y) return 0;
+	else return -1;
+}
+int main() {
+	scanf("%d",&n);
+	for(int i=2; i<=n; i++) scanf("%d",&fa[i]);
+	scanf("%s",s+1);
+	for(int i=1; i<=n; i++) ins(root,i,1,INF);
+	dfs(root);
+	for(int i=1; i<=n; i++) printf("%d ",sa[i]);
+	return 0;
+}
+</code>
+</hidden>
+.[[https://www.luogu.com.cn/problem/P5212]]
+给定一个字符串 $init$ ，要求支持两个操作（强制在线）：
+.在字符串的后面插入一个字符串 操作符号为 $ADD$
+.询问字符串 $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>

CVBB ACM Team

用户工具

站点工具

差别

页面工具