记录编号	543909	评测结果	WWWWWWWWWW
题目名称	[ZJOI 2013] K大数查询	最终得分	0
用户昵称	Marvolo	是否通过	未通过
代码语言	C++	运行时间	1.901 s
提交时间	2019-10-11 15:00:10	内存使用	33.12 MiB

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define N 100010
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;

int n,m,i,tot;
int Ans[N];

struct Data{
	int op,l,r,id;
	LL k;
}a[N],p1[N],p2[N];

struct Tree{
	int x,l,r;
	LL d,p;
}t[N*4];

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline LL read(){
	LL f=1,p=0;	char	c=getchar();
	while (c<48||c>57)	{if (c=='-')	f=-1;	c=getchar();}
	while (c>=48&&c<=57)	p=(p<<1)+(p<<3)+c-48,c=getchar();
	return p*f;
}

inline void Maketree(int x,int low,int high){
	int mid=(low+high)>>1;
	t[x].l=low;	t[x].r=high;
	if (low==high)	return;
	Maketree(l(x),low,mid);	Maketree(r(x),mid+1,high);
}

inline void Push(int x){
	LL p=t[x].p;
	t[l(x)].p+=p;	t[r(x)].p+=p;
	t[l(x)].d+=(LL)(t[l(x)].r-t[l(x)].l+1)*p;
	t[r(x)].d+=(LL)(t[r(x)].r-t[r(x)].l+1)*p;
	t[x].p=0;
}

inline void Add(int x,int low,int high,int val){
	int mid=(t[x].l+t[x].r)>>1;
	if (t[x].l==low&&t[x].r==high){
		t[x].d+=(LL)val*(t[x].r-t[x].l+1);	t[x].p+=val;
		return;
	}
	if (t[x].p)	Push(x);
	if (high<=mid)	Add(l(x),low,high,val);
	else if (low>mid)	Add(r(x),low,high,val);
	else Add(l(x),low,mid,val),Add(r(x),mid+1,high,val);
	t[x].d=t[l(x)].d+t[r(x)].d;
}

inline LL Query(int x,int low,int high){
	int mid=(t[x].l+t[x].r)>>1;
	if (t[x].l==low&&t[x].r==high)	return t[x].d;
	if (t[x].p)	Push(x);
	if (high<=mid)	return Query(l(x),low,high);
	else if (low>mid)	return Query(r(x),low,high);
	else return Query(l(x),low,mid)+Query(r(x),mid+1,high);
}

inline void Solve(int l,int r,int L,int R){
	int i=0,s=0,u=0,mid=(L+R)>>1;
	LL sum=0;
	if (r<l||R<L)	return;
	if (L==R){
		for (i=l;i<=r;i++)
			if (a[i].op==2)	Ans[a[i].id]=L;
		return;
	}
	for (i=l;i<=r;i++){
		if (a[i].op==1){
			if (a[i].k<=mid)	p1[++s]=a[i];
			else Add(1,a[i].l,a[i].r,1),p2[++u]=a[i];
		}	else {
			sum=Query(1,a[i].l,a[i].r);
			if (sum>=a[i].k)	p2[++u]=a[i];
			else a[i].k-=sum,p1[++s]=a[i];
		}
	}
	for (i=1;i<=u;i++)
		if (p2[i].op==1)	Add(1,a[i].l,a[i].r,-1);
	for (i=1;i<=s;i++)	a[l+i-1]=p1[i];
	for (i=1;i<=u;i++)	a[l+s+i-1]=p2[i];
	Solve(l,l+s-1,L,mid);
	Solve(l+s,l+s+u-1,mid+1,R);
}

int main(){
	freopen("zjoi13_sequence.in","r",stdin);
	freopen("zjoi13_sequence.out","w",stdout);
	n=read();	m=read();
	for (i=1;i<=m;i++){
		a[i].op=read();	a[i].l=read();
		a[i].r=read();	a[i].k=read();
		a[i].id=(a[i].op==2)?++tot:i;
	}
	Maketree(1,1,n);
	Solve(1,m,0,n);
	for (i=1;i<=tot;i++)	printf("%d\n",Ans[i]);
	return 0;
}