记录编号	366187	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2013] K大数查询	最终得分	100
用户昵称	Cydiater	是否通过	通过
代码语言	C++	运行时间	2.825 s
提交时间	2017-01-23 09:35:20	内存使用	211.55 MiB

//BZOJ 3110
//by Cydiater
//2017.1.23
#include <iostream>
#include <ctime>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <iomanip>
#include <bitset>
#include <set>
#include <vector>
using namespace std;
#define ll long long
#define up(i,j,n)	for(int i=j;i<=n;i++)
#define down(i,j,n)	for(int i=j;i>=n;i--)
#define cmax(a,b)	a=max(a,b)
#define cmin(a,b)	a=min(a,b)
#define FILE		"zjoi13_sequence"
const int MAXN=7e4+5;
const int oo=0x3f3f3f3f;
inline int read(){
	char ch=getchar();int x=0,f=1;
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;	
}
int num[MAXN],top,N,M,ans,cnt=0,pre[MAXN][2],Top,ID=0;
struct SegTree{
	int tag,which;
}t[MAXN<<2];
struct Query{
	int opt,a,b,c;
}query[MAXN];
struct Tree{
	int son[2],sum;
}tree[MAXN<<8];
struct ValSeg{
	int ROOT;
	void Insert(int leftt,int rightt,int &root,int val,int pos){
		if(!root)root=++cnt;
		if(leftt==rightt){
			tree[root].sum+=val;
			return;
		}
		int mid=(leftt+rightt)>>1;
		if(pos<=mid)	Insert(leftt,mid,tree[root].son[0],val,pos);
		else		Insert(mid+1,rightt,tree[root].son[1],val,pos);
		tree[root].sum=tree[tree[root].son[0]].sum+tree[tree[root].son[1]].sum;
	}
}T[MAXN<<3];
namespace solution{
	void Build(int leftt,int rightt,int root){
		t[root].which=++ID;t[root].tag=++ID;
		if(leftt==rightt)return;
		int mid=(leftt+rightt)>>1;
		Build(leftt,mid,root<<1);
		Build(mid+1,rightt,root<<1|1);
	}
	void Prepare(){
		N=read();M=read();
		up(i,1,M){
			int opt=read(),a=read(),b=read(),c=read();
			query[i]=(Query){opt,a,b,c};
			if(opt==1)num[++top]=c;
		}
		sort(num+1,num+top+1);
		top=unique(num+1,num+top+1)-(num+1);
		Build(1,N,1);
		up(i,1,M)if(query[i].opt==1)query[i].c=lower_bound(num+1,num+top+1,query[i].c)-num;
	}
	void ADD(int leftt,int rightt,int root,int L,int R,int Pos){
		if(leftt>=L&&rightt<=R){
			T[t[root].tag].Insert(1,top,T[t[root].tag].ROOT,1,Pos);
			return;
		}
		int mid=(leftt+rightt)>>1;
		T[t[root].which].Insert(1,top,T[t[root].which].ROOT,min(R,rightt)-max(L,leftt)+1,Pos);
		if(R<=mid)		ADD(leftt,mid,root<<1,L,R,Pos);
		else if(L>=mid+1)	ADD(mid+1,rightt,root<<1|1,L,R,Pos);
		else{
			ADD(leftt,mid,root<<1,L,R,Pos);
			ADD(mid+1,rightt,root<<1|1,L,R,Pos);
		}
	}
	void PushTree(int leftt,int rightt,int root,int L,int R){
		if(leftt>=L&&rightt<=R){
			pre[++Top][0]=T[t[root].which].ROOT;
			pre[Top][1]=1;
			pre[++Top][0]=T[t[root].tag].ROOT;
			pre[Top][1]=rightt-leftt+1;
			return;
		}
		int mid=(leftt+rightt)>>1;
		pre[++Top][0]=T[t[root].tag].ROOT;
		pre[Top][1]=min(R,rightt)-max(L,leftt)+1;
		if(R<=mid)		PushTree(leftt,mid,root<<1,L,R);
		else if(L>=mid+1)	PushTree(mid+1,rightt,root<<1|1,L,R);
		else{
			PushTree(leftt,mid,root<<1,L,R);
			PushTree(mid+1,rightt,root<<1|1,L,R);
		}
	}
	int GetK(int leftt,int rightt,int rnk){
		if(leftt==rightt){
			int sum=0;
			up(i,1,Top)sum+=tree[pre[i][0]].sum*pre[i][1];
			if(rnk<=sum)	return leftt;
			else 		return -1;
		}
		int sum=0,mid=(leftt+rightt)>>1;
		up(i,1,Top)sum+=tree[tree[pre[i][0]].son[1]].sum*pre[i][1];
		if(rnk<=sum){
			up(i,1,Top)pre[i][0]=tree[pre[i][0]].son[1];
			return GetK(mid+1,rightt,rnk);
		}else{
			up(i,1,Top)pre[i][0]=tree[pre[i][0]].son[0];
			return GetK(leftt,mid,rnk-sum);
		}
	}
	void Solve(){
		up(i,1,M){
			//ans&=(1<<8)-1;
			int opt=query[i].opt,L=query[i].a,R=query[i].b,K=query[i].c;
			//L^=ans;R^=ans;cmax(L,1);cmax(R,1);
			if(L>R)swap(L,R);
			if(opt==1)	ADD(1,N,1,L,R,K);
			else{
				Top=0;
				PushTree(1,N,1,L,R);
				printf("%d\n",num[GetK(1,top,K)]);
			}
		}
	}
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	//freopen("input.in","r",stdin);
	//freopen("out.out","w",stdout);
	using namespace solution;
	Prepare();
	Solve();
	return 0;
}