Editorial for Order statistic set
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
#include<iostream> #include<algorithm> #define maxn 200020 #define fr(a,b,c) for (a=b;a<=c;a++) using namespace std; struct rec { int v,p,q; }; int n,m,a[maxn],b[maxn],e[maxn],g[maxn*5],h[maxn*5]; rec c[maxn]; char ch; void put(int nd,int l,int r,int x,int y,int v) { if (l==x && r==y) g[nd]+=v; else { int mid=(l+r)/2; if (x<=mid) put(nd*2,l,mid,x,min(y,mid),v); if (y>mid) put(nd*2+1,mid+1,r,max(x,mid+1),y,v); } h[nd]=g[nd]; if (r>l) h[nd]+=h[nd*2+1]; } int get(int nd,int l,int r,int k) { if (l==r) return l; int mid=(l+r)/2; k-=g[nd]; if (h[nd*2]>=k) return get(nd*2,l,mid,k); return get(nd*2+1,mid+1,r,k); } int calc(int nd,int l,int r,int x) { if (l==r) return g[nd]; int mid=(l+r)/2; if (x<=mid) return (calc(nd*2,l,mid,x)+g[nd]); return (calc(nd*2+1,mid+1,r,x)+g[nd]); } bool cmp(rec i,rec j) { return (i.v<j.v); } int main() { int i,x; scanf("%d\n",&n); fr(i,1,n) { scanf("%c%d\n",&ch,&a[i]); switch (ch) { case 'I': b[i]=0; break; case 'D': b[i]=1; break; case 'K': b[i]=2; break; default: b[i]=3; a[i]--; } c[i].v=a[i]; c[i].p=i; c[i].q=b[i]; } sort(c+1,c+n+1,cmp); m=0; c[0].v=-2000000000; fr(i,1,n) { if (c[i].q==2) continue; if (c[i].v>c[m].v) c[++m]=c[i]; a[c[i].p]=m; } fr(i,1,n) { switch (b[i]) { case 0: if (!e[a[i]]) { put(1,1,m,a[i],m,1); e[a[i]]=1; } break; case 1: if (e[a[i]] && a[i]) { put(1,1,m,a[i],m,-1); e[a[i]]=0; } break; case 2: if (a[i]>h[1]) printf("invalid\n"); else { x=get(1,1,m,a[i]); printf("%d\n",c[x]); } break; default: if (a[i]) x=calc(1,1,m,a[i]); else x=0; printf("%d\n",x); } } return 0; }
Code mẫu của happyboy99x
#include<cstdio> #include<algorithm> using namespace std; const int Q = 200000 + 2; int val[Q], nVal, qry[Q][2], q, bit[Q+Q], hgBit; //highestBit void enter() { char s[2]; scanf("%d", &q); for(int i = 0; i < q; ++i) { scanf("%s%d", s, &qry[i][1]); qry[i][0] = s[0]; if(s[0] == 'I') val[nVal++] = qry[i][1]; } } void add(int i, int v) { for(; i <= hgBit + hgBit; i += i & -i) bit[i] += v; } int read(int i) { int res = bit[i], z = i - (i & -i); for(int v = i - 1; v != z; v -= v & -v) res -= bit[v]; return res; } int sum(int i) { int res = 0; for(; i > 0; i -= i & -i) res += bit[i]; return res; } int lowerBound(int fre) { int bitmask = hgBit, idx = hgBit << 1; while(bitmask != 0 && idx > 0) { int tIdx = idx - bitmask; if(fre <= bit[tIdx]) idx = tIdx; else fre -= bit[tIdx]; bitmask >>= 1; } return idx; } void solve() { sort(val, val + nVal); nVal = unique(val, val + nVal) - val; hgBit = nVal; while(hgBit & (hgBit - 1)) hgBit -= hgBit & -hgBit; int n = 0; for(int i = 0, v, *t; i < q; ++i) switch(qry[i][0]) { case 'I': v = lower_bound(val, val + nVal, qry[i][1]) - val + 1; if(read(v) == 0) add(v, 1), ++n; break; case 'D': t = lower_bound(val, val + nVal, qry[i][1]); if(*t == qry[i][1]) { v = t - val + 1; if(read(v) == 1) add(v, -1), --n; } break; case 'C': v = lower_bound(val, val + nVal, qry[i][1]) - val; printf("%d\n", sum(v)); break; case 'K': if(qry[i][1] > n) printf("invalid\n"); else printf("%d\n", val[lowerBound(qry[i][1]) - 1]); break; } } int main() { enter(); solve(); return 0; }
Code mẫu của ladpro98
#include <bits/stdc++.h> using namespace std; class Treap { struct Node { int key, prior, size; Node *l, *r; Node(int key): key(key), prior(rand()), size(1), l(NULL), r(NULL) {} ~Node() { delete l; delete r; } }; int size(Node *x) { return x ? x->size : 0; } void update(Node *x) { if (!x) return; x->size = size(x->l) + size(x->r) + 1; } Node* join(Node *l, Node *r) { if (!l || !r) return l ? l : r; if (l->prior < r->prior) return l->r = join(l->r, r), update(l), l; else return r->l = join(l, r->l), update(r), r; } void split(Node *v, int x, Node* &l, Node* &r) { if (!v) l = r = NULL; else if (v->key < x) split(v->r, x, v->r, r), l = v; else split(v->l, x, l, v->l), r = v; update(v); } int getKeyByOrder(Node *v, int k) { int cnt = size(v->l); if (k <= cnt) return getKeyByOrder(v->l, k); if (k == cnt + 1) return v->key; return getKeyByOrder(v->r, k - cnt - 1); } void show(Node *x) { if (!x) return; show(x->l); cout << x->key << ' '; show(x->r); } Node *root; public: Treap(): root(NULL) {} ~Treap() { delete root; } bool insert(int x) { Node *l, *mid, *r; split(root, x, l, mid); split(mid, x + 1, mid, r); if (mid) { root = join(join(l, mid), r); return false; } root = join(join(l, new Node(x)), r); return true; } bool erase(int x) { Node *l, *mid, *r; split(root, x, l, mid); split(mid, x + 1, mid, r); root = join(l, r); if (mid) { delete mid; return true; } return false; } int getKeyByOrder(int x) { return getKeyByOrder(root, x); } int countSmaller(int x) { Node *l, *r; split(root, x, l, r); int res = size(l); root = join(l, r); return res; } int size() const { return root ? root->size : 0; } void show() { cout << "{"; show(root); cout << "}\n"; } }; int main() { ios::sync_with_stdio(false); cin.tie(NULL); Treap S; int nQuery; cin >> nQuery; while (nQuery--) { char cmd; int x; cin >> cmd >> x; if (cmd == 'I') S.insert(x); else if (cmd == 'D') S.erase(x); else if (cmd == 'C') cout << S.countSmaller(x) << '\n'; else if (S.size() < x) cout << "invalid\n"; else cout << S.getKeyByOrder(x) << '\n'; } return 0; }
Code mẫu của RR
{$R+,Q+} const finp=''; fout=''; MaxQ=200000; MaxD=4*MaxQ; Var A:Array[1..MaxQ] of Longint; Var ID:Array[1..MaxQ] of Longint; Var Oder:Array[1..MaxQ] of Char; Var Q,N,U:Longint; Var F:Array[1..MaxD] of Longint; (***************************) procedure OpenFile; inline; begin assign(input,finp);reset(input); assign(output,fout);rewrite(output); end; (****************************) procedure CloseFile; inline; Begin Close(input); Close(output); End; (**************************************) procedure QS(l,r:longint); inline; var i,j:longint; tg,k:longint; begin if l>=r then exit; k:=A[l+random(r-l+1)]; i:=l; j:=r; repeat while (A[i]<K) do inc(i); while (A[j]>K) do dec(j); if i<=j then Begin Tg:=A[i];A[i]:=A[j];A[j]:=tg; Inc(i); Dec(j); End; until i>j; QS(L,j); QS(i,R); end; (*******************************) Procedure Init; inline; Var j,i:Longint; Begin j:=1; For i:=2 to Q do If A[i]<>A[j] Then Begin Inc(j); A[j]:=A[i]; End; N:=j; End; (*******************************) procedure Enter; inline; Var i:Longint; Begin Readln(Q); For i:=1 to Q do Begin Readln(Oder[i],A[i]); ID[i]:=A[i]; End; QS(1,Q); Init; End; (*******************************) Procedure Inc_Seq(L,R,K:Longint); inline; Var Mid,Con:Longint; Begin If (A[R]<U)Or(A[L]>U) Then Exit; If (L=R)Then Begin F[K]:=1; Exit; End; Mid:=(L+R) Shr 1; Con:=K Shl 1; Inc_Seq(L,Mid,Con); Inc_Seq(Mid+1,R,Con+1); F[K]:=F[Con]+F[Con+1]; End; (*******************************) Procedure Dec_Seq(L,R,K:Longint); inline; Var Mid,Con:Longint; Begin If (A[R]<U)Or(A[L]>U) Then Exit; If (L=R)Then Begin F[K]:=0; Exit; End; Mid:=(L+R)shr 1; Con:=K Shl 1; Dec_Seq(L,Mid,Con); Dec_Seq(Mid+1,R,Con+1); F[K]:=F[Con]+F[Con+1]; End; (*******************************) Function Find(L,R,K:Longint):Longint; inline; Var Mid:Longint; Con:Longint; Begin If L=R Then Exit(L); Mid:=(L+R) shr 1; Con:=K Shl 1; If F[Con]>=U Then Find:=Find(L,Mid,Con) Else Begin U:=U-F[Con]; Find:=Find(Mid+1,R,Con+1); End; End; (*******************************) Function Get_Seq(L,R,K:Longint):Longint; inline; Var Mid:Longint; Con:Longint; Begin Get_Seq:=0; If A[L]>=U Then Exit; If A[R]<U Then Begin Get_Seq:=F[K]; Exit; End; Mid:=(L+R) shr 1; Con:=K Shl 1; Get_Seq:=Get_Seq(L,Mid,Con)+Get_Seq(Mid+1,R,Con+1); End; (*******************************) procedure Solve; Var i:Longint; Begin For i:=1 to Q do Begin U:=ID[i]; If Oder[i]='I' Then Inc_Seq(1,N,1) Else If Oder[i]='D' Then Dec_Seq(1,N,1) Else If Oder[i]='K' Then Begin If U>F[1] Then Writeln('invalid') Else Writeln(A[Find(1,N,1)]); End Else Writeln(Get_Seq(1,N,1)); End; End; (*******************************) Begin OpenFile; Enter; Solve; CloseFile; End.
Code mẫu của hieult
#include <stdlib.h> #include <stdio.h> //#include <conio.h> struct t_query { char type; int param; int porder; } ; int queries; t_query query[200010]; void read_input() { char s[16]; scanf("%d",&queries); for(int i = 0;i<queries;i++) { scanf("%s",s); query[i].type = s[0]; scanf("%d",&query[i].param); } } int compare_queries( const void *ptr1, const void *ptr2) { return query[*((int *)ptr1)].param - query[*((int *)ptr2)].param; } int qorder[200010],value[200010],distinct; void find_order() { for(int i = 0;i<queries;i++) qorder[i] = i; qsort(qorder,queries,sizeof(int),compare_queries); query[qorder[0]].porder = 0; value[0] = query[qorder[0]].param; distinct = 1; for(int i = 1;i<queries;i++) { if(query[qorder[i]].param!=query[qorder[i-1]].param){ query[qorder[i]].porder = query[qorder[i-1]].porder+1; value[distinct++] = query[qorder[i]].param; } else query[qorder[i]].porder = query[qorder[i-1]].porder; } } int norm,present[1<<19],totpresent; void init_present() { for(norm = 1;norm<distinct;norm*=2); for(int i = 1;i<2*norm;i++) present[i] = 0; totpresent = 0; } void insert_value(int v) { int i = norm+v; if(present[i]) return; for(;i;i/=2) present[i]++; totpresent++; } void delete_value(int v) { int i = norm+v; if(!present[i]) return; for(;i;i/=2) present[i]--; totpresent--; } int kth_value(int root, int size, int k){ if((root == 1) && (k>present[root])) return -1; if(size == 1) return root-norm; if(k<=present[2*root]) return kth_value(2*root,size/2,k); else return kth_value(2*root+1,size/2,k-present[2*root]); } int count_smaller(int root,int size, int v) { if(v==0) return 0; if(v<size/2) return count_smaller(2*root,size/2,v); else return present[2*root]+count_smaller(2*root+1,size/2,v-size/2); } int main() { // freopen("ORDERSET.in","r",stdin); int q,i; read_input(); find_order(); init_present(); for(q = 0;q<queries;q++) switch(query[q].type) { case 'I' : insert_value(query[q].porder); break; case 'D' : delete_value(query[q].porder); break; case 'K': { i = kth_value(1,norm,query[q].param); if(i<0) printf("invalid\n"); else printf("%d\n",value[i]); break; } case 'C': { printf("%d\n",count_smaller(1,norm,query[q].porder)); break; } } // getch(); }
Code mẫu của ll931110
{$MODE DELPHI} program ORDERSET; const input = ''; output = ''; maxn = 200000; var a,b,pos,list,t: array[1..maxn] of integer; ch: array[1..maxn] of char; q,num,c1: integer; fi,fo: text; procedure openfile; begin assign(fi, input); reset(fi); assign(fo, output); rewrite(fo); end; //Pre-processing procedure init; var i: integer; begin c1 := 0; readln(fi, q); for i := 1 to q do begin read(fi, ch[i]); if ch[i] = 'K' then readln(fi, a[i]) else begin inc(c1); readln(fi, b[c1]); pos[c1] := i; end; end; end; procedure swap(var x,y: integer); var z: integer; begin z := x; x := y; y := z; end; procedure swapint(i,j: integer); begin swap(b[i],b[j]); swap(pos[i],pos[j]); end; procedure quicksort; procedure par(l,h: integer); var i,j,p: integer; begin if l >= h then exit; i := l; j := h; p := b[random(h - l + 1) + l]; repeat while b[i] < p do inc(i); while b[j] > p do dec(j); if i <= j then begin if i < j then swapint(i,j); inc(i); dec(j); end; until i > j; par(l,j); par(i,h); end; var i: integer; begin if c1 = 0 then exit; par(1,c1); num := 1; a[pos[1]] := 1; list[1] := b[1]; for i := 2 to c1 do begin if b[i] > b[i - 1] then begin inc(num); list[num] := b[i]; end; a[pos[i]] := num; end; end; //End of pre-processing //BIT's operations procedure update(x,k: integer); begin while x <= maxn do begin t[x] := t[x] + k; x := x + (x and -x); end; end; function calc(x: integer): integer; var r: integer; begin r := 0; while x > 0 do begin r := r + t[x]; x := x - (x and -x); end; calc := r; end; //End of BIT's operations //Query's operations procedure insert(x: integer); begin if calc(x) = calc(x - 1) then update(x,1); end; procedure delete(x: integer); begin if calc(x) > calc(x - 1) then update(x,-1); end; procedure kth(x: integer); var inf,sup,mid: integer; res,tmp: integer; begin if calc(num) < x then begin writeln(fo, 'invalid'); exit; end; inf := 1; sup := num; repeat mid := (inf + sup) div 2; tmp := calc(mid); if tmp = x then begin res := mid; if tmp = calc(mid - 1) then sup := mid - 1 else break; end else if tmp < x then inf := mid + 1 else begin res := mid; sup := mid - 1; end; until inf > sup; writeln(fo, list[res]); end; procedure count(x: integer); begin writeln(fo, calc(x - 1)); end; //End of query's operations //Answer procedure solve; var i: integer; begin fillchar(t, sizeof(t), 0); for i := 1 to q do case ch[i] of 'I': insert(a[i]); 'D': delete(a[i]); 'K': kth(a[i]); 'C': count(a[i]); end; end; procedure closefile; begin close(fo); close(fi); end; begin openfile; init; quicksort; solve; closefile; end.
Code mẫu của skyvn97
#include<cstdio> #include<cassert> #define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1) #define REP(i,n) for (int i=0;i<(n);i=i+1) const char inv[]="invalid"; struct node { int val,nnode; node *parent,*left,*right; node(){} node(const int &x) { val=x; nnode=1; parent=NULL; left=NULL; right=NULL; } void calculate(void) { int l,r; if (left==NULL) l=0; else l=left->nnode; if (right==NULL) r=0; else r=right->nnode; nnode=l+r+1; } bool isleft(const node *a) const { return (a!=NULL && left==a); } bool isright(const node *a) const { return (a!=NULL && right==a); } }; node *root; void create(node *&a,const int &x) { if (a!=NULL) return; a=new node(x); } void link(node *a,node *b,int dir) { if (a==NULL) { root=b; if (root!=NULL) root->parent=NULL; return; } if (dir==1) a->left=b; else a->right=b; if (b!=NULL) b->parent=a; } void treeview(node *a,int lev) { if (a==NULL) return; REP(i,lev) printf(" "); printf("%d|%d\n",a->val,a->nnode); REP(i,lev) printf(" "); printf("left\n"); treeview(a->left,lev+1); REP(i,lev) printf(" "); printf("right\n"); treeview(a->right,lev+1); } void left_rotation(node *a) { node *b,*c; int dir=0; c=a->parent; if (c!=NULL) { if (c->isleft(a)) dir=1; else dir=2; } b=a->right; link(a,b->left,2); link(b,a,1); link(c,b,dir); } void right_rotation(node *a) { node *b,*c; int dir=0; c=a->parent; if (c!=NULL) { if (c->isleft(a)) dir=1; else dir=2; } b=a->left; link(a,b->right,1); link(b,a,2); link(c,b,dir); } void splay(node *a) { while (a->parent!=NULL) { if (a->parent->parent==NULL) { if (a->parent->isleft(a)) { right_rotation(a->parent); a->right->calculate(); } else { left_rotation(a->parent); a->left->calculate(); } } else { if (a->parent->isleft(a)) { if (a->parent->parent->isleft(a->parent)) { right_rotation(a->parent->parent); right_rotation(a->parent); a->right->right->calculate(); a->right->calculate(); } else { right_rotation(a->parent); left_rotation(a->parent); a->left->calculate(); a->right->calculate(); } } else { if (a->parent->parent->isright(a->parent)) { left_rotation(a->parent->parent); left_rotation(a->parent); a->left->left->calculate(); a->left->calculate(); } else { left_rotation(a->parent); right_rotation(a->parent); a->right->calculate(); a->left->calculate(); } } } a->calculate(); } } void find(const int &x) { if (root==NULL) return; node *p=root; while (true) { if (p->val==x) break; if (p->val>x) { if (p->left!=NULL) p=p->left; else break; } else { if (p->right!=NULL) p=p->right; else break; } } splay(p); } void split(const int &x,node *&a) { if (root==NULL) { a=NULL; return; } find(x); a=root->right; if (a!=NULL) a->parent=NULL; root->right=NULL; root->calculate(); } void merge(node *a) { if (root==NULL) { link(NULL,a,1); return; } node *p=root; while (p->right!=NULL) p=p->right; splay(p); link(p,a,2); p->calculate(); } void insert(const int &x) { //printf("Insert %d\n",x); node *p,*q; int dir=0; q=NULL; p=root; while (p!=NULL) { if (p->val==x) return; q=p; if (p->val>x) { p=p->left; dir=1; } else { p=p->right; dir=2; } } create(p,x); link(q,p,dir); splay(p); } void erase(const int &x) { //printf("Erase %d\n",x); node *p,*l; split(x,p); if (root==NULL || root->val!=x) { merge(p); return; } l=root->left; delete root; link(NULL,l,1); merge(p); } void value(const int &k) { if (root==NULL || root->nnode<k) { printf("%s\n",inv); return; } int rem=0; int nleft; node *p=root; while (true) { if (p->left==NULL) nleft=0; else nleft=p->left->nnode; if (rem+nleft+1==k) { printf("%d\n",p->val); splay(p); return; } if (rem+nleft+1>k) p=p->left; else { p=p->right; rem+=nleft+1; } } } void count(const int &k) { if (root==NULL) { printf("0\n"); return; } int res=0; int nleft; node *p=root; while (true) { if (p->left==NULL) nleft=0; else nleft=p->left->nnode; if (p->val<k) { res+=nleft+1; if (p->right!=NULL) p=p->right; else break; } else { if (p->left!=NULL) p=p->left; else break; } } printf("%d\n",res); splay(p); } void answer(void) { root=NULL; char type; int v,q; scanf("%d",&q); REP(i,q) { scanf(" %c",&type); scanf("%d",&v); //fprintf(stdout,"Query %d: %c %d\n",i+1,type,v); if (type=='I') insert(v); if (type=='D') erase(v); if (type=='K') value(v); if (type=='C') count(v); //int nn=0; //if (root!=NULL) nn=root->nnode; //fprintf(stderr,"%d\n",nn); //treeview(root,0); } } int main(void) { answer(); return 0; }
Code mẫu của khuc_tuan
#include <iostream> using namespace std; struct Instruction { char c; int x; }; int Q; Instruction a[200020]; char buf[100]; int ds[200020], nd; int sum[200020 * 4], value[200020]; void add(int n, int l, int r, int p, int v) { sum[n] += v; if(l<r) { int m = (l+r) / 2; if(p<=m) add( 2*n, l, m, p, v); else add( 2*n+1, m+1, r, p, v); } } int dem(int n, int l, int r, int x) { if(ds[r] < x) return sum[n]; if(ds[l] >= x) return 0; if(l<r) { int m = (l+r) / 2; return dem( 2*n, l, m, x) + dem( 2*n+1, m+1, r, x); } } int getK(int n, int l, int r, int k) { if(k > sum[n]) return -1; if(l==r) return l; int m = (l+r) / 2; if(sum[2*n] >= k) return getK( 2*n, l, m, k); else return getK( 2*n+1, m+1, r, k - sum[2*n]); } int main() { scanf("%d", &Q); for(int i=0;i<Q;++i) { gets(buf); scanf("%c %d", &a[i].c, &a[i].x); } for(int i=0;i<Q;++i) if(a[i].c=='I') ds[nd++] = a[i].x; sort( ds, ds+nd); nd = unique(ds, ds+nd) - ds; for(int i=0;i<Q;++i) { if(a[i].c=='I') { int pos = lower_bound(ds, ds+nd, a[i].x) - ds; if(value[pos]==0) add( 1, 0, nd-1, pos, 1), value[pos] = 1; } else if(a[i].c=='D') { int pos = lower_bound( ds, ds+nd, a[i].x) - ds; if(pos < nd && ds[pos] == a[i].x && value[pos]==1) add( 1, 0, nd-1, pos, -1), value[pos] = 0; } else if(a[i].c=='K') { int pos = getK( 1, 0, nd-1, a[i].x); if(pos < 0 || pos >= nd) printf("invalid\n"); else printf("%d\n", ds[pos]); } else if(a[i].c=='C') { int res = dem( 1, 0, nd-1, a[i].x); printf("%d\n", res); } } return 0; }
Comments