16tps 蒟蒻求助

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+3,inf=1e9+3;
int T,n,m,p[maxn];
inline int read(){
	int res=0;
	char c;c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9'){
		res=res*10+c-'0';
		c=getchar();
	}
	return res;
}
struct node{
	int desmax,desmin,res,pmax,lazy;
}t[maxn<<2];
void pushup(int u){
	t[u].res=min(t[u<<1].res,t[u<<1|1].res);
	t[u].desmax=max(t[u<<1].desmax,t[u<<1|1].desmax);
	t[u].desmin=min(t[u<<1].desmin,t[u<<1|1].desmin);
	t[u].pmax=max(t[u<<1].pmax,t[u<<1|1].pmax);
}
void pushdown(int u){
	if(t[u].lazy){
		int k=t[u].lazy;t[u].lazy=0;
		t[u<<1].lazy=max(t[u<<1].lazy,k),t[u<<1|1].lazy=max(t[u<<1|1].lazy,k);
		if(k>t[u<<1].desmax){
			t[u<<1].desmin=t[u<<1].desmax=k;
			t[u<<1].res=p[k]-t[u<<1].pmax;
		}
		if(k>t[u<<1|1].desmax){
			t[u<<1|1].desmin=t[u<<1|1].desmax=k;
			t[u<<1|1].res=p[k]-t[u<<1|1].pmax;
		}
	}
}
void build(int u,int l,int r){
	t[u].lazy=0;
	if(l==r){
		t[u].desmax=t[u].desmin=l+1;t[u].pmax=p[l];t[u].res=p[l+1]-p[l];
		return;
	}
	int mid=l+r>>1;
	build(u<<1,l,mid);build(u<<1|1,mid+1,r);
	pushup(u);
}
void change(int u,int l,int r,int x,int y,int v){
	if(l>=x&&r<=y){
		if(v>t[u].desmax){
			t[u].desmin=t[u].desmax=v;
			t[u].res=p[v]-t[u].pmax;
		}
		t[u].lazy=max(t[u].lazy,v);
		return;
	}
	pushdown(u);
	int mid=l+r>>1;
	if(x<=mid)change(u<<1,l,mid,x,y,v);
	if(y>mid)change(u<<1|1,mid+1,r,x,y,v);
	pushup(u);
}
int find(int u,int l,int r,int x,int y,int border){
	if(l>y||r<x)return inf;
	if(l>=x&&r<=y){
		if(t[u].desmax<=border){
			return p[border]-t[u].pmax;
		}
		if(t[u].desmin<border){
			pushdown(u);
			int mid=l+r>>1;
			return min(find(u<<1,l,mid,x,y,border),find(u<<1|1,mid+1,r,x,y,border));
		}
		return t[u].res;
	}
	pushdown(u);
	int mid=l+r>>1,res=inf;
	if(x<=mid)res=min(res,find(u<<1,l,mid,x,y,border));
	if(y>mid)res=min(res,find(u<<1|1,mid+1,r,x,y,border));
	return res;
}
int main(){
	T=read();
	while(T--){
		n=read();m=read();
		for(int i=1;i<=n;i++){
			p[i]=read();
		}
		p[n+1]=inf+p[n];
		build(1,1,n);
		for(int i=1;i<=m;i++){
			int c,x,y;
			c=read();x=read();y=read();
			if(c==1){
				change(1,1,n,x,y,y+1);
			}
			else{
				if(x>=y){
					if(x==y)cout<<0<<endl;
					else cout<<-1<<endl;
					continue;
				}
				int ans=find(1,1,n,1,x,y);
				if(ans==inf)cout<<-1<<endl;
				else cout<<ans<<endl;
			}
		}
	}
	return 0;
}