不要用```cout```,慢的一批
by hl666 @ 2019-01-23 17:13:16
@[hl666](/space/show?uid=41698) emm真是抱歉习惯了就没改(不过改了也过不了诶)
by Cyan_rose @ 2019-01-23 17:16:58
@[Cyan_rose](/space/show?uid=48246) 那我也没办法了,平时都写```FHQ_Treap```(除了```LCT```好像就没怎么用过```splay```)
by hl666 @ 2019-01-23 17:18:29
~~虽然迟了快二十多天还是偷偷来说一声~~
看了下您的评测记录过了的那几个点的时间会TLE应该不是程序效率的问题qwq
也许是什么地方死循环了之类的qwq
或者您可以参考一下我的代码qwq(虽然写法有点小不同)
```cpp
#include <cstdio>
#include <algorithm>
using namespace std;
typedef struct node{
int v,siz,s[2],p;
}node;
node t[80010];
int n,m,root,tot=0,s,a[80010],pos[80010];
char opt[10];
inline int read(){
int num=0,k=1; char c=getchar();
while(c>'9' || c<'0') k=(c=='-')?0:k,c=getchar();
while(c>='0' && c<='9') num=num*10+c-'0',c=getchar();
return k?num:-num;
}
int check(int x) {return (t[t[x].p].s[0]==x)?0:1;}
void update(int x) {t[x].siz=t[t[x].s[0]].siz+t[t[x].s[1]].siz+1;}
void rotate(int x){
int y=t[x].p,z=t[y].p,k=check(x),w=t[x].s[k^1];
t[y].s[k]=w; if(w) t[w].p=y;
t[z].s[check(y)]=x; t[x].p=z;
t[x].s[k^1]=y; t[y].p=x;
update(y); update(x);
}
void splay(int x,int goal=0){
while(t[x].p!=goal){
int y=t[x].p,z=t[y].p;
if(z!=goal) rotate((check(y)==check(x))?y:x);
rotate(x);
}
if(!goal) root=x;
}
int build(int l,int r,int p){
if(l>r) return 0;
int cur=++tot,mid=(l+r)>>1;
t[cur].p=p; t[cur].v=a[mid]; t[cur].siz=1; pos[t[cur].v]=cur;
if(l!=r) {t[cur].s[0]=build(l,mid-1,cur); t[cur].s[1]=build(mid+1,r,cur);}
update(cur);
return cur;
}
int pre(){
int cur=t[root].s[0];
if(!cur) return 0;
while(t[cur].s[1]) cur=t[cur].s[1];
return cur;
}
int succ(){
int cur=t[root].s[1];
if(!cur) return 0;
while(t[cur].s[0]) cur=t[cur].s[0];
return cur;
}
void top(int s){
splay(pos[s]);
if(!t[root].s[0]) return;
else if(!t[root].s[1]) swap(t[root].s[0],t[root].s[1]);
else{
splay(succ(),root);
int cur=t[root].s[0];
t[t[root].s[1]].s[0]=cur; t[cur].p=t[root].s[1]; t[root].s[0]=0;
update(t[root].s[1]); update(root);
}
}
void bottom(int s){
splay(pos[s]);
if(!t[root].s[1]) return;
else if(!t[root].s[0]) swap(t[root].s[0],t[root].s[1]);
else{
splay(pre(),root);
int cur=t[root].s[1];
t[t[root].s[0]].s[1]=cur; t[cur].p=t[root].s[0]; t[root].s[1]=0;
update(t[root].s[0]); update(root);
}
}
void insert(int s,int w){
if(!w) return;
if(w==1){
splay(pos[s]);
int cur=succ();
swap(t[root].v,t[cur].v);
pos[t[root].v]=root; pos[t[cur].v]=cur;
}
else{
splay(pos[s]);
int cur=pre();
swap(t[root].v,t[cur].v);
pos[t[root].v]=root; pos[t[cur].v]=cur;
}
}
int ask(int s){
splay(pos[s]);
return t[t[root].s[0]].siz;
}
int query(int s){
int cur=root;
while(true){
if(t[t[cur].s[0]].siz+1==s) return t[cur].v;
if(t[t[cur].s[0]].siz>=s) cur=t[cur].s[0];
else s-=t[t[cur].s[0]].siz+1,cur=t[cur].s[1];
}
return 0;
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++) a[i]=read();
root=build(1,n,0);
while(m--){
scanf("%s",opt); int s=read(),w;
if(opt[0]=='T') top(s);
else if(opt[0]=='B') bottom(s);
else if(opt[0]=='I') {w=read(); insert(s,w);}
else if(opt[0]=='A') printf("%d\n",ask(s));
else printf("%d\n",query(s));
}
}
```
by kkxhh @ 2019-02-11 23:20:58
@[kkxhh](/space/show?uid=100037) 啊才看到真是抱歉!已经调试出来了,是在top和bottom的时候左右儿子没处理好崩了233~不过还是十分感谢!
by Cyan_rose @ 2019-03-01 20:40:06
@[Cyan_rose](/space/show?uid=48246) qwq
by kkxhh @ 2019-03-01 20:46:45