[BZOJ]3110: [Zjoi2013]K大数查询 整体二分+线段树

Description

有N个位置，M个操作。操作有两种，每次操作如果是1 a b c的形式表示在第a个位置到第b个位置，每个位置加入一个数c
如果是2 a b c形式，表示询问从第a个位置到第b个位置，第C大的数是多少。

题解：

这题跟入门题POJ2104差不多，不过那道题目是改点求段，这道题目是改段求段，用线段树代替树状数组就可以了。

代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define pa pair<int,int>
const int Maxn=50010;
const int inf=50000;
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<<3)+(x<<1)+(ch^48),ch=getchar();
    return x*f;
}
int n,m,cnt=0,ans[Maxn],trlen=0;
struct Opt{int type,x,y,z,id;}q[Maxn],q1[Maxn],q2[Maxn];
struct Seg{int l,r,lc,rc;LL s,lazy;}tr[Maxn<<1];
void build(int l,int r)
{
    int t=++trlen;
    tr[t].l=l;tr[t].r=r;tr[t].s=tr[t].lazy=0;
    if(l<r)
    {
        int mid=l+r>>1;
        tr[t].lc=trlen+1;build(l,mid);
        tr[t].rc=trlen+1;build(mid+1,r);
    }
}
void work(Seg &x,LL y){x.lazy+=y;x.s+=(LL)((x.r-x.l+1)*y);}
void push_down(Seg &x)
{
    LL t=x.lazy;x.lazy=0;
    work(tr[x.lc],t);work(tr[x.rc],t);
}
void add(int now,int l,int r,LL x)
{
    if(tr[now].l==l&&tr[now].r==r){work(tr[now],x);return;}
    int lc=tr[now].lc,rc=tr[now].rc,mid=tr[now].l+tr[now].r>>1;
    if(tr[now].lazy!=0)push_down(tr[now]);
    if(r<=mid)add(lc,l,x);
    else if(l>mid)add(rc,x);
    else add(lc,mid,x),add(rc,mid+1,x);
    tr[now].s=tr[lc].s+tr[rc].s;
}
LL query(int now,int r)
{
    if(tr[now].l==l&&tr[now].r==r)return tr[now].s;
    int lc=tr[now].lc,mid=tr[now].l+tr[now].r>>1;
    if(tr[now].lazy!=0)push_down(tr[now]);
    if(r<=mid)return query(lc,r);
    else if(l>mid)return query(rc,r);
    else return query(lc,mid)+query(rc,r);
    tr[now].s=tr[lc].s+tr[rc].s;
}
void solve(int l,int L,int R)
{
    if(l>r)return;
    if(L==R)
    {
        for(int i=l;i<=r;i++)
        if(q[i].type==2)ans[q[i].id]=L;
        return;
    }
    int Mid=L+R>>1,l1=0,l2=0;
    for(int i=l;i<=r;i++)
    {
        if(q[i].type==1)
        {
            if(q[i].z>Mid)add(1,q[i].x,q[i].y,1),q2[++l2]=q[i];
            else q1[++l1]=q[i];
        }
        else
        {
            LL t=query(1,q[i].y);
            if(t<q[i].z)q[i].z-=t,q1[++l1]=q[i];
            else q2[++l2]=q[i];
        }
    }
    for(int i=1;i<=l1;i++)q[l+i-1]=q1[i];
    for(int i=1;i<=l2;i++)q[l+i+l1-1]=q2[i];
    for(int i=1;i<=l2;i++)if(q2[i].type==1)add(1,q2[i].x,q2[i].y,-1);
    solve(l,l+l1-1,L,Mid);solve(l+l1,Mid+1,R);
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=m;i++)
    {
        q[i].type=read(),q[i].x=read(),q[i].y=read(),q[i].z=read();
        if(q[i].type==2)q[i].id=++cnt;
    }
    build(1,n);
    solve(1,-inf,inf);
    for(int i=1;i<=cnt;i++)printf("%dn",ans[i]);
}