BZOJ3110: [Zjoi2013]K大数查询

整体二分+树状数组
这道题和某题类似：http://www.voidcn.com/article/p-dhtqhpdp-bph.html

整体二分，每次二分一个值，因为是求第k大，比二分值大的在 [l,r] 区间+1，询问就问这个区间的数，如果数量大于k，说明实际答案大于二分值，下放右区间，否则下放左区间，k减去询问的值（因为后面不会再考虑mid~r的值），把区间加操作也按照权值两边下放，每次询问完答案要撤销之前的区间加操作

这题学了新姿势：树状数组区间修改+区间查询
有篇介绍树状数组的blog：http://www.voidcn.com/article/p-tzoagqlk-bkz.html

树状数组区间修改的大致思想是将序列查分，区间加减就变成单点修改，询问 (l,r) 区间和的时候求 sum(r)?sum(l?1)
设原序列是 a ，查分序列是 b ，得

code：

#include<set>
#include<map>
#include<deque>
#include<queue>
#include<stack>
#include<cmath>
#include<ctime>
#include<bitset>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<complex>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 110000
using namespace std;

const int maxn = 110000;
struct node
{
    int l,r,s,id;
    ll c;
    node(){}
    node(int a1,int a2,ll a3,int a4,int a5){l=a1;r=a2;c=a3;s=a4;id=a5;}
}a[maxn],b[maxn],c[maxn]; int num;
ll s[maxn],si[maxn];
int ans[maxn];
int n,m;

int lowbit(int x){return x&(-x);}
void update(ll *tr,int x,ll c){while(x<=n){tr[x]+=c;x+=lowbit(x);}}
ll q(ll *tr,int x){ll ret=0;while(x>0){ret+=tr[x];x-=lowbit(x);}return ret;}
void add(int l,int r,ll c)
{
    update(s,l,c);update(s,r+1,-c);
    update(si,l*c);update(si,(r+1)*-c);
}
ll query(int l,int r)
{
    ll r1=(q(s,r)*(ll)(r+1)-q(si,r));
    ll r2=(q(s,l-1)*(ll)l-q(si,l-1));
    return r1-r2;
}
void solve(int lp,int rp,int lc,int rc)
{
    if(lp>rp)return ;
    if(lc==rc)
    {
        for(int i=lp;i<=rp;i++)if(a[i].s==1)ans[a[i].id]=lc;
        return ;
    }
    int mid=(lc+rc)>>1; int bn=0,cn=0;
    for(int i=lp;i<=rp;i++)
    {
        if(a[i].s==0)
        {
            if(a[i].c>mid) {add(a[i].l,a[i].r,1);c[++cn]=a[i];}
            else b[++bn]=a[i];
        }
        else
        {
            ll temp=query(a[i].l,a[i].r);
            if(temp>=a[i].c)c[++cn]=a[i];
            else {b[++bn]=a[i];b[bn].c-=temp;}
        }
    }
    for(int i=lp;i<=rp;i++)
        if(a[i].s==0&&a[i].c>mid) add(a[i].l,-1);

    for(int i=1;i<=bn;i++)a[lp+i-1]=b[i];
    for(int i=1;i<=cn;i++)a[lp+bn+i-1]=c[i];
    solve(lp,lp+bn-1,lc,mid);
    solve(lp+bn,rp,mid+1,rc);
}

int main()
{
    scanf("%d%d",&n,&m); num=0;
    for(int i=1;i<=m;i++)
    {
        int x,r;ll c;
        scanf("%d",&x);
        if(x==1)
        {
            scanf("%d%d%lld",&l,&r,&c);
            a[++num]=node(l,c,0,0);
        }
        else
        {
            scanf("%d%d%lld",1,i);
        }
    }
    for(int i=1;i<=m;i++)ans[i]=-inf-1;
    solve(1,num,-inf,inf);
    for(int i=1;i<=m;i++)if(ans[i]!=-inf-1)printf("%dn",ans[i]);

    return 0;
}