思路:
这道题其实还是普通的区间修改和查询问题,只不过序列变为了环形,所以就是小小的改一下就可以了。
分类讨论一下,如果输入的l<r,那么就是照常修改和查询。但由于是环形,所以会出现l>r的地方,其实也就是这样拆成l-n和1-r两个操作即可。
代码,不需要代码,太水了
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+7; struct node{ int l,r; long long lazy,mi; }tree[maxn*4]; int n,m; bool space; int a[maxn]; int l,r; long long v; inline long long read_long() { space=0; register long long s=0,w=1; register char c=getchar(); while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();} while(c>='0'&&c<='9')s=(s<<1)+(s<<3)+c-48,c=getchar(); if(c==' ') space=1; return s*w; } inline int read_int() { space=0; register int s=0,w=1; register char c=getchar(); while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();} while(c>='0'&&c<='9')s=(s<<1)+(s<<3)+c-48,c=getchar(); if(c==' ') space=1; return s*w; } void build(int now,int l,int r){ tree[now].l=l,tree[now].r=r; if(l==r){ tree[now].mi=a[l]; return; } int mid=(l+r)>>1; build(now<<1,l,mid); build(now<<1|1,mid+1,r); tree[now].mi=min(tree[now<<1].mi,tree[now<<1|1].mi); } void pushdown(int now){ if(tree[now].lazy){ tree[now<<1].mi+=tree[now].lazy; tree[now<<1|1].mi+=tree[now].lazy; tree[now<<1].lazy+=tree[now].lazy; tree[now<<1|1].lazy+=tree[now].lazy; tree[now].lazy=0; } } void update(int now,int l,int r,long long v){ if(tree[now].l>=l&&tree[now].r<=r){ tree[now].mi+=v; tree[now].lazy+=v; return; } pushdown(now); int mid=(tree[now].l+tree[now].r)>>1; if(l<=mid) update(now<<1,l,r,v); if(r>mid) update(now<<1|1,l,r,v); tree[now].mi=min(tree[now<<1].mi,tree[now<<1|1].mi); } long long query(int now,int l,int r){ if(tree[now].l>=l&&tree[now].r<=r) return tree[now].mi; pushdown(now); int mid=(tree[now].l+tree[now].r)>>1; long long ans=1e20; if(l<=mid) ans=min(ans,query(now<<1,l,r)); if(r>mid) ans=min(ans,query(now<<1|1,l,r)); return ans; } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); build(1,1,n); scanf("%d",&m); for(int i=1;i<=m;i++){ l=read_int();r=read_int(); l++,r++; if(space){ v=read_long(); if(l>r){ update(1,l,n,v); update(1,1,r,v); } else update(1,l,r,v); } else{ if(l>r) printf("%lld\n",min(query(1,l,n),query(1,1,r))); else printf("%lld\n",query(1,l,r)); } } return 0; }