P3369
Splay 我的版本一开始是必须要Insert 一个最小值 和一个最大值的 不然前驱后继 k大值会出锅
/*if you can't see the repayWhy not just work step by steprubbish is relaxedto ljq*/#include <cstdio>#include <cstring>#include <iostream>#include <queue>#include <cmath>#include <map>#include <stack>#include <set>#include <sstream>#include <vector>#include <stdlib.h>#include <algorithm>using namespace std;#define dbg(x) cout<<#x<<" = "<< (x)<< endl#define dbg2(x1,x2) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<endl#define dbg3(x1,x2,x3) cout<<#x1<<" = "<<x1<<" "<<#x2<<" = "<<x2<<" "<<#x3<<" = "<<x3<<endl#define max3(a,b,c) max(a,max(b,c))#define min3(a,b,c) min(a,min(b,c))typedef pair<int,int> pll;typedef long long ll;const int inf = 0x3f3f3f3f;const int _inf = 0xc0c0c0c0;const ll INF = 0x3f3f3f3f3f3f3f3f;const ll _INF = 0xc0c0c0c0c0c0c0c0;const ll mod = (int)1e9+7;ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}ll ksm(ll a,ll b,ll mod){int ans=1;while(b){if(b&1) ans=(ans*a)%mod;a=(a*a)%mod;b>>=1;}return ans;}ll inv2(ll a,ll mod){return ksm(a,mod-2,mod);}void exgcd(ll a,ll b,ll &x,ll &y,ll &d){if(!b) {d = a;x = 1;y=0;}else{exgcd(b,a%b,y,x,d);y-=x*(a/b);}}//printf("%lld*a + %lld*b = %lld\n", x, y, d);/*namespace sgt{#define mid ((l+r)>>1)#undef mid}*/const int MAX_N = 100025;int ch[MAX_N][2],fa[MAX_N],cnt[MAX_N],sz[MAX_N],val[MAX_N],rev[MAX_N],root,ncnt;int chk(int x){return ch[fa[x]][1] == x;}void pushup(int x){sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x];}void Rotate(int x){int y = fa[x],z = fa[y],k = chk(x), w = ch[x][k^1];ch[y][k] = w;fa[w] = y;ch[z][chk(y)] = x;fa[x] = z;ch[x][k^1] = y;fa[y] = x;pushup(y);pushup(x);}void Splay(int x,int goal = 0){while(fa[x]!=goal){int y = fa[x],z = fa[y];if(z!=goal){if(chk(x)==chk(y)) Rotate(y);else Rotate(x);}Rotate(x);}if(!goal) root = x;}//辅助操作，将最大的小于等于 x 的数所在的节点splay到根。void Find(int x){if(!root) return;int cur = root;while(ch[cur][x>val[cur]]&&x!=val[cur]){cur = ch[cur][x>val[cur]];}Splay(cur);}void Insert(int x){int cur = root,p = 0;while(cur&&val[cur]!=x){p = cur;cur = ch[cur][x>val[cur]];}if(cur){cnt[cur]++;}else{cur = ++ncnt;if(p) ch[p][x>val[p]] = cur;ch[cur][0] = ch[cur][1] = 0;val[cur] = x;fa[cur] = p;cnt[cur] = sz[cur] = 1;}Splay(cur);}void pushdown(int x){if(rev[x]){swap(ch[x][0],ch[x][1]);rev[ch[x][0]] ^= 1;rev[ch[x][1]] ^= 1;rev[x] = 0;}}int Kth(int k){int cur = root;while(1){pushdown(cur);if(ch[cur][0]&&k<=sz[ch[cur][0]]){cur = ch[cur][0];}else if(k>sz[ch[cur][0]]+cnt[cur]){k -= sz[ch[cur][0]] + cnt[cur];cur = ch[cur][1];}else return cur;}}void Reverse(int l,int r){int x = Kth(l), y = Kth(r+2);Splay(x);Splay(y,x);rev[ch[y][0]] ^= 1;}int pre(int x){Find(x);if(val[root]<x) return root;int cur = ch[root][0];while(ch[cur][1]){cur = ch[cur][1];}return cur;}int suc(int x){Find(x);if(val[root]>x) return root;int cur = ch[root][1];while(ch[cur][0]){cur = ch[cur][0];}return cur;}void Remove(int x){int last = pre(x),next = suc(x);Splay(last);Splay(next,last);int del = ch[next][0];if(cnt[del]>1){cnt[del]--;Splay(del);}else ch[next][0] = 0;}int main(){//ios::sync_with_stdio(false);//freopen("a.txt","r",stdin);//freopen("b.txt","w",stdout);Insert(_inf);Insert(inf);int n,opt,x;scanf("%d",&n);while(n--){scanf("%d%d",&opt,&x);if(opt==1){Insert(x);}else if(opt==2){Remove(x);}else if(opt==3){Find(x);printf("%d\n",sz[ch[root][0]]);}else if(opt==4){printf("%d\n",val[Kth(x+1)]);}else if(opt==5){printf("%d\n",val[pre(x)]);}else{printf("%d\n",val[suc(x)]);}}//fclose(stdin);//fclose(stdout);//cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;return 0;}
