BZOJ/1901.cpp

   1 /**************************************************************
   2     Problem: 1901
   3     User: dennisyang
   4     Language: C++
   5     Result: Accepted
   6     Time:1012 ms
   7     Memory:59508 kb
   8 ****************************************************************/
   9
  10 //Algorithm: Fenwick Tree & Persistent Segment Tree
  11 #include <cstdio>
  12 #include <vector>
  13
  14 const int maxnode = 5e6 + 10,maxn = 1e4 + 10,rlim = 1<<30;
  15
  16 struct node {
  17     int size;
  18     node *ch[2];
  19 } pool[maxnode],*tot = &pool[0],*root[maxn];
  20
  21 int n,m,orig[maxn];
  22
  23 node* Insert(node* orig, int l, int r, int pos, int val) {
  24     if (orig == NULL) orig = tot++;
  25     orig->size += val;
  26     if (l == r) return orig;
  27     int m = (l + r) >> 1;
  28     if (pos <= m) orig->ch[0] = Insert(orig->ch[0],l,m,pos,val); else orig->ch[1] = Insert(orig->ch[1],m+1,r,pos,val);
  29     return orig;
  30 }
  31
  32 inline int lowbit(int x) { return x & -x; }
  33
  34 inline void get(std::vector<node*> &tree, int idx) {
  35     tree.clear();
  36     while (idx) {
  37         tree.push_back(root[idx]);
  38         idx -= lowbit(idx);
  39     }
  40 }
  41
  42 inline int getsum(std::vector<node*> &tree) {
  43     int res = 0;
  44     std::vector<node*>::iterator iter;
  45     for (iter = tree.begin(); iter != tree.end(); ++iter)
  46         if ((*iter) && (*iter) -> ch[0]) res += (*iter) -> ch[0] -> size;
  47     return res;
  48 }
  49
  50 inline void turn(std::vector<node*> &tree, bool d) {
  51     std::vector<node*>::iterator iter;
  52     for (iter = tree.begin(); iter != tree.end(); ++iter)
  53         if (*iter) *iter = (*iter) -> ch[d];
  54 }
  55
  56 inline void update(int idx, int pos, int val) {
  57     while (idx <= n) {
  58         root[idx] = Insert(root[idx],0,rlim,pos,val);
  59         idx += lowbit(idx);
  60     }
  61 }
  62
  63 int Query(int l, int r, int k, std::vector<node*> lt, std::vector<node*> rt) {
  64     if (l == r) return l;
  65     int m = (l + r) >> 1, cnt = getsum(rt) - getsum(lt);
  66     bool d = k > cnt;
  67     turn(lt,d);
  68     turn(rt,d);
  69     if (d) {
  70         l = m + 1;
  71         k -= cnt;
  72     } else r = m;
  73     return Query(l,r,k,lt,rt);
  74 }
  75
  76 inline int query(int l, int r, int k) {
  77     std::vector<node*> tree[2];
  78     get(tree[0],l-1);
  79     get(tree[1],r);
  80     return Query(0,rlim,k,tree[0],tree[1]);
  81 }
  82
  83 int main() {
  84     std::scanf("%d%d",&n,&m);
  85     for (int i = 1,t; i <= n; ++i) {
  86         std::scanf("%d",orig + i);
  87         update(i,orig[i],1);
  88     }
  89     char op;
  90     int pos,num,l,r,k;
  91     while (m--) {
  92         std::scanf(" %c",&op);
  93         switch (op) {
  94             case 'C':
  95                 std::scanf("%d%d",&pos,&num);
  96                 update(pos,orig[pos],-1);
  97                 update(pos,orig[pos] = num,1);
  98                 break;
  99             case 'Q':
 100                 std::scanf("%d%d%d",&l,&r,&k);
 101                 std::printf("%d\n",query(l,r,k));
 102                 break;
 103         }
 104     }
 105     return 0;
 106 }