记录编号	274075	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2013] K大数查询	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	0.845 s
提交时间	2016-06-26 16:46:09	内存使用	3.56 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=50010;
struct Node{
	int tp,l,r,k,id,tmp;
}p[maxn],tmp[maxn];

int b0[maxn],b1[maxn];
int v0[maxn],v1[maxn];
int ans[maxn],n,Q,tim,cntQ;

void Add0(int x,int d){
	while(x<=n){
		b0[x]=v0[x]==tim?b0[x]+d:d;
		v0[x]=tim;
		x+=x&(-x);
	}
}

void Add1(int x,int d){
	while(x<=n){
		b1[x]=v1[x]==tim?b1[x]+d:d;
		v1[x]=tim;
		x+=x&(-x);
	}
}

void Update(int l,int r,int d){
	Add0(l,d);
	Add0(r+1,-d);
	Add1(l,-(l-1)*d);
	Add1(r+1,r*d);
}

int Query(int x){
	int ret=0;
	for(int i=x;i;i-=i&(-i))
		ret+=v0[i]==tim?b0[i]:0;
	ret*=x;
	for(int i=x;i;i-=i&(-i))
		ret+=v1[i]==tim?b1[i]:0;
	return ret;	
}

int Que(int l,int r){
	return Query(r)-Query(l-1);
} 

void Solve(int h,int t,int l,int r){
	if(h>t)return;
	if(l==r){
		for(int i=h;i<=t;i++)
			ans[p[i].id]=l;
		return;	
	}
	int mid=(l+r)>>1;
	int ct1=h,ct2=h;++tim;
	for(int i=h;i<=t;i++){
		if(p[i].tp==1){
			if(p[i].k>mid)continue;
			Update(p[i].l,p[i].r,1);
			ct2+=1;
		}
		else{
			p[i].tmp=Que(p[i].l,p[i].r);
			if(p[i].tmp>=p[i].k)ct2+=1;
		}
	}
	for(int i=h;i<=t;i++){
		if(p[i].tp==1){
			if(p[i].k>mid)tmp[ct2++]=p[i];
			else tmp[ct1++]=p[i];
		}
		else{
			if(p[i].tmp>=p[i].k)tmp[ct1++]=p[i];
			else p[i].k-=p[i].tmp,tmp[ct2++]=p[i];
		}
	}
	for(int i=h;i<=t;i++)p[i]=tmp[i];
	Solve(h,ct1-1,l,mid);Solve(ct1,t,mid+1,r);
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("zjoi13_sequence.in","r",stdin);
	freopen("zjoi13_sequence.out","w",stdout);
#endif
	scanf("%d%d",&n,&Q);
	for(int i=1;i<=Q;i++){
		scanf("%d%d",&p[i].tp,&p[i].l);
		scanf("%d%d",&p[i].r,&p[i].k);
		if(p[i].tp==2){
			p[i].id=++cntQ;
			p[i].k=Que(p[i].l,p[i].r)-p[i].k+1;
		}
		else
			Update(p[i].l,p[i].r,1);
	}
	
	Solve(1,Q,1,n);
	
	for(int i=1;i<=cntQ;i++)
		printf("%d\n",ans[i]);
	return 0;
}