小A盗墓
时间限制: 5 Sec 内存限制: 128 MB题目描述
小A终于通过了保安的考验,来到了古墓门前,古墓门前有n根柱子,第i根柱子的高度是整数。古墓的门上会弹出一些暗号,机智小A猜到这个暗号表示询问第l到第r根柱子的高度在升序排序后是否构成一段连续且上升的序列。并且这些柱子的高度还可能在弹出暗号的过程中出现变化。现在小A需要回答出每个暗号的答案
输入
第一行两个整数,表示柱子的个数n以及操作的个数m。第二行n个整数,第i个整数表示第i根柱子的高度。
接下来m行,每行三个整数opt, x, y。当opt=1时,表示把第x根柱子的高度改为y;当opt=2时,表示询问第x到第y根柱子的高度在升序排序后是否构成一段连续且上升的序列。若是,则输出Yes,否则输出No。
输出
对于每个询问输出一行Yes或No。
样例输入
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; }View Code