记录编号	262639	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]聪聪的世界	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	27.124 s
提交时间	2016-05-21 11:21:43	内存使用	126.18 MiB

#include<cstdio>
#include<algorithm>

#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define maxn 1000010

using namespace std;

typedef long long ll;
int n,m,inv[maxn],L[maxn<<2],R[maxn<<2];
ll mn[maxn<<2],mx[maxn<<2],mark[maxn<<2];

int read()
{
	int ret=0;char ch=getchar();
	while(ch<'!') ch=getchar();
	while(ch>'!') ret=ret*10+ch-'0',ch=getchar();
	return ret;
}

void update(int x)
{
	mn[x]=min(mn[L(x)],mn[R(x)]);
	mx[x]=max(mx[L(x)],mx[R(x)]);
	return;
}

void pushdown(int x)
{
	if(mark[x]){
		mark[L(x)]+=mark[x];
		mark[R(x)]+=mark[x];
		mn[L(x)]+=mark[x];
		mn[R(x)]+=mark[x];
		mx[L(x)]+=mark[x];
		mx[R(x)]+=mark[x];
		mark[x]=0;
	}
	return;
}

void build(int l,int r,int x)
{
	L[x]=l,R[x]=r;
	if(l==r){
		inv[l]=x;
		mn[x]=mx[x]=read();
		return ;
	}
	int mid=l+r>>1;
	build(l,mid,L(x));
	build(mid+1,r,R(x));
	update(x);
}

void modify(int pos,ll val,int l,int r,int x)
{
	if(l==r){
		mx[x]=mn[x]=val;
		return;
	}
	pushdown(x);
	int mid=l+r>>1;
	if(pos<=mid) modify(pos,val,l,mid,L(x));
	else modify(pos,val,mid+1,r,R(x));
	update(x);
}

void modify(int al,int ar,int val,int l,int r,int x)
{
	if(al<=l&&r<=ar){
		mn[x]+=val;
		mx[x]+=val;
		mark[x]+=val;
		return;
	}
	pushdown(x);
	int mid=l+r>>1;
	if(al<=mid) modify(al,ar,val,l,mid,L(x));
	if(ar>mid) modify(al,ar,val,mid+1,r,R(x));
	update(x);
}

ll ask(int pos,int l,int r,int x)
{
	if(l==r) return mn[x];
	pushdown(x);
	int mid=l+r>>1;ll ans;
	if(pos<=mid) ans=ask(pos,l,mid,L(x));
	else ans=ask(pos,mid+1,r,R(x));
	update(x);
	return ans;
}

bool cmp(ll x,ll y,int cmd)
{
	if(cmd==1) return x<y;
	else return x>y;
}

ll cal(int x,int cmd)
{
	if(cmd==1) return mn[x];
	return mx[x];
}

ll gol(int l,int r,int x,ll val,int cmd)
{
	if(l==r) return mn[x];
	pushdown(x);
	int mid=l+r>>1;ll ans;
	if(cmp(cal(R(x),cmd),val,cmd)) ans=gol(mid+1,r,R(x),val,cmd);
	else ans=gol(l,mid,L(x),val,cmd);
	update(x);
	return ans;
}

ll findl(int x,int cmd)
{
	ll val=ask(x,1,n,1);
	x=inv[x];
	do{
		if(x&1){
			int t=x-1;
			if(cmp(cal(t,cmd),val,cmd)) return gol(L[t],R[t],t,val,cmd);
		}
		x>>=1;
	}while(x!=1);
	return -1;
}

ll gor(int l,int r,int x,ll val,int cmd)
{
	if(l==r) return mn[x];
	pushdown(x);
	int mid=l+r>>1;ll ans;
	if(cmp(cal(L(x),cmd),val,cmd)) ans=gor(l,mid,L(x),val,cmd);
	else ans=gor(mid+1,r,R(x),val,cmd);
	update(x);
	return ans;
}

ll findr(int x,int cmd)
{
	ll val=ask(x,1,n,1);
	x=inv[x];
	do{
		if(!(x&1)){
			int t=x+1;
			if(cmp(cal(t,cmd),val,cmd)) return gor(L[t],R[t],t,val,cmd);
		}
		x>>=1;
	}while(x!=1);
	return -1;
}

int main()
{
	freopen("ccsworld.in","r",stdin);
	freopen("ccsworld.out","w",stdout);
	n=read(),m=read();
	build(1,n,1);
	for(int i=1;i<=m;i++){
		int cmd=read();
		if(cmd==1){
			int x=read();
			printf("%lld\n",findl(x,1));
		}
		if(cmd==2){
			int x=read();
			printf("%lld\n",findl(x,2));
		}
		if(cmd==3){
			int x=read();
			printf("%lld\n",findr(x,1));
		}
		if(cmd==4){
			int x=read();
			printf("%lld\n",findr(x,2));
		}
		if(cmd==5){
			int x=read(),y=read();
			ll t1=ask(x,1,n,1);
			ll t2=ask(y,1,n,1);
			modify(x,t2,1,n,1);
			modify(y,t1,1,n,1);
		}
		if(cmd==6){
			int x=read(),y=read(),w=read();
			modify(x,y,w,1,n,1);
		}
		if(cmd==7){
			int x=read(),y=read(),w=read();
			modify(x,y,-w,1,n,1);
		}
	}
	return 0;
}