Dynamic Rankings（整体二分）

带修区间第k小。\(n,q\le 10^4\)。

这次我们旧瓶装新酒，不用带修主席树。我们用整体二分！整体二分是啥东西呢？

二分答案可以解决一次询问的问题。只要二分这个询问的答案就行了。

考虑这道题，如果改成一个询问，怎么用二分答案做（虽然其它方法随便做）。把初始值也看成一个修改，暴力修改值。二分区间第k小数的值v，把小于v的数都改成1，大于的都改成0。那么现在问题就变成了，查询区间中1的个数cnt。如果cnt<=k，那么第k小数的值肯定<=v。否则第k小数的值>v。

对于这道题，如果把所有询问都二分一遍，那么时间复杂度为\(O(q*nlogv)\)。炸了！！

好的，我们来边缘ob一波。我们发现，我们把所有询问都二分答案了一遍。可不可以把询问放到一个二分里呢？

这就是整体二分。把所有修改和询问按照时间排在一起，设当前层二分的答案是v。那么，就可以把小于v的所有数变成1，大于v的则变成0。

那么，对于这个层的每一个询问，它们都需要获得它们[l, r]区间中1的个数。并且，还要支持修改某个位置的值（把那个值变成0或变成1）。用树状数组维护就行了哟。

显然时间复杂度是\(O(logv*nlogn)=O(nlog^2n)\)。但是比起带修主席树来说，整体二分的常数相对小一些，不过也快不了多少。

能用整体二分的条件是：

询问满足可二分性
修改对询问的贡献独立
题目允许离线处理询问
……

整体二分可以二分第k大值，也可以二分时间（某个点被消灭的时间）。

还有一个东西，我讲不清楚，摘一下这里的博客：

关于整体二分

整体二分主要是把所有询问放在一起二分答案，然后把操作也一起分治。

什么时候用呢？

当你发现多组询问可以离线的时候

当你发现询问可以二分答案而且check复杂度对于单组询问可以接受的时候

当你发现询问的操作都是一样的的时候

你就可以使用整体二分这个东西了。

具体做法讲起来有些玄学，其实类似主席树转化到区间的操作或者线段树上二分。

想想：二分答案的时候，对于一个答案，是不是有些操作是没用的，有些操作贡献是不变的？

比如二分一个时间，那么时间后面发生的操作就是没有用的，时间前面的贡献是不变的。

二分一个最大值，比mid大的都是没用的，比mid小的个数是一定的。

整体二分就是利用了这么一个性质。

坑点：

树状数组不能暴力清零！（\(O(n^2logn)\)预警）



#include <cctype>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn=5e4+5;

struct Query{

    int x, y, k, type, dfn;  //l, r, k, 2, 询问编号 或者修改时值

}q[maxn], q1[maxn], q2[maxn];

int a[maxn], n, m, t, cntq, ans[maxn];

int seg[maxn];

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

void add(int x, int v){

    for (int i=x; i<=n; i+=lowbit(i))

        seg[i]+=v; }

int query(int x){ int re=0;

    for (int i=x; i>0; i-=lowbit(i))

        re+=seg[i]; return re; }

void solve(int qb, int qe, int l, int r){

    if (qb>qe) return;

    if (l==r){

        for (int i=qb; i<=qe; ++i)

            if (q[i].type==2) ans[q[i].dfn]=l;

        return; }

    int m=(l+r)>>1, f=0, s=0;  //f,s:左边/右边几个操作

    //memset(seg, 0, sizeof(seg));  这行的问题！

    for (int i=qb; i<=qe; ++i){

        if (q[i].type==1)

            if (q[i].x<=m){

                add(q[i].k, q[i].y);

                q1[f++]=q[i];

            } else q2[s++]=q[i];

        else {

            int t=query(q[i].y)-query(q[i].x-1);  //区间中有多少1

            if (t>=q[i].k) q1[f++]=q[i];

            else{ q[i].k-=t; q2[s++]=q[i]; }

        }

    }

    for (int i=0; i<f; ++i)

    	if (q1[i].type==1) add(q1[i].k, -q1[i].y);

    //左边的修改对右边没影响，右边的修改对左边的也没影响

    memcpy(q+qb, q1, f*sizeof(Query));

    memcpy(q+qb+f, q2, s*sizeof(Query));

    solve(qb, qb+f-1, l, m);

    solve(qb+f, qe, m+1, r);

}

int main(){

    scanf("%d%d", &n, &m);

    char c; int x, y, k, maxm=0;

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

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

        q[++cntq]=(Query){a[i], 1, i, 1, cntq}; }

    for (int i=1; i<=m; ++i){

        while (c=getchar(), !isgraph(c));

        scanf("%d%d", &x, &y); maxm=max(maxm, y);

        if (c=='Q'){

            scanf("%d", &k);

            q[++cntq]=(Query){x, y, k, 2, cntq};  //询问区间[x, y]，第k小数

        }else{

            q[++cntq]=(Query){a[x], -1, x, 1, cntq};  //由于只有a[x]<=m时，在前面会打标记，因此也在a[x]<=m时才消去

            a[x]=y;  //通过a[x]来判断修改要分到哪里

            q[++cntq]=(Query){a[x], 1, x, 1, cntq};  //a[k]=x

        }

    }

    solve(1, cntq, 0, maxm);

    for (int i=1; i<=cntq; ++i)

        if (ans[i]) printf("%d\n", ans[i]);

    return 0;

}

巴特西

Dynamic Rankings（整体二分）

Dynamic Rankings（整体二分）

最新文章

热门文章