RT,#5~#10出现奇异MLE,TLE和WA,求调
/*
* @ Author: Xiaohuba
* @ Usage: OI Problem
* @ Language: C++
*/
#include<bits/stdc++.h>
using namespace std;
/* ---File Head Begin--- */
namespace Xiaohuba_File_Head
{
//def
#define ll long long
#define lll __int128
#define pii pair<int,int>
#define mkp make_pair
#define vi vector<int>
#define vs vector<string>
#define viit vector<int>::iterator
#define pb push_back
#define il inline
#define pch putchar
#define gch getchar
#define Endl putchar('\n')
#define Space putchar(' ')
#define For(x,st,ed) for(register int x=(st),END=(ed);x<=END;++x)
#define ForDown(x,st,ed) for(register int x=(st),END=(ed);x>=END;--x)
#define sq(x) (x*x)
#define Set(a,b) memset(a,b,sizeof(a))
#define Cpy(a,b) memcpy(a,b,sizeof(a))
#define PRIME_MOD 100000007ll
#ifdef ONLINE_JUDGE
#define log2 __lg
#define gcd __gcd
#endif
//io
template <typename T>
il void read(T & tmp){ tmp=0;char c=getchar();bool flg=0;while(!isdigit(c)) flg=c=='-',c=getchar();while(isdigit(c)) tmp=(tmp<<3)+(tmp<<1)+c-'0',c=getchar();if(flg) tmp*=-1; }
template <typename T, typename... Args>
il void read(T &tmp, Args &...tmps){ read(tmp);read(tmps...); }
template <typename T>
il void __write(const T &x){ if(x==0) return;__write(x/10);putchar(x%10+'0'); }
template <typename T>
il void write(const T &x){ if(x==0) putchar('0');if(x<0) putchar('-');__write((x<0 ? -x : x)); }
template <typename T>
il void write_with_space(const T &x){ write(x);Space; }
template <typename T>
il void write_with_endl(const T &x){ write(x);Endl; }
template <typename T, typename... Args>
il void write_with_space(const T &x, const Args &...y){ write_with_space(x);write_with_space(y...); }
il void __getline(istream & istr, string & str){ getline(istr,str);if(*(str.end()-1)=='\r') str.erase(str.end()-1); }
#define getline __getline
};
using namespace Xiaohuba_File_Head;
/* ---File Head End--- */
class FHQ_Treap
{
public:
struct Node
{
int lc,rc,v,w,size;
};
Node tr[10001];int cnt,root;
il int New(int x)
{
tr[++cnt]=(Node){0,0,x,rand(),1};
return cnt;
}
il void pushUp(int id)
{
tr[id].size=tr[tr[id].lc].size+tr[tr[id].rc].size+1;
}
il void split(int v, int &x, int &y, int id)
{
if(!id)
{
x=y=0;
return;
}
if(tr[id].v<=v)
{
x=id;
split(v,tr[id].rc,y,tr[id].rc);
} else {
y=id;
split(v,x,tr[id].lc,tr[id].lc);
}
pushUp(id);
}
il int merge(int x, int y)
{
if(!x || !y) return x+y;
if(tr[x].w > tr[y].w)
{
tr[x].rc=merge(tr[x].rc,y);
pushUp(x);
return x;
} else {
tr[y].lc=merge(x,tr[y].lc);
pushUp(y);
return y;
}
}
il void insert(int v)
{
int x,y;
split(v,x,y,root);
root=merge(merge(x,New(v)),y);
}
il void erase(int v)
{
int x,y,z;
split(v,x,y,root);
split(v-1,x,z,x);
z=merge(tr[z].lc,tr[z].rc);
root=merge(merge(x,z),y);
}
il int rank(int v)
{
int x,y;
split(v-1,x,y,root);
int res=tr[x].size+1;
root=merge(x,y);
return res;
}
il int kth(int k)
{
int u=root;
while(u)
{
if(tr[tr[u].lc].size+1==k) break;
if(tr[tr[u].lc].size+1>k) u=tr[u].lc;
else
{
k-=tr[tr[u].lc].size+1;
u=tr[u].rc;
}
}
return tr[u].v;
}
il int pre(int v)
{
int x,y;
split(v-1,x,y,root);
int u=x;
while(tr[u].rc) u=tr[u].rc;
root=merge(x,y);
return tr[u].v;
}
il int nxt(int v)
{
int x,y;
split(v,x,y,root);
int u=y;
while(tr[u].lc) u=tr[u].lc;
root=merge(x,y);
return tr[u].v;
}
};
FHQ_Treap bt;
int T;
signed main()
{
srand(666);
read(T);
while(T--)
{
int op,x;
read(op,x);
switch(op)
{
case 1:
bt.insert(x);
break;
case 2:
bt.erase(x);
break;
case 3:
write_with_endl(bt.rank(x));
break;
case 4:
write_with_endl(bt.kth(x));
break;
case 5:
write_with_endl(bt.pre(x));
break;
case 6:
write_with_endl(bt.nxt(x));
}
}
return 0;
}