记录编号	372037	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2013] K大数查询	最终得分	100
用户昵称	哒哒哒哒哒！	是否通过	通过
代码语言	C++	运行时间	5.367 s
提交时间	2017-02-17 16:21:21	内存使用	477.20 MiB

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
#define ll long long 
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*10+ch-48,ch=getchar();
	return x*f;
}
const int maxn=50005*2;
int n,m,N,cnt,root[maxn*250],lazy[maxn*250];
int sum[maxn*250],lc[maxn*250],rc[maxn*250];
void insert(int &rt,int l,int r,int a,int b){
	if(!rt) rt=++cnt;
	if(a<=l&&b>=r){sum[rt]+=(r-l+1);lazy[rt]++;return;}
	int mid=(l+r)/2;
	if(a<=mid) insert(lc[rt],l,mid,a,b);
	if(b>mid) insert(rc[rt],mid+1,r,a,b);
	sum[rt]=sum[lc[rt]]+sum[rc[rt]]+(r-l+1)*lazy[rt];
}
void insert(int rt,int l,int r,int p,int a,int b){
	insert(root[rt],1,N,a,b);
	if(l==r) return;int mid=(l+r)/2;
	if(p<=mid) insert(rt*2,l,mid,p,a,b);
	else insert(rt*2+1,mid+1,r,p,a,b);
}
int query(int rt,int l,int r,int a,int b){
	if(a<=l&&b>=r) return sum[rt];
	int mid=(l+r)/2,res=0;
	if(lazy[rt])
		res+=(min(r,b)-max(l,a)+1)*lazy[rt];
	if(a<=mid) res+=query(lc[rt],l,mid,a,b);
	if(b>mid) res+=query(rc[rt],mid+1,r,a,b);
	return res;
}
int query(int rt,int l,int r,int a,int b,int k){
	if(l==r) return l;
	int mid=(l+r)/2,c=query(root[rt*2+1],1,N,a,b);
	if(c>=k) return query(rt*2+1,mid+1,r,a,b,k);
	else return query(rt*2,l,mid,a,b,k-c);
}
int main(){
	freopen("zjoi13_sequence.in","r",stdin);freopen("zjoi13_sequence.out","w",stdout);
	n=read(),m=read(),N=2*n+1;
	while(m--){
		int op=read(),a=read(),b=read(),c=read();
		if(op==1) insert(1,1,N,c+n+1,a,b);
		else printf("%d\n",query(1,1,N,a,b,c)-n-1);
	}
	fclose(stdin);fclose(stdout);
	return 0;
}