工信部门备案网站获取的icp备案号/淘宝关键词

例：UVA - 12538 Version Controlled IDE
1、利用可持久化无旋Treap
有旋treap是不能维护给定序列的，但是无旋treap可以，但是对于可持续化，会消耗很大的空间
无旋treap在维护给定顺序的序列中，其序列下标满足BST，如果不是维护给定顺序的序列，那么其节点值满足BST
这个题是要求维护给定顺序的，剩下一种传送门
指针版本的，是我阅读能力太差了，看不懂，巨犇的代码技巧看不懂，最后选择了使用数组版本

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>using namespace std;const int maxn = 50010;char s[maxn * 100];struct tree
{int lch,rch,pri,sze;char val;
}node[maxn * 100];//因为是可持久化数据，所以数组要开大int cnt,root[maxn],d,now,a,b,c;
//a/b/c 记录分裂后子树的根节点
//d:记录已经输出的c的个数
//now : 目前版本//每次分裂或者合并就要更新当前根节点下树的大小
void update(int rt)
{node[rt].sze = 1;if(node[rt].lch){node[rt].sze += node[node[rt].lch].sze;}if(node[rt].rch){node[rt].sze += node[node[rt].rch].sze;}
}int newnode(char w = 0)
{cnt++;node[cnt].val = w;node[cnt].lch = node[cnt].rch = 0;node[cnt].pri = rand();node[cnt].sze = 1;return cnt;
}//合并操作，模板
//这里默认x树节点的值的序号全部小于y树节点的值的序号
int merge(int x,int y)
{if(!x||!y){return x + y;}int rt = newnode();if(node[x].pri < node[y].pri){node[rt] = node[x];node[rt].rch = merge(node[rt].rch,y);}else{node[rt] = node[y];node[rt].lch = merge(x,node[rt].lch);}update(rt);return rt;
}//分裂操作，模板
//分裂成x的树中所有节点的序号都小于y树中所有节点的序号值
void split(int rt,int k,int &x,int &y)
{if(!rt){x = y = 0;}else{if(k <= node[node[rt].lch].sze){y = newnode();node[y] = node[rt];split(node[y].lch,k,x,node[y].lch);update(y);}else{x = newnode();node[x] = node[rt];split(node[x].rch,k - node[node[rt].lch].sze - 1,node[x].rch,y);update(x);}}
}//建树操作
void build(int l,int r,int &rt)
{if(l > r){return ;}int m = (l + r)>>1;rt = newnode(s[m]);build(l,m - 1,node[rt].lch);build(m + 1,r,node[rt].rch);update(rt);
}//插入操作
void ins(int &rt,int last,int pos)
{// rt : 更新的版本根节点// last : 旧版本的根节点// pos : 要插入的位置a = b = c = 0;scanf("%s",s + 1);int len = strlen(s + 1);split(last,pos,a,c);build(1,len,b);//将插入完的树重新合并rt = merge(merge(a,b),c);
}//删除操作
void del(int &rt,int last,int pos,int len)
{// rt : 更新的版本根节点// last : 旧版本的根节点// pos : 要删除的位置// len : 要删除的长度a = b = c = 0;split(last,pos - 1,a,b);split(b,len,b,c);// 分成三组，然后把前后两组合并（中间的是被删除的rt = merge(a,c);
}//前序遍历二叉树
void print(int rt)
{if(!rt){return ;}print(node[rt].lch);printf("%c",node[rt].val);if(node[rt].val == 'c'){d++;//统计输出的c的数量}print(node[rt].rch);
}void print(int rt,int pos,int len)
{// rt : 更新的版本根节点// pos : 要输出的起始位置// len : 要输出的长度a = b = c = 0;split(rt,pos - 1,a,b);split(b,len,b,c);//分离出我们想要的子树;print(b);printf("\n");
}int main()
{int n;scanf("%d",&n);while(n--){a = b = c = 0;int oper;scanf("%d",&oper);if(oper == 1){int p;scanf("%d",&p);p -= d;ins(root[now + 1],root[now],p);//更新一次，版本数+1;now++;}if(oper == 2){int p,l;scanf("%d%d",&p,&l);p -= d,l -= d;del(root[now + 1],root[now],p,l);//更新一次，版本数+1;now++;}if(oper == 3){int ver,p,l;scanf("%d%d%d",&ver,&p,&l);ver -= d,p -= d,l -= d;print(root[ver],p,l);}}return 0;
}

2、利用c++的stl容器crope，内部是用平衡树实现的，操作都是O（logN）
这里直接转了别人的代码
代码出处传送门

#include<iostream>
#include<cstdio>
#include<ext/rope>
#include<string>using namespace std;
using namespace __gnu_cxx;const int maxn=50005;crope ro,l[maxn],tmp;char str[205];int main()
{int n,op,p,cnt,c,d,v;d=0;cnt=1;scanf("%d",&n);while(n--){scanf("%d",&op);if(op==1){scanf("%d%s",&p,str);p-=d;ro.insert(p,str);l[cnt++]=ro;}else if(op==2){scanf("%d%d",&p,&c);p-=d;c-=d;ro.erase(p-1,c);l[cnt++]=ro;}else{scanf("%d%d%d",&v,&p,&c);v-=d;p-=d;c-=d;tmp=l[v].substr(p-1,c);d+=count(tmp.begin(),tmp.end(),'c');cout<<tmp<<endl;}}return 0;
}
/*
6
1 0 abcdefgh
2 4 3
3 1 2 5
3 3 3 4
1 4 xy
3 5 4 6
*/