rt,在学术版是因为这道题没几个人做,经过我的调试,发现样例中第二次修改之后,整个区间的min值还是1,理论上应该是0。
#include<bits/stdc++.h>
#define lid (id<<1)
#define rid (id<<1|1)
#define int long long
using namespace std;
const int maxn=200005;
int n,q,m,ans,a[maxn];
struct seg_tree{
int l,r,mn,add;
}tr[maxn<<2];
void build(int id,int l,int r){
tr[id].l=l,tr[id].r=r;
if(l==r){
tr[id].mn=a[l];
return;
}
int mid=(l+r)>>1;
build(lid,l,mid);
build(rid,mid+1,r);
tr[id].mn=min(tr[lid].mn,tr[rid].mn);
}
void pushdown(int id){
tr[lid].add+=tr[id].add,tr[rid].add+=tr[id].add;
tr[lid].mn+=tr[id].add,tr[rid].mn+=tr[id].add;
tr[id].add=0;
//cout<<id<<" "<<tr[id].l<<" "<<tr[id].r<<" "<<tr[id].mn<<" "<<tr[id].add<<endl;
}
void change(int id,int l,int r,int k){
if(tr[id].l==l&&tr[id].r==r){
tr[id].add+=k,tr[id].mn+=k;
return;
}
pushdown(id);
int mid=(tr[id].l+tr[id].r)>>1;
if(r<=mid)change(lid,l,r,k);
else if(l>mid)change(rid,l,r,k);
else change(lid,l,mid,k),change(rid,mid+1,r,k);
tr[id].mn=min(tr[lid].mn,tr[rid].mn);
}
int query(int id,int l,int r){
if(tr[id].l==l&&tr[id].r==r)return tr[id].mn;
pushdown(id);
int mid=(tr[id].l+tr[id].r)>>1;
if(r<=mid)return query(lid,l,r);
else if(l>mid)return query(rid,l,r);
else return min(query(lid,l,mid),query(rid,mid+1,r));
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
build(1,1,n);
cin>>q;
while(q--){
int x,y,z;
char c;
cin>>x>>y;
x++,y++;
c=getchar();
if(c!='\n'){
cin>>z;
z++;
if(x>y)change(1,x,n,z),change(1,1,y,z);
else change(1,x,y,z);
}else{
ans=1111111;
if(x>y)ans=min(ans,min(query(1,x,n),query(1,1,y)));
else ans=min(ans,query(1,x,y));
cout<<ans<<endl;
}
}
return 0;
}