HDU - 5412 CRB and Queries (整体二分)

动态区间第k小，但是这道题的话用主席树+树状数组套线段树的空间复杂度是O(nlog²n)会爆掉。

另一种替代的方法是用树状数组套平衡树，空间复杂度降到了O(nlogn)，但我感觉平衡树是个挺恶心的东西，而且时间复杂度是O(nlog³n)，比主席树还多了个logn。

最高效的方法是用一个叫整体二分的东西算法，它的基本思想是这样的：

假设当前所有查询的答案范围都在[l,r]之间，设mid=(l+r)/2，那么我们只处理所有修改后的值在[l,mid]中的修改操作，把不需要执行的修改操作全部扔到后半区间，那么对于每个询问操作都可以知道它的答案是在[l,mid]之间还是(mid+1,r]之间，这样就把所有的询问划分到了两个独立的区间，然后递归处理即可。本质上是将原序列转化成01序列，这样处理起来就方便多了。与CDQ分治较为类似，是个很神奇的算法。

空间复杂度O(n)，时间复杂度O(nlog²n)

 #include<bits/stdc++.h>

 using namespace std;

 const int inf=0x3f3f3f3f;

 const int N=1e5+;

 struct QR {

     int f,l,r,k,u,x,dx;

 } qr[N<<];

 int a[N],c[N],b[N<<],lq[N<<],rq[N<<],nq,tot,ans[N],n,m;

 int lowbit(int x) {return x&-x;}

 void add(int u,int x) {

     for(; u<=n; u+=lowbit(u))c[u]+=x;

 }

 int query(int u) {

     int ret=;

     for(; u; u-=lowbit(u))ret+=c[u];

     return ret;

 }

 void solve(int l,int r,int L,int R) {

     if(L>R)return;

     if(l==r) {

         for(int i=L; i<=R; ++i)if(qr[b[i]].f)ans[qr[b[i]].u]=l;

         return;

     }

     int nl=,nr=,mid=(l+r)>>;

     for(int i=L; i<=R; ++i) {

         if(!qr[b[i]].f) {

             if(qr[b[i]].x<=mid)add(qr[b[i]].u,qr[b[i]].dx),lq[nl++]=b[i];

             else rq[nr++]=b[i];

         } else {

             int t=query(qr[b[i]].r)-query(qr[b[i]].l-);

             if(qr[b[i]].k<=t)lq[nl++]=b[i];

             else qr[b[i]].k-=t,rq[nr++]=b[i];

         }

     }

     for(int i=; i<nl; ++i)if(!qr[lq[i]].f)add(qr[lq[i]].u,-qr[lq[i]].dx);

     for(int i=; i<nl; ++i)b[L+i]=lq[i];

     for(int i=; i<nr; ++i)b[L+nl+i]=rq[i];

     solve(l,mid,L,L+nl-);

     solve(mid+,r,L+nl,R);

 }

 int main() {

     while(scanf("%d",&n)==) {

         nq=tot=;

         memset(c,,sizeof c);

         int maxn=;

         for(int i=; i<=n; ++i) {

             scanf("%d",&a[i]);

             maxn=max(maxn,a[i]);

             qr[nq++]=(QR) {,,,,i,a[i],};

         }

         scanf("%d",&m);

         while(m--) {

             int f;

             scanf("%d",&f);

             if(f==) {

                 int u,x;

                 scanf("%d%d",&u,&x);

                 qr[nq++]=(QR) {,,,,u,a[u],-};

                 qr[nq++]=(QR) {,,,,u,a[u]=x,};

                 maxn=max(maxn,a[u]);

             } else {

                 int l,r,k;

                 scanf("%d%d%d",&l,&r,&k);

                 qr[nq++]=(QR) {,l,r,k,tot++,,};

             }

         }

         for(int i=; i<nq; ++i)b[i]=i;

         solve(,maxn,,nq-);

         for(int i=; i<tot; ++i)printf("%d\n",ans[i]);

     }

     return ;

 }

巴特西

HDU - 5412 CRB and Queries (整体二分)

最新文章

热门文章