[ZJOI2013]K大数查询——整体二分

题目描述

有N个位置，M个操作。操作有两种，每次操作如果是：

• 1 a b c：表示在第a个位置到第b个位置，每个位置加上一个数c
• 2 a b c：表示询问从第a个位置到第b个位置，第C大的数是多少。

思路

　　比较基础的整体二分。我们二分出$mid，对于值域[l,r]对应的操作[L,R]$，若为操作1，则考虑把$val>mid$的插入线段树中，表示比$mid$大的值的个数，若为操作2，先询问$[q[i].l,q[i].r]$中比$mid$大的值的个数，然后把当前询问填到左右区间再处理。讲的很简单，调过来整体二分原理的一些东西，，，毕竟这题还是比较板子的。

code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define I inline
#define smid (l+r>>1)
#define lch (now<<1)
#define rch (now<<1|1)
using namespace std;
const int N=50010;
typedef long long LL;
int n,m,tot;
LL ans[N];
struct segment
{
    LL sum,pls;
}sgt[N<<2];
struct node
{
    int l,r,k,op,id;
}q[N<<1],q1[N<<1],q2[N<<1];

I int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

I LL readll()
{
    LL x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

I void pushup(int now)
{
    sgt[now].sum=sgt[lch].sum+sgt[rch].sum;
}

I void pushdown(int now,int l,int r)
{
    if(!sgt[now].pls)return;
    sgt[lch].pls+=sgt[now].pls;
    sgt[rch].pls+=sgt[now].pls;
    sgt[lch].sum+=(smid-l+1)*sgt[now].pls;
    sgt[rch].sum+=(r-smid)*sgt[now].pls;
    sgt[now].pls=0;
}
    

I void modify(int now,int l,int r,int x,int y,int val)
{
    if(x<=l&&r<=y)
    {
        sgt[now].pls+=val;
        sgt[now].sum+=(r-l+1)*val;
        return;
    }
    pushdown(now,l,r);
    if(x<=smid)modify(lch,l,smid,x,y,val);
    if(smid<y)modify(rch,smid+1,r,x,y,val);
    pushup(now);
}

I LL query(int now,int l,int r,int x,int y)
{
    if(x<=l&&r<=y)return sgt[now].sum;
    pushdown(now,l,r);
    LL res=0;
    if(x<=smid)res+=query(lch,l,smid,x,y);
    if(smid<y)res+=query(rch,smid+1,r,x,y);
    pushup(now);
    return res;
}

I 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].op==2)ans[q[i].id]=l;
        return;
    }
    int mid=(l+r>>1),cnt1=0,cnt2=0;
    for(int i=L;i<=R;i++)
    {
        if(q[i].op==1)
        {
            if(q[i].k>mid)
            modify(1,1,n,q[i].l,q[i].r,1),q2[++cnt2]=q[i];
            else q1[++cnt1]=q[i];
        }
        else
        {
            LL tmp=query(1,1,n,q[i].l,q[i].r);
            if(q[i].k>tmp)q[i].k-=tmp,q1[++cnt1]=q[i];
            else q2[++cnt2]=q[i];
        }
    }
    for(int i=1;i<=cnt2;i++)if(q2[i].op==1)modify(1,1,n,q2[i].l,q2[i].r,-1);
    for(int i=1;i<=cnt1;i++)q[L+i-1]=q1[i];
    for(int i=1;i<=cnt2;i++)q[L+cnt1+i-1]=q2[i];
    solve(l,mid,L,L+cnt1-1);solve(mid+1,r,L+cnt1,R);
}


int main()
{
    n=read();m=read();
    for(int i=1;i<=m;i++)
    {
        q[i].op=read();q[i].l=read();q[i].r=read();q[i].k=readll();
        if(q[i].op==2)q[i].id=++tot;
    }
    solve(-n,n,1,m);
    for(int i=1;i<=tot;i++)printf("%lld
",ans[i]);
}