Hướng dẫn giải của Order statistic set
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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; }
Bình luận