1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119
| #include <bits/stdc++.h> #define MAXN 500005 using namespace std; inline int read() { int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9') { x=(x*10)+(ch-'0'); ch=getchar(); } return x*f; } namespace FHQ_Treap{ struct node{ int l,r; int val; int pri; int sz; }tree[MAXN]; int tot; #define lc(i) tree[i].l #define rc(i) tree[i].r inline void Update(int x){ tree[x].sz=tree[lc(x)].sz+tree[rc(x)].sz+1; } inline int New(int v){ tree[++tot].val=v; tree[tot].pri=rand(); tree[tot].sz=1; return tot; } int Merge(int x,int y){ if (!x||!y) return x+y; if (tree[x].pri<tree[y].pri){ rc(x)=Merge(rc(x),y),Update(x); return x; } else { lc(y)=Merge(x,lc(y)),Update(y); return y; } } void Split(int i,int k,int &x,int &y){ if (!i){ x=y=0; } else { if (tree[i].val<=k){x=i,Split(rc(i),k,rc(i),y);} else{y=i,Split(lc(i),k,x,lc(i));} Update(i); } } int kth(int i,int k){ while (true){ if (k<=tree[lc(i)].sz){ i=lc(i); } else if (k==tree[lc(i)].sz+1){ return i; } else{ k-=tree[lc(i)].sz+1; i=rc(i); } } } int root,x,y,z; void Init(){ tot=0; root=0; srand(time(NULL)); } inline void Add(int num){ Split(root,num,x,y); root=Merge(Merge(x,New(num)),y); } inline void Del(int num){ Split(root,num,x,z); Split(x,num-1,x,y); y=Merge(lc(y),rc(y)); root=Merge(Merge(x,y),z); } inline int Rank(int num){ Split(root,num-1,x,y); int temp=tree[x].sz+1; root=Merge(x,y); return temp; } #define Get_K(rt,rk) tree[kth(rt,rk)].val inline int Kth(int k){ return Get_K(root,k); } inline int Pre(int num){ Split(root,num-1,x,y); int temp=Get_K(x,tree[x].sz); root=Merge(x,y); return temp; } inline int Nex(int num){ Split(root,num,x,y); int temp=Get_K(y,1); root=Merge(x,y); return temp; } }; using namespace FHQ_Treap; #define INF 0x3f3f3f3f int main(){ Init(); int n=read(); Add(INF),Add(-INF); }
|