You are given circular array a0,?a1,?...,?an?-?1. There are two types of operations with it:
- inc(lf,?rg,?v) — this operation increases each element on the segment [lf,?rg](inclusively) by v;
- rmq(lf,?rg) — this operation returns minimal value on the segment [lf,?rg](inclusively).
Assume segments to be circular, so if n?=?5 and lf?=?3,?rg?=?1, it means the index sequence: 3,?4,?0,?1.
Write program to process given sequence of operations.
The first line contains integer n (1?≤?n?≤?200000). The next line contains initial state of the array: a0,?a1,?...,?an?-?1 (?-?106?≤?ai?≤?106), ai are integer. The third line contains integer m (0?≤?m?≤?200000), m — the number of operartons. Next mlines contain one operation each. If line contains two integer lf,?rg (0?≤?lf,?rg?≤?n?-?1) it means rmq operation, it contains three integers lf,?rg,?v (0?≤?lf,?rg?≤?n?-?1;?-?106?≤?v?≤?106) — inc operation.
For each rmq operation write result for it. Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cout (also you may use %I64d).
4 1 2 3 4 4 3 0 3 0 -1 0 1 2 1
1 0 0
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=200006;
#define INF 0x3fffffff
#define lson ans<<1,ll,mid
#define rson ans<<1|1,mid+1,rr
__int64 m,n,sum[N],mins[N<<2],lazy[N<<2];
char str[200];__int64 min(__int64 x,__int64 y)
{return x>y?y:x;
}void pushup(int ans)
{mins[ans] =min(mins[ans<<1],mins[ans<<1|1]);
}void pushdown(int ans)
{if(lazy[ans]){lazy[ans<<1]+=lazy[ans] ;lazy[ans<<1|1]+=lazy[ans] ;mins[ans<<1]+= lazy[ans];mins[ans<<1|1]+=lazy[ans];lazy[ans]=0;}
}void build_tree(int ans,int ll,int rr)
{lazy[ans] =0;if(ll == rr ){mins[ans] = sum[ll];return ;}int mid = (ll + rr )>>1;build_tree(lson);build_tree(rson);pushup(ans);
}void update(int ans,int ll,int rr,int L,int R,int value)
{if(L<=ll && R>= rr){lazy[ans]+=value;mins[ans]+=value;return ;}pushdown(ans);int mid = (ll+rr)>>1;if(mid<R)//更新从mid+1到R的的区间update(rson,L,R,value);if(mid>=L)update(lson,L,R,value);pushup(ans);
}__int64 query(int ans,int ll,int rr,int L,int R)
{if(ll>=L && rr<= R)//是否在区间内{return mins[ans];}pushdown(ans);int mid = (ll+rr)>>1;__int64 ss=INF;if(mid >= L)//往左走{ss=min(ss,query(lson,L,R));}if(mid<R)//往右走ss = min(ss,query(rson,L,R));return ss;
}int main()
{while(~scanf("%I64d",&n)){int a,b,c;n--;for(int i=0;i<=n;i++)scanf("%I64d",&sum[i]);build_tree(1,0,n);scanf("%I64d",&m);getchar();for(int i=1;i<=m;i++){gets(str);if(sscanf(str,"%d%d%d",&a,&b,&c)==3){if(a>b){update(1,0,n,a,n,c);update(1,0,n,0,b,c);}elseupdate(1,0,n,a,b,c);}else{if(a>b){__int64 ans=min(query(1,0,n,a,n),query(1,0,n,0,b));printf("%I64d\n",ans);}else{printf("%I64d\n",query(1,0,n,a,b));}}}}return 0;
}