BZOJ_3110_[Zjoi2013]K大数查询_整体二分+树状数组

Description

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

Input

第一行N，M
接下来M行，每行形如1 a b c或2 a b c

Output

输出每个询问的结果

Sample Input

2 5
1 1 2 1
1 1 2 2
2 1 1 2
2 1 1 1
2 1 2 3

Sample Output

1
2
1

solve(b,e,l,r)表示处理b~e的询问，答案在l~r之间，同时处理插入，权值范围为l~r。

把所有操作都离线下来，同时使得操作在任意时刻都按时间戳顺序。

二分答案mid,对于插入的数大于mid就插进去(区间加)，否则丢到左边。

对于询问像正常的整体二分一样，查询区间和，然后往左走或往右走。

代码：

#include <stdio.h>

#include <string.h>

#include <algorithm>

using namespace std;

typedef unsigned int uint;

#define N 50050

int n,m,flg[N],ans[N];

struct Bit {

    uint c[N];

    void fix(int x,uint v) { for(;x<=n;x+=x&(-x)) c[x]+=v; }

    uint inq(int x) { uint re=0;for(;x;x-=x&(-x)) re+=c[x];return re;}

}A,B;

struct Q {

    int a,b,c,d,id;

}q[N],t[N];

void update(int x,int y,uint v) {

    A.fix(x,v); A.fix(y+1,-v);

    B.fix(x,x*v); B.fix(y+1,-(y+1)*v);

}

uint query(int x,int y) {

    return A.inq(y)*(y+1)-B.inq(y)-A.inq(x-1)*x+B.inq(x-1);

}

void solve(int b,int e,int l,int r) {

    int i;

    if(b>e) return ;

    if(l==r) {

        for(i=b;i<=e;i++) if(q[i].a==2) ans[q[i].id]=l;

        return ;

    }

    int mid=(l+r)>>1,lp=b-1,rp=e+1;

    for(i=b;i<=e;i++) {

        if(q[i].a==1) {

            if(q[i].d<=mid) t[++lp]=q[i];

            else update(q[i].b,q[i].c,1),t[--rp]=q[i];

        }else {

            uint tmp=query(q[i].b,q[i].c);

            if(q[i].d<=tmp) t[--rp]=q[i];

            else q[i].d-=tmp,t[++lp]=q[i];

        }

    }

    for(i=b;i<=e;i++) {

        if(q[i].a==1&&q[i].d>mid) update(q[i].b,q[i].c,-1);

    }

    for(i=b;i<=lp;i++) q[i]=t[i];

    for(i=rp;i<=e;i++) q[e-i+rp]=t[i];

    solve(b,lp,l,mid);

    solve(rp,e,mid+1,r);

}

int main() {

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

    int i;

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

        scanf("%d%d%d%d",&q[i].a,&q[i].b,&q[i].c,&q[i].d); q[i].id=i;

        if(q[i].a==2) flg[i]=1;

    }

    solve(1,m,-n,n);

    for(i=1;i<=m;i++) if(flg[i]) printf("%d\n",ans[i]);

}

秒客网