?
线段树区间更新水题。
代码如下：
#include #include #include #include #include #include #include #include #include #include #include using namespace std; const int INF=0x3f3f3f3f; #define lson l, mid, rt<<1 #define rson mid+1, r, rt<<1|1 int min1[1000000], lazy[1000000]; void PushUp(int rt) { min1[rt]=min(min1[rt<<1],min1[rt<<1|1]); } void PushDown(int rt) { if(lazy[rt]) { min1[rt<<1|1]+=lazy[rt]; min1[rt<<1]+=lazy[rt]; lazy[rt<<1|1]+=lazy[rt]; lazy[rt<<1]+=lazy[rt]; lazy[rt]=0; } } void build(int l, int r, int rt) { if(l==r) { scanf(%d,&min1[rt]); return ; } int mid=l+r>>1; build(lson); build(rson); PushUp(rt); } void update(int ll, int rr, int x, int l, int r, int rt) { if(ll<=l&&rr>=r) { lazy[rt]+=x; min1[rt]+=x; return ; } PushDown(rt); int mid=l+r>>1; if(ll<=mid) update(ll,rr,x,lson); if(rr>mid) update(ll,rr,x,rson); PushUp(rt); } int query(int ll, int rr, int l, int r, int rt) { if(ll<=l&&rr>=r) { return min1[rt]; } PushDown(rt); int ans=INF, mid=l+r>>1; if(ll<=mid) ans=min(ans,query(ll,rr,lson)); if(rr>mid) ans=min(ans,query(ll,rr,rson)); return ans; } int main() { int n, l, r, x, q, i; scanf(%d,&n); build(0,n-1,1); scanf(%d,&q); memset(lazy,0,sizeof(lazy)); while(q--) { scanf(%d%d,&l,&r); if(getchar()==' ') { scanf(%d,&x); if(l>r) { update(l,n-1,x,0,n-1,1); update(0,r,x,0,n-1,1); /*for(i=1;i<=7;i++) printf(%d ,min1[i]); printf( );*/ } else { update(l,r,x,0,n-1,1); /*for(i=1;i<=7;i++) printf(%d ,min1[i]); printf( );*/ } } else { if(l>r) { int ans=min(query(l,n-1,0,n-1,1),query(0,r,0,n-1,1)); printf(%d ,ans); } else { int ans=query(l,r,0,n-1,1); printf(%d ,ans); } } } return 0; }