【差分主席树】zjoi2013 k大数

这道题的解法挺多，值域线段树套区间线段树，区间线段树套值域线段树（目前想到的是zkw的标记永久化），cdq分治

相对好写一点的就是维护差分主席树，每个位置维护与前一个位置的数集差分，修改就可以看做是单点修改，然后再反推前缀和http://blog.csdn.net/huyuncong/article/details/6440979

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
const long long oo=1LL<<50;
using namespace std;
int l[2][5000000],st[2][5000000][2],r[2][5000000];
long long sum[2][5000000];
int ss[2],n,m,root[2][5000000];
int ori(int e)
{
    ++ss[e];
    l[e][ss[e]]=r[e][ss[e]]=sum[e][ss[e]]=0;
    return ss[e];
}
void change(int e,int x,long long L,long long R,long long c,int w) 
{
    if (L==R) {
        sum[e][x]+=w;
        return ;
    }
    long long mid=(L+R)>>1;
    if (c<=mid) {
        if (!l[e][x]) l[e][x]=ori(e);
        change(e,l[e][x],L,mid,c,w);
    }
    else {
        if (!r[e][x]) r[e][x]=ori(e);
        change(e,r[e][x],mid+1,R,w);
    }
    sum[e][x]=sum[e][l[e][x]]+sum[e][r[e][x]];
}
void origin()
{
    ss[0]=ss[1]=0;
    for (int i=1;i<=n;i++)
        root[0][i]=ori(0),root[1][i]=ori(1);
}
int lowbit(int x)
{
    return x & -x;
}
void modify(int x,int c,int w)
{
		int X=x;
    for (;x<=n;x+=lowbit(x))
        change(0,root[0][x],1,oo+oo,oo+c,1*w),change(1,root[1][x],X*w);
}
long long ask(int e,int t,int k)
{
    long long Sum=0;
    for (int i=1;i<=t;i++)
    	Sum+=sum[k][r[k][st[e][i][k]]];
    return Sum;
}
void Lstep(int e,int t)
{
	for (int i=1;i<=t;i++) 
		for (int k=0;k<=1;k++)
			st[e][i][k]=l[k][st[e][i][k]];
}
void Rstep(int e,int t)
{
	for (int i=1;i<=t;i++) 
		for (int k=0;k<=1;k++)
			st[e][i][k]=r[k][st[e][i][k]];
}
long long query(int l,int r,int k)
{
    int t[2]={0,0};
    for (int x=l-1;x;x-=lowbit(x))
        st[0][++t[0]][0]=root[0][x],st[0][t[0]][1]=root[1][x];
    for (int x=r;x;x-=lowbit(x))
        st[1][++t[1]][0]=root[0][x],st[1][t[1]][1]=root[1][x];
	long long L=1,R=oo+oo;
    for (;L!=R;) {
    		long long mid=(L+R)>>1;
    		long long sum1=(l-1+1)*ask(0,t[0],0)-ask(0,1);
    		long long sum2=(r+1)*ask(1,t[1],0)-ask(1,1);
        long long sum=sum2-sum1;
        //cout<<mid-oo<<' '<<sum<<endl;
        //cout<<"zz "<<ask(0,t)<<' '<<ask(1,t)<<endl;
        if (sum>=k) {
            L=mid+1;
            Rstep(0,t[0]);
            Rstep(1,t[1]);
        }
        else {
            R=mid;
            k-=sum;
            Lstep(0,t[0]);
            Lstep(1,t[1]);
        }
    }
    return L;
}
int main()
{
	freopen("input.txt","r",stdin);
    scanf("%d%d",&n,&m);
    origin();
    for (int i=1;i<=m;i++) {
        int c;
        scanf("%d",&c);
        if (1==c) {
            int l,r,c;
            scanf("%d%d%d",&l,&r,&c);
            modify(l,1);
            modify(r+1,-1);
        }
        else {
            int l,k;
            scanf("%d%d%d",&k);
            long long ans=query(l,k);
            printf("%dn",(int)(ans-oo));
        }
    }
    return 0;
}