小A终于通过了保安的考验，来到了古墓门前，古墓门前有n根柱子，第i根柱子的高度是整数。古墓的门上会弹出一些暗号，机智小A猜到这个暗号表示询问第l到第r根柱子的高度在升序排序后是否构成一段连续且上升的序列。并且这些柱子的高度还可能在弹出暗号的过程中出现变化。
现在小A需要回答出每个暗号的答案
5 5
1 2 3 4 5
2 1 5
2 2 3
2 3 3
1 3 6
2 3 5
Yes
Yes
Yes
Yes
Solution：
一开始想到的是最朴素的做法，用线段树维护区间和及最值，然后主席树维护区间内数的个数，但显然空间不够。
再仔细想了想看看能不能从区间和入手，使得不同的数产生的区间和唯一，这就是费马大定理了：
当整数
时，关于
的方程
没有正整数解。
#pragma GCC optimite(3) #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; const int N = 500010; int a[N]; struct Seg { int l,r,lx,rx; ull sum; }t[N<<2]; inline void pushup(int p) { t[p].sum=t[p*2].sum+t[p*2+1].sum; t[p].lx=min(t[p<<1].lx,t[p<<1|1].lx); t[p].rx=max(t[p<<1].rx,t[p<<1|1].rx); } void update(int p,int x,int val) { if(t[p].l==t[p].r) { t[p].lx=t[p].rx=val; t[p].sum=(ull)val*val*val; return; } int mid=(t[p].l+t[p].r)/2; if(x<=mid) update(p<<1,x,val); else update(p<<1|1,x,val); pushup(p); } void build(int p,int l,int r) { t[p].l=l,t[p].r=r; if(l==r) { t[p].lx=t[p].rx=a[l]; t[p].sum=(ull)a[l]*a[l]*a[l]; return; } int mid=(l+r)/2; build(p*2,l,mid); build(p*2+1,mid+1,r); pushup(p); } ull query(int p,int l,int r) { if(l<=t[p].l&&r>=t[p].r) return t[p].sum; int mid=(t[p].l+t[p].r)/2; ull val=0; if(l<=mid) val+=query(p*2,l,r); if(r>mid) val+=query(p*2+1,l,r); return val; } int ask1(int p,int l,int r) { if(l<=t[p].l&&r>=t[p].r) return t[p].rx; int mid=(t[p].l+t[p].r)/2; int ans=-1; if(l<=mid) ans=max(ans,ask1(p<<1,l,r)); if(r>mid) ans=max(ans,ask1(p<<1|1,l,r)); return ans; } int ask2(int p,int l,int r) { if(l<=t[p].l&&r>=t[p].r) return t[p].lx; int mid=(t[p].l+t[p].r)/2; int ans=1e9+7; if(l<=mid) ans=min(ans,ask2(p<<1,l,r)); if(r>mid) ans=min(ans,ask2(p<<1|1,l,r)); return ans; } int main() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); #endif ios::sync_with_stdio(false); cin.tie(0); int n,m,op,x,y; cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; build(1,1,n); while(m--) { cin>>op>>x>>y; if(op==1) update(1,x,y); else { ull l=ask2(1,x,y),r=ask1(1,x,y); ull tmp=(ull)(r*(r+1)/2+l*(l-1)/2)*(r*(r+1)/2-l*(l-1)/2); if(query(1,x,y)==tmp) cout<<"Yes"<<endl; else cout<<"No"<<endl; } } return 0; }
原文：https://www.cnblogs.com/Suiyue-Li/p/11586705.html
