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.
Input 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 m lines 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.
Output 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).
Examples Input 4 1 2 3 4 4 3 0 3 0 -1 0 1 2 1 Output 1 0 0 题意：两操作，第一种操作是指给固定区间加上权值 k ， 第二是询问，询问输出区间值最小值。 思路：线段树模板可解，特别地，由于它的环状结构，当操作的 r 边界小于 l 边界时，分两步进行更新或者是询问，(l - n) , (0 - r) ，注意边界取值从零开始。
#include<cstdio> //* #include<cstring> //* #include<algorithm> //* #include<iostream> //* #include<vector> //* #include<map> //* #include<set> //* #include<queue> //* #include<stack> //* #include<cmath> //* #include<list> //* #define ll INT //* #define INT __int64 //* #define usn unsigned //* const int INF = 0x3f3f3f3f; //* const ll INF_LL = 9223372036854775807LL; //* const double E = exp(1.0); //* const double PI = acos(-1.0); //* ll gcd(ll a,ll b){while(b^=a^=b^=a%=b);return a;} //* ll lcd(ll a , ll b){return a * b / gcd(a,b);} //* inline ll read(){ //* char ch = getchar(); ll x = 0, f = 1; //* while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();} //* while('0' <= ch && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();} //* return x * f; //* } //* inline void write(ll x) //* { //* if(x<0) { //* putchar('-'); //* x = -x; //* } //* if(x>9) write(x / 10); //* putchar(x % 10 + '0'); //* } //* void init_cin(){ //* std::ios::sync_with_stdio(false); //* std::cin.tie(nullptr); //* std::cout.tie(nullptr); //* } //* using namespace std; //* //---------------------------------------------------------------------------//* const int MAXN = (ll)1e5 * 2 + 5; ll v[MAXN<<2] , lazy[MAXN<<2]; void up(int pos){ v[pos] = min(v[pos<<1|1] , v[pos<<1]); } void down(int pos){ if(lazy[pos]){ lazy[pos<<1] += lazy[pos]; lazy[pos<<1|1] += lazy[pos]; v[pos<<1] += lazy[pos]; v[pos<<1|1] += lazy[pos]; lazy[pos] = 0; } } void build(int pos , int l , int r){ if(l == r){ scanf("%I64d", v + pos); return; } int mid = l + r >> 1; build(pos<<1,l,mid); build(pos<<1|1,mid+1,r); up(pos); } void update(int pos , int l , int r , int L , int R , int k){ if(l >= L && R >= r){ lazy[pos] += k; v[pos] += k; return; } down(pos); int mid = l + r >> 1; if(R > mid) update(pos<<1|1,mid+1,r,L,R,k); if(L <= mid) update(pos<<1,l,mid,L,R,k); up(pos); } ll solve(int pos , int l , int r ,int L , int R){ if(l >= L && R >= r){ return v[pos];} down(pos); int mid = l + r >> 1; ll ans = INF_LL; if(R > mid) ans = min(ans ,solve(pos<<1|1,mid+1,r,L,R)); if(L <= mid) ans = min(ans ,solve(pos<<1,l,mid,L,R)); return ans; } inline void get(ll *a , ll *b , ll *c) { char doll = 0; ll d[3] = {INF_LL,INF_LL,INF_LL}; int cnt = 0; while(doll != '\n'){ scanf("%I64d",&d[cnt++]); doll = getchar(); } *a = d[0] , *b = d[1] , *c = d[2]; } int main(){ int n; scanf("%d", &n); build(1,1,n); int m; scanf("%d", &m); while(m--){ ll a = INF_LL , b = INF_LL , c = INF_LL; get(&a,&b,&c);a++,b++; if(c != INF_LL) { if(a <= b){ update(1,1,n,a,b,c); } else{ update(1,1,n,a,n,c); update(1,1,n,1,b,c); } }else { if(a <= b){ printf("%I64d\n", (solve(1,1,n,a,b))); } else{ printf("%I64d\n",min(solve(1,1,n,1,b),solve(1,1,n,a,n))); } } } }