记录编号	147041	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2013] K大数查询	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	10.437 s
提交时间	2015-01-23 21:03:40	内存使用	306.25 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define Maxm 10000010
#define Maxn 50010
#define l(x) ch[x][0]
#define r(x) ch[x][1]
using namespace std;
int ch[Maxm<<1][2]={0};
int sumt[Maxm<<1]={0},tot=0,n,m,root[Maxn<<2]={0};
int lazt[Maxm<<1]={0};
void update1(int o,int l,int r){   //下传标记附带动态开点
    if(!lazt[o]||l==r) return; int mid=(l+r)>>1;
    if(!l(o)) l(o)=++tot; sumt[l(o)]+=lazt[o]*(mid-l+1);
    if(!r(o)) r(o)=++tot; sumt[r(o)]+=lazt[o]*(r-mid);
	lazt[l(o)]+=lazt[o]; lazt[r(o)]+=lazt[o]; lazt[o]=0;
}
void insert1(int &o,int l,int r,int ql,int qr){   //副线段树维护区间（动态）
    if(!o) o=++tot;
    update1(o,l,r);
    if(ql<=l&&r<=qr){lazt[o]++;sumt[o]+=(r-l+1);return;}
    int mid=(l+r)>>1;
    if(ql<=mid) insert1(l(o),l,mid,ql,qr);
    if(mid<qr) insert1(r(o),mid+1,r,ql,qr);
    sumt[o]=sumt[l(o)]+sumt[r(o)];
}
int query1(int &o,int l,int r,int ql,int qr){   //动态加点的query
	if(!o) return 0;
    update1(o,l,r);
    if(ql<=l&&r<=qr) return sumt[o];
    int mid=(l+r)>>1,res=0;
    if(ql<=mid) res+=query1(l(o),l,mid,ql,qr);
    if(mid<qr) res+=query1(r(o),mid+1,r,ql,qr);
    return res;
}
void insert2(int o,int l,int r,int qx,int qa,int qb){   //主线段树维护权值
    insert1(root[o],1,n,qa,qb);
    if(l==r) return; int mid=(l+r)>>1;
    if(qx<=mid) insert2(o<<1,l,mid,qx,qa,qb);
    else insert2(o<<1|1,mid+1,r,qx,qa,qb);
}
int query_all(int a,int b,int k){
    int L=1,R=n,now=1;    //二分答案求k大
    while(L!=R){
        int mid=(L+R)>>1,tmp=query1(root[now<<1],1,n,a,b);
        if(tmp>=k) R=mid,now<<=1;
        else L=mid+1,now=now<<1|1,k-=tmp;
    }
    return L;
}
int main(){
	freopen("zjoi13_sequence.in","r",stdin);
	freopen("zjoi13_sequence.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1,a,b,c,d;i<=m;i++){
		scanf("%d%d%d%d",&d,&a,&b,&c);
        if(d==1) insert2(1,1,n,n-c+1,a,b);
        else printf("%d\n",n-query_all(a,b,c)+1);
    }
    return 0;
}