【算法分析】
鉴于zyylhappy提到这题，大年初一的凌晨心血来潮爬起来，就把它做了。
网上大部分看到都是块状链表或者说beyondvoid大神的splay。
但是我不会splay，块状链表觉得太不和谐了，于是我果断就拿起了具有我们广东特色的数据结构——陈启峰树(SBT)。
虽然说着比较牵强。。。
然后这题嘛，我的思路就是把字符串拆成字符，按位置前后作为key值大小，插入我们可爱的平衡树之中。
虽然我的程序没有定义这个位置，但是这是可以体现出来的。
我们注意到旋转的性质，旋转以后，整体是排序二叉树这一性质不会被破坏（废话
）
所以我们可以无所顾忌的用SBT去弄到他平衡。
但是我刚写出来的时候一用cena测试。。。悲剧，栈溢出
。。。偶就是为了栈不溢出才学的C++，你现在告诉我你也溢出了
分析一下，我发现我写的时候是找到那个光标位置的下一个插入点的时候，一口气插完了整个字符串，
然后在递归回来修复，这样的话，栈就需要搞到一次插入的字符串长度的大小。而据我不完全统计，它一次插入的字符串有时候甚至长度超10^6（这不是猥琐是什么？）。
偶就改成一个一个字符地插入SBT之中。但是这样的话，插入一个字符串的代价变成O(LEN*lgSUM)。SUM是全部字符的个数。
于是，很果断地TLE，几乎全部跑了6S多。。。（在我这特别残破的机器上，估计是beyondvoid大牛2001买的电脑的1/3的运算速度。。。据beyondvoid大牛说我应该是运行环境有问题，而我悲剧地不会改）
额。然后我想放弃了，但是突然有想到直接插入那颗这么大的平衡树的话，那个lg会变得比较大，而我现在就是被常数卡住了。
于是我就是采取的这样的方法来解决insert操作：先建一颗SBT，然后在找到光标，把新建的SBT的树根拼在那上面。然后这样插入一个长度为LEN的字符串，复杂度会变成O(LEN*lgLEN)
于是高高兴兴地一测，全部4s多，然后我找到时间限制一看，2~4s。于是当场纠结在那。。。我想，如果是beyondvoid的电脑，我是能过的吧
不过我喜欢追求完美。。。所以想搞到在自己这台垃圾机器上也能AC，所以继续优化。
由于上一次注意到他一次插入的字符串长度可能超10^6，于是就觉得肯定是新建SBT的时候O(LEN*lgLEN)的复杂度还是不够快，毕竟他来多几次10^6的话，正常的SBT都要完蛋。。。
于是苦思冥想之后，发现一种新的构建方法——二分区间。
因为是字符串，而且是以先后顺序作为平衡二叉树的关键字，所以我建SBT的话，会每次都找到向右的最长链，然后插入的新的位置当中。如果是有这个单调性的话，那么就可以考虑二分了。
二分构建的话，这棵树会直接达到最平衡，然后插入的复杂度就是O(LEN)！
扯远了。。。先来说说怎么二分。
就是每次把字符串中间的那个字符抽出来放中间，然后左边的放左边去，右边的右边去。
就像这样：
void build(int &p,int l,int r){
if (l>r) return;
int mid=(l+r)/2;
tot++;
p=tot;
tr[p].l=0;
tr[p].r=0;
tr[p].key=str[mid];
build(tr[p].l,l,mid-1);
build(tr[p].r,mid+1,r);
tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
}
这样构建以后，一个完全平衡的二叉树插入到SBT某个关键位置的话，旋转次数大大减少。
一测，果然AC!
【其它】经测试，beyondvoid的splay在我这台机器上用了6.22s通过所有的测试数据，我的总共用了5.00s
而我这个长度也算比较短。。。160行，beyondvoid的splay上220行吧。。。块状链表不知。
【CODE】
#include
struct {int l,r,s;char key;}tr[N];
char op[20],str[N];
int tot,root,gb,len,done,nowi,troot;
inline void left(int &k){
int p=tr[k].r;
tr[k].r=tr[p].l;
tr[p].l=k;
tr[k].s=tr[tr[k].l].s+tr[tr[k].r].s+1;
tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
k=p;
}
inline void right(int &k){
int p=tr[k].l;
tr[k].l=tr[p].r;
tr[p].r=k;
tr[k].s=tr[tr[k].l].s+tr[tr[k].r].s+1;
tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
k=p;
}
inline void repair(int &k){
bool flag=false;
if (tr[tr[tr[k].l].l].s>tr[tr[k].r].s){
right(k);
flag=true;
}else
if (tr[tr[tr[k].l].r].s>tr[tr[k].r].s){
left(tr[k].l);
right(k);
flag=true;
}else
if (tr[tr[tr[k].r].r].s>tr[tr[k].l].s){
left(k);
flag=true;
}else
if (tr[tr[tr[k].r].l].s>tr[tr[k].l].s){
right(tr[k].r);
left(k);
flag=true;
}
if (flag){
repair(tr[k].l);
repair(tr[k].r);
repair(k);
}
}
inline void ins(int &p){
if (p==0) p=troot;
else
if (tr[tr[p].l].s+done+1>gb) ins(tr[p].l);
else{
done+=tr[tr[p].l].s+1;
ins(tr[p].r);
}
tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
repair(p);
}
inline char findr(int &p){
tr[p].s–;
if (tr[p].r==0){
char tmp=tr[p].key;
p=tr[p].l;
return tmp;
}
else return findr(tr[p].r);
}
inline void del(int &p){
if (p==0 || done>gb+len || done+tr[p].s<=gb) return;
bool flag=false;
int td=done+tr[tr[p].l].s+1;
if (td>gb && td<=gb+len) flag=true;
if (td-1>gb) del(tr[p].l);
done=td;
del(tr[p].r);
if (flag)
if (!tr[p].l || !tr[p].r) p=tr[p].l+tr[p].r;
else tr[p].key=findr(tr[p].l);
if (p!=0) tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
}
inline void solve(int p){
if (p==0 || done>gb+len) return;
bool flag=false; int td=done;
if (tr[tr[p].l].s+done+1>gb && tr[tr[p].l].s+done+1<=gb+len) flag=true;
if (tr[tr[p].l].s+done>gb) solve(tr[p].l);
if (flag) printf("%c",tr[p].key);
done=td+tr[tr[p].l].s+1;
solve(tr[p].r);
}
inline void Move(){scanf("%d",&gb);}
inline void Next(){if (gb
inline void build(int &p,int l,int r){
if (l>r) return;
int mid=(l+r)/2;
tot++;
p=tot;
tr[p].l=0;
tr[p].r=0;
tr[p].key=str[mid];
build(tr[p].l,l,mid-1);
build(tr[p].r,mid+1,r);
tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
}
inline void Ins(){
scanf("%d",&len);
char ch;
for (int i=0;i
while (ch==’n’) ch=getchar();
str[i]=ch;
}
troot=0;
build(troot,0,len-1);
done=0;
ins(root);
}
inline void Del(){
scanf("%d",&len);
done=0;
del(root);
}
inline void Get(){
scanf("%d",&len);
done=0;
solve(root);
printf("n");
}
int main(){
freopen("editor.in","r",stdin);
freopen("editor.out","w",stdout);
int tmp;
scanf("%d",&tmp);
for (int i=1;i<=tmp;i++){
scanf("%s",&op);
switch (op[0]){
case ‘M’:Move(); break;
case ‘I’:Ins(); break;
case ‘D’:Del(); break;
case ‘N’:Next(); break;
case ‘P’:Prev(); break;
case ‘G’:Get(); break;
}
}
}