【BZOJ1901】【ZJU2112】Dynamic Rankings

Author Avatar
q234rty 7月 27, 2016

树状数组套动态开点的权值线段树即可。

树状数组中的每个节点 i 为满足 j 在 [i−lowbit(i)+1,i] 的所有 a[j] 组成的权值线段树。

修改操作对应树状数组的修改操作，但加法变成了权值线段树的插入，减法变成了权值线段树的删除。

查询对应在 O(\log n) 棵权值线段树的加减操作的结果上查询第k小，直接同时在这 O(\log n) 棵树上走即可。

需要离散化以减小空间。时空复杂度均为 O(n \log^2 n) 。

Code

  1. #include <cctype>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <algorithm>
  5. #define rep(i,f,t) for(int i=(f);i<=(t);i++)
  6. #define WTF
  7. using namespace std;
  8. const int MAXSIZE=10000020;
  9. int bufpos;
  10. char buf[MAXSIZE];
  11. void init(){
  12.     #ifdef LOCAL
  13.         freopen("1901.txt","r",stdin);
  14.     #endif // LOCAL
  15.     buf[fread(buf,1,MAXSIZE,stdin)]='\0';
  16.     bufpos=0;
  17. }
  18. int readint(){
  19.     int val=0;
  20.     for(;!isdigit(buf[bufpos]);bufpos++);
  21.     for(;isdigit(buf[bufpos]);bufpos++)
  22.         val=val*10+buf[bufpos]-'0';
  23.     return val;
  24. }
  25. char readchar(){
  26.     for(;isspace(buf[bufpos]);bufpos++);
  27.     return buf[bufpos++];
  28. }
  29. const int maxn=10001;
  30. const int maxm=10001;
  31. struct segkth{
  32.     private:
  33.         static const int maxt=16*16*(maxn+maxm);
  34.         struct node{
  35.             int sum,lson,rson;
  36.             node(){
  37.                 sum=lson=rson=0;
  38.             }
  39.         };
  40.         node t[maxt];
  41.         int n,cur;
  42.         int p,v;
  43.         void update(int& o,int l,int r){
  44.             if (!o)
  45.                 o=++cur;
  46.             t[o].sum+=v;
  47.             //printf("o=%d,l=%d,r=%d\n",o,l,r);
  48.             if (l==r)
  49.                 return;
  50.             int m=(l+r)/2;
  51.             if (p<=m)
  52.                 update(t[o].lson,l,m);
  53.             else update(t[o].rson,m+1,r);
  54.         }
  55.     public:
  56.         void init(int n,int maxv){
  57.             this->n=maxv;
  58.             cur=n;
  59.         }
  60.         void ins(int c,int x){
  61.             p=x,v=1;
  62.             update(c,1,n);
  63.         }
  64.         void del(int c,int x){
  65.             p=x,v=-1;
  66.             update(c,1,n);
  67.         }
  68.         int kth(int k,int* add,int addc,int* dec,int decc){
  69.             int l=1,r=n,mid;
  70.             while(l<r){
  71.                 //printf("l=%d,r=%d\n",l,r);
  72.                 mid=(l+r)/2;
  73.                 int sz=0;
  74.                 rep(i,1,addc)
  75.                     sz+=t[t[add[i]].lson].sum;
  76.                 rep(i,1,decc)
  77.                     sz-=t[t[dec[i]].lson].sum;
  78.                 if (sz>=k){ //left
  79.                     rep(i,1,addc)
  80.                         add[i]=t[add[i]].lson;
  81.                     rep(i,1,decc)
  82.                         dec[i]=t[dec[i]].lson;
  83.                     r=mid;
  84.                 }else{  //right
  85.                     k-=sz;
  86.                     rep(i,1,addc)
  87.                         add[i]=t[add[i]].rson;
  88.                     rep(i,1,decc)
  89.                         dec[i]=t[dec[i]].rson;
  90.                     l=mid+1;
  91.                 }
  92.             }
  93.             return l;
  94.         }
  95. }t;
  96. struct bit{
  97.     private:
  98.         static const int maxw=18;
  99.         int n;
  100.         int val[maxn];
  101.         int add[maxw],dec[maxw];
  102.         inline int lowbit(int x){
  103.             return x&-x;
  104.         }
  105.     public:
  106.         void init(int n,int *a,int maxv){
  107.             this->n=n;
  108.             t.init(n,maxv);
  109.             memcpy(val,a,sizeof(val));
  110.             rep(i,1,n)
  111.                 for(int j=i;j<=n;j+=lowbit(j))
  112.                     t.ins(j,val[i]);
  113.         }
  114.         void modify(int p,int v){
  115.             //WTF;
  116.             for(int i=p;i<=n;i+=lowbit(i))
  117.                 t.del(i,val[p]),t.ins(i,v);
  118.             val[p]=v;
  119.         }
  120.         int kth(int l,int r,int k){
  121.             //WTF;
  122.             int addc=0,decc=0;
  123.             for(int i=r;i;i-=lowbit(i))
  124.                 add[++addc]=i;
  125.             for(int i=l-1;i;i-=lowbit(i))
  126.                 dec[++decc]=i;
  127.             //WTF;
  128.             return t.kth(k,add,addc,dec,decc);
  129.         }
  130. }b;
  131. int a[maxn];
  132. int nums[maxn+maxm],cur;
  133. struct query{
  134.     char c;
  135.     int i,j,k;
  136. }q[maxm];
  137. int main(){
  138.     init();
  139.     //WTF;
  140.     int n=readint(),m=readint();
  141.     rep(i,1,n)
  142.         a[i]=readint(),nums[++cur]=a[i];
  143.     rep(i,1,m){
  144.         q[i].c=readchar(),q[i].i=readint(),q[i].j=readint();
  145.         if (q[i].c=='Q')
  146.             q[i].k=readint();
  147.         else nums[++cur]=q[i].j;
  148.     }
  149.     //WTF;
  150.     sort(nums+1,nums+cur+1);
  151.     cur=unique(nums+1,nums+cur+1)-nums-1;
  152.     rep(i,1,n)
  153.         a[i]=lower_bound(nums+1,nums+cur+1,a[i])-nums;
  154.     //WTF;
  155.     b.init(n,a,cur);
  156.     //WTF;
  157.     rep(i,1,m){
  158.         //WTF;
  159.         if (q[i].c=='Q'){
  160.             printf("%d\n",nums[b.kth(q[i].i,q[i].j,q[i].k)]);
  161.         }
  162.         else {
  163.             //WTF;
  164.             b.modify(q[i].i,lower_bound(nums+1,nums+cur+1,q[i].j)-nums);
  165.         }
  166.     }
  167. }

知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。
本文链接：https://www.q234rty.top/2016/07/27/bzoj1901/

隐藏