```cpp
#include<bits/stdc++.h>
#define int long long
#define mem(x) memset(x,0,sizeof(x))
using namespace std;
int read(){
int s = 0,w = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();}
while(ch >= '0' && ch <= '9')s = s * 10 + ch - '0',ch = getchar();
return s * w;
}
mt19937 rnd(time(0));
struct node{
int l;
int r;
int w;
int key;
int siz;
int fa;
bool flag;
}e[100010];
int cnt,rt;
int q[100010];
int newnode(int w){
cnt ++;
e[cnt].w = w;
e[cnt].key = rnd();
e[cnt].siz = 1;
q[w] = cnt;
return cnt;
}
void update(int i){
e[i].siz = e[e[i].l].siz + e[e[i].r].siz + 1;
e[e[i].l].fa = i;
e[e[i].r].fa = i;
}
void split(int i,int siz,int &x,int &y){
if(!i){
x = y = 0;
return ;
}
if(e[e[i].l].siz < siz){
x = i;
split(e[i].r,siz - e[e[i].l].siz - 1,e[i].r,y);
}
else {
y = i;
split(e[i].l,siz,x,e[i].l);
}
update(i);
}
int merge(int x,int y){
if(!x || !y)return x + y;
if(e[x].key < e[y].key){
e[x].r = merge(e[x].r,y);
update(x);
return x;
}
else {
e[y].l = merge(x,e[y].l);
update(y);
return y;
}
}
void ins(int w){
int x,y;
newnode(w);
rt = merge(rt,q[w]);
}
void del(int id){
int x,y,z;
split(rt,id,x,z);
split(x,id - 1,x,y);
y = merge(e[y].l,e[y].r);
rt = merge(x,merge(y,z));
}
int getrank(int rk){
int s = e[e[rk].l].siz + 1;
while(e[rk].fa){
if(rk == e[e[rk].fa].r)s += e[e[e[rk].fa].l].siz + 1;
rk = e[rk].fa;
}
return s;
}
int getnum(int rk){
int x,y,z;
split(rt,rk,x,z);
split(x,rk - 1,x,y);
int ans = e[y].w;
rt = merge(x,merge(y,z));
return ans;
}
int n,m;
signed main(){
cin>>n>>m;
for(int i = 1;i <= n;i ++){
int x;
x = read();
ins(x);
}
while(m --){
string s;
int x,y;
cin>>s;
if(s == "Top"){
x = read();
int xx = getrank(q[x]);
int l,r,w;
split(rt,xx - 1,l,r);
split(r,1,r,w);
rt = merge(merge(r,l),w);
}
if(s == "Bottom"){
x = read();
int xx = getrank(q[x]);
int l,r,w;
split(rt,xx - 1,l,r);
split(r,1,r,w);
rt = merge(merge(l,w),r);
}
if(s == "Insert"){
x = read(),y = read();
int xx = getrank(q[x]);
if(y == 0)continue;
int qwq,qaq,qvq,awa,qwqwq,qaqaq;
split(rt,xx - 1,qwq,qaq);
split(qaq,1,qvq,awa);
if(y > 0){
split(awa,xx - 2,qwqwq,qaqaq);
rt = merge(merge(merge(qwqwq,qwq),qaqaq),qaq);
}
else {
split(awa,1,qwqwq,qaqaq);
rt = merge(merge(merge(qwq,qwqwq),qvq),qaqaq);
}
}
if(s == "Ask"){
x = read();
printf("%lld\n",getrank(q[x]) - 1);
}
if(s == "Query"){
x = read();
printf("%lld\n",getnum(x));
}
}
}
```
by EDqwq @ 2021-05-08 02:05:46
死循环然后空间爆了?
by 滑蒻稽 @ 2021-05-08 08:02:57
@[EDqwq](/user/294562) 我输出了一下中序遍历,你 `insert x -1` 的情况写错了:
![](https://gitee.com/huaruoji/images/raw/master/img/20210511155338.png)
而且 `t` 有可能是等于 0 的。
by 滑蒻稽 @ 2021-05-11 15:54:17
@[滑蒻稽](/user/113181) 感谢您3天之后仍在看我的代码
但是我已经通过了,错误确实是insert
by EDqwq @ 2021-05-11 16:11:03