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{
    ll minv, add_tag;
    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(){
        lc->minv += add_tag;
        rc->minv += add_tag;
        lc->add_tag += add_tag;
        rc->add_tag += add_tag;
        add_tag = 0LL;
    }
    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;
            add_tag += 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;
}