# CFR 52 C. Circular RMQ ( Segment Tree )

Problem - 52C - Codeforces
Tag のちょっとした練習になる。

```#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
const int MAXM = 2e5 + 5;
const int MAXABSV = 1e6 + 6;
typedef long long ll;
const ll INF = 1e16;

int n;
int a[ MAXN ];
int m;

struct itvt{
int lb, rb;
itvt *lc, *rc;
itvt(int _l = 0, int _r = 0): minv(INF), add_tag(0), lb(_l), rb(_r), lc(NULL), rc(NULL){}
void push(){
}
void pull(){
minv = min<ll>( lc->minv, rc->minv );
}
void update(int ql, int qr, int v){
if( qr < lb || rb < ql ) return;
if( ql <= lb && rb <= qr ){
minv += v;
return;
}
int mid = lb + rb >> 1;
push();
lc->update( ql, qr, v );
rc->update( ql, qr, v );
pull();
}
ll qmin(int ql, int qr){
if( qr < lb || rb < ql ) return INF;
if( ql <= lb && rb <= qr ) return minv;
ll res = INF;
push();
res = min<ll>( res, lc->qmin( ql, qr ) );
res = min<ll>( res, rc->qmin( ql, qr ) );
pull();
return res;
}
};

itvt* buildItvt(int lb, int rb){
itvt *t = new itvt( lb, rb );
if( lb == rb ){
t->minv = a[ lb ];
return t;
}
int mid = lb + rb >> 1;
t->lc = buildItvt( lb, mid );
t->rc = buildItvt( mid + 1, rb );
t->pull();
return t;
}

int main(){
ios::sync_with_stdio( false );
cin >> n;
for(int i = 0; i < n; ++i)
cin >> a[ i ];
cin >> m;
itvt *root = buildItvt( 0, n - 1 );
string line; getline( cin, line ); // "\n"
while( m-- ){
getline( cin, line ); stringstream ss( line );
vector<int> vin;
int v; while( ss >> v ) vin.push_back( v );
if( (int)vin.size() == 2 ){
int lf = vin[ 0 ], rg = vin[ 1 ];
ll minv = INF;
if( lf <= rg )
minv = min<ll>( minv, root->qmin( lf, rg ) );
else
minv = min<ll>( minv, root->qmin( lf, n - 1 ) ),
minv = min<ll>( minv, root->qmin( 0, rg ) );
cout << minv << endl;
} else{
int lf = vin[ 0 ], rg = vin[ 1 ];
ll v = vin[ 2 ];
if( lf <= rg )
root->update( lf, rg, v );
else
root->update( lf, n - 1, v ),
root->update( 0, rg, v );
}
}
return 0;
}
```