Luogu

动态区间第K大的整体二分解法

之前学主席树的时候就做了这道题（明明是树套树不是主席树啊），码量挺大而且调了我一个晚上。换成整体二分我半个小时就写完了而且一A。

写起来就是爽。

其实原理很简单，先把修改和询问放在一起，注意这里不能排序，要严格按照时间戳进行处理。

区间的初值也视作一次修改，之后的每次修改要当成两次，即删除原先那个数，再加入新的那个数。

对于当前的一些询问，二分一个答案\(mid\)。处理所有修改的值小于等于\(mid\)的修改操作，用树状数组维护区间内有多少个数的值小于等于\(mid\)，再把这个数与询问的\(k\)比较，选择向左递归（答案更小）还是向右递归（答案更大）。注意向左向右的时候要保证原修改查询的有序性，即对于某一个修改和某一个查询，若他们被分在了相同的一边（左或右），那么他们的相对顺序一定不能改变。

code

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

using namespace std;

const int N = 1e5+5;

int gi()

{

    int x=0,w=1;char ch=getchar();

    while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

    if (ch=='-') w=0,ch=getchar();

    while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

    return w?x:-x;

}

struct node{

    int opt,x,y,id,k;

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

int n,m,cnt,qcnt,a[N],tmp[N],c[N],ans[N];

void modify(int k,int v){while (k<=n) c[k]+=v,k+=k&-k;}

int query(int k){int s=0;while (k) s+=c[k],k-=k&-k;return s;}

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 (q[i].opt==0) ans[q[i].id]=l;

        return;

    }

    int mid=l+r>>1;

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

        if (q[i].opt==0) tmp[q[i].id]=query(q[i].y)-query(q[i].x-1);

        else if (q[i].y<=mid) modify(q[i].x,q[i].opt);

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

        if (q[i].opt!=0&&q[i].y<=mid) modify(q[i].x,-q[i].opt);

    int t1=0,t2=0;

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

        if (q[i].opt==0)

            if (q[i].k<=tmp[q[i].id]) q1[++t1]=q[i];

            else q[i].k-=tmp[q[i].id],q2[++t2]=q[i];

        else

            if (q[i].y<=mid) q1[++t1]=q[i];

            else q2[++t2]=q[i];

    for (int i=L,j=1;j<=t1;i++,j++) q[i]=q1[j];

    for (int i=L+t1,j=1;j<=t2;i++,j++) q[i]=q2[j];

    solve(L,L+t1-1,l,mid);solve(L+t1,R,mid+1,r);

}

int main()

{

    n=gi();m=gi();

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

    {

        a[i]=gi();

        q[++cnt]=(node){1,i,a[i]};

    }

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

    {

        char ch=getchar();

        while (ch!='C'&&ch!='Q') ch=getchar();

        if (ch=='C')

        {

            int x=gi(),y=gi();

            q[++cnt]=(node){-1,x,a[x]};

            a[x]=y;

            q[++cnt]=(node){1,x,a[x]};

        }

        else

        {

            int l=gi(),r=gi(),k=gi();

            q[++cnt]=(node){0,l,r,++qcnt,k};

        }

    }

    solve(1,cnt,0,1e9);

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

    return 0;

}