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.

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

Please read the guidelines before commenting.


There are no comments at the moment.