给定一个序列 有三种操作:
:在区间
加上
.
: 查询区间
中的
.
:查询
.
根据 的性质,
,设
是
的差分数组,对于任意一个区间
由于
的性质,在区间
加上一个数
其实只对 有用所以只需要维护
数组就可以单点更新即可,求询问2刚好在差分数组上单点更新就可以.
#include<bits/stdc++.h> #define me(a,x) memset(a,x,sizeof(a)) #define sc scanf #define itn int using namespace std; const int N=1e6; const long long mod=1e9+7; const int oo=0x7fffffff; const int sup=0x80000000; typedef long long ll; typedef unsigned long long ull; template <typename it>void db(it *begin,it *end){while(begin!=end)cout<<(*begin++)<<" ";puts("");} template <typename it> string to_str(it n){string s="";while(n)s+=n%10+'0',n/=10;reverse(s.begin(),s.end());return s;} template <typename it>int o(it a){cout<<a<<endl;return 0;} ll mul(ll a,ll b,ll c){ll ans=0;for(;b;b>>=1,a=(a+a)%c)if(b&1)ans=(ans+a)%c;return ans;} ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=mul(a,a,c))if(b&1)ans=mul(ans,a,c);return ans;} int n,m; int MAX[N],MIN[N],gcd[N]; int pos[N],sum[N]={0}; int main(){ //freopen("in.txt","r",stdin); cin>>n>>m; vector<int>cdi(n+5,0),cnt(n+5,0); function<void(int x,int val)>modify=[&](int x,int val){for(int i=x;i<=n;i+=i&(-i))sum[i]+=val;}; function<int(int x)>getsum=[&](int x){int res=0;for(int i=x;i;i&=i-1)res+=sum[i];return res;}; for(int i=1;i<=n;i++){ sc("%d",&cdi[i]); if(i==1)cnt[i]=cdi[i]; else cnt[i]=cdi[i]-cdi[i-1]; modify(i,cnt[i]); } function<void(int rt)>push=[&](int rt){ gcd[rt]=__gcd(gcd[rt<<1],gcd[rt<<1|1]); MAX[rt]=max(MAX[rt<<1],MAX[rt<<1|1]); MIN[rt]=min(MIN[rt<<1],MIN[rt<<1|1]); }; function<void(int l,int r,int rt)> tree=[&](int l,itn r,int rt){ if(l==r){ pos[l]=rt; gcd[rt]=cnt[l]; MAX[rt]=MIN[rt]=cnt[l]; return; } int mid=l+r>>1; tree(l,mid,rt<<1); tree(mid+1,r,rt<<1|1); push(rt); }; function<void(int pt,int val)> up=[&](int pt,int val){ int x=pos[pt]; gcd[x]+=val; MIN[x]=(MAX[x]+=val); while(x>1)x>>=1,push(x); }; function<int(int l,int r,itn rt,int L,int R,int op)> Q=[&](int l,itn r,int rt,int L,int R,int op){ if(l>=L&&r<=R){ if(op==1)return MAX[rt]; if(op==2)return MIN[rt]; if(op==3)return gcd[rt]; } int mid=l+r>>1; if(op==1){ int x=sup; if(mid>=L)x=max(x,Q(l,mid,rt<<1,L,R,op)); if(mid<R)x=max(x,Q(mid+1,r,rt<<1|1,L,R,op)); return x; }else if(op==2){ int x=oo; if(mid>=L)x=min(x,Q(l,mid,rt<<1,L,R,op)); if(mid<R)x=min(x,Q(mid+1,r,rt<<1|1,L,R,op)); return x; }else{ int x=0; if(mid>=L)x=__gcd(x,Q(l,mid,rt<<1,L,R,op)); if(mid<R)x=__gcd(x,Q(mid+1,r,rt<<1|1,L,R,op)); return x; } }; tree(1,n,1); while(m--){ int op; sc("%d",&op); if(op==1){ int l,r,x; sc("%d%d%d",&l,&r,&x); modify(l,x);modify(r+1,-x); up(l,x);up(r+1,-x); }else if(op==2){ int l,r; sc("%d%d",&l,&r); if(l==r){ puts("0"); continue; } int mi=Q(1,n,1,l+1,r,2); int ma=Q(1,n,1,l+1,r,1); printf("%d\n",max(abs(mi),abs(ma))); }else{ int l,r; sc("%d%d",&l,&r); if(l==r){ printf("%d\n",getsum(l)); continue; } int ans=__gcd(getsum(l),Q(1,n,1,l+1,r,3)); if(ans<0)ans=-ans; printf("%d\n",ans); } } }