再次求助
查看原帖
再次求助
115668
y0y68楼主2020/9/4 12:55

请问最后一点如何卡过,大佬救救孩子

#pragma GCC optimize(1)
#pragma G++ optimize(1)
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#pragma GCC optimize(3)
#pragma G++ optimize(3)
#pragma GCC optimize(4)
#pragma G++ optimize(4)
#pragma GCC optimize(5)
#pragma G++ optimize(5)
#pragma GCC optimize(6)
#pragma G++ optimize(6)
#pragma GCC optimize(7)
#pragma G++ optimize(7)
#pragma GCC optimize(8)
#pragma G++ optimize(8)
#pragma GCC optimize(9)
#pragma G++ optimize(9)
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define re register
#define int long long
using namespace std;
const int N=1e6+5;
const int INF=1e18;
bool anc[N];
int n,m,size,a[N],f[N],s[N],e[N],mn[N],mx[N],tag[N];
inline int min(int x,int y){
	return x<y?x:y;
}
inline int max(int x,int y){
	return x>y?x:y;
}
void in(int &x){
	char c;x=0;int tmp=1;
	for(c=getchar();c<'0'||c>'9';c=getchar())if(c=='-')tmp=-1;
	for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);
	x*=tmp;
}
void reset(int x){
	re int top=e[x];
	for(re int i=s[x];i<=top;++i)
		a[i]+=tag[x];
	tag[x]=0,anc[x]=false;
	mx[x]=INF,mn[x]=-INF;
	for(re int i=s[x];i<top;++i)
		if(a[i]>a[i+1]){anc[x]=true;break;}
	for(re int i=s[x];i<=top;++i){
		mn[x]=min(mn[x],a[i]);
		mx[x]=max(mx[x],a[i]);
	}
}
void update(int l,int r,int x){
	if(f[l]==f[r]){
		for(re int i=l;i<=r;++i)a[i]+=x;
	}
	else{
	    re int top=e[f[l]];
		for(re int i=l;i<=top;++i)a[i]+=x;
		for(re int i=s[f[r]];i<=r;++i)a[i]+=x;
		top=f[r];
		for(re int i=f[l]+1;i<top;++i)tag[i]+=x;
	}
}
bool query(int l,int r){
	if(f[l]==f[r]){
		reset(f[l]);
		for(re int i=l;i<r;++i)
			if(a[i]>a[i+1])return false;
	}
	else{
		reset(f[l]);reset(f[r]);
		re int tt=f[r],ttt=f[l];
		for(re int i=ttt;i<tt;++i)
			if(anc[i])return false;
		tt--;
		for(re int i=ttt+1;i<tt;++i)
			if(mx[i]>mn[i+1])return false;
		re int top=e[ttt];
		re int tmx=a[top];
		for(re int i=l;i<top;++i){
			tmx=max(tmx,a[i]);
			if(a[i]>a[i+1])return false;
		}
		if(tmx>mn[ttt+1])return false;
		re int tmn=a[r];
		for(re int i=s[tt];i<r;++i){
			tmn=min(tmn,a[i]);
			if(a[i]>a[i+1])return false;
		}
		if(mx[tt-1]>tmn)return false;
	}
	return true;
}
signed main(){
	in(n),in(m),size=sqrt(n);
	for(re int i=1;i<=n;++i)in(a[i]);
	for(re int i=1;i<=n;++i)
		f[i]=(i-1)/size+1,e[f[i]]=i;
	for(re int i=n;i>=1;i--)
		s[f[i]]=i;
	for(re int i=1;i<=f[n];++i){
		int top=e[i];
		mn[i]=mx[i]=a[top];
		for(re int j=s[i];j<top;++j){
			mn[i]=min(mn[i],a[j]);
			mx[i]=max(mx[i],a[j]);
			if(a[j]>a[j+1])anc[i]=true;
		}
	}
	while(m--){
		re int opt;in(opt);
		if(opt&1){
			int l,r,x;
			in(l),in(r),in(x);
			update(l,r,x);
		}
		else{
			re int l,r;in(l),in(r);
			puts(query(l,r)?"Yes":"No");
		}
	}
	return 0;
}
2020/9/4 12:55
加载中...