一点都不难
环状修改+RMQ
一看就是线段树
然后l<=r直接修改,l>r则分(l,n)和(1,r)
结束了
(PS:r和R搞错调了20min)
代码:
#include<bits/stdc++.h> using namespace std; const int N=200005; typedef long long ll; int n,m; ll a[N]; char c[N]; inline ll llmin(ll x,ll y){return x<y?x:y;} struct Sugment_Tree{ ll t[N<<2]; ll LZT[N<<2]; Sugment_Tree(){memset(LZT,0,sizeof(LZT));} #define il inline #define mid (l+r)/2 il void push_up(int num){t[num]=llmin(t[num<<1]+LZT[num<<1],t[num<<1|1]+LZT[num<<1|1]);} il void build(int l,int r,int num){ LZT[num]=0; if(l==r){t[num]=a[l];return;} build(l,mid,num<<1),build(mid+1,r,num<<1|1); push_up(num); } /* il void push_down(int num){ LZT[num<<1]+=LZT[num],LZT[num<<1|1]+=LZT[num]; t[num<<1]+=LZT[num],t[num<<1|1]+=LZT[num]; LZT[num]=0; } */ il void upt(int l,int r,int num,int L,int R,int sum){ if(l>=L&&r<=R){ LZT[num]+=sum; return; } if(l>R||r<L) return; upt(l,mid,num<<1,L,R,sum); upt(mid+1,r,num<<1|1,L,R,sum); push_up(num); } il ll ask(int l,int r,int num,int L,int R){ if(l>=L&&r<=R){return t[num]+LZT[num];} if(l>R||r<L) return 4327429874328; return llmin(ask(l,mid,num<<1,L,R),ask(mid+1,r,num<<1|1,L,R))+LZT[num]; } }T; int sp=0; inline int read() { sp=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==‘ ‘) sp=1; return s*w; } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) cin>>a[i]; T.build(1,n,1); cin>>m; while(m--){ int l,r; ll x; int nega; int cnt=0; l=read(); r=read(); if(sp==1){ cin>>x; l++,r++; if(l<=r){ T.upt(1,n,1,l,r,x); } else{ T.upt(1,n,1,l,n,x); T.upt(1,n,1,1,r,x); } } else{ l++,r++; ll ans; if(l<=r){ ans=T.ask(1,n,1,l,r); } else{ ans=llmin(T.ask(1,n,1,l,n),T.ask(1,n,1,1,r)); } cout<<ans<<endl; } } return 0; }
原文:https://www.cnblogs.com/QYJ060604/p/11423536.html