min_and_update.cpp

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n, m, q;
const int MAXN = 2e5 + 10;
const int INF = 1e9 + 7;

int t[4 * MAXN], a[MAXN], add[4 * MAXN];

void build(int v, int tl, int tr){
    if (tl > tr){
        return;
    }
    if (tl == tr){
        t[v] = a[tl];
        return;
    }

    int tm = (tl + tr) / 2;
    build(v + v, tl, tm);
    build(v + v + 1, tm + 1, tr);
    t[v] = min(t[v + v], t[v + v + 1]);
}

void push(int v){
    if (add[v] != 0){
        t[v + v] += add[v];
        t[v + v + 1] += add[v];
        add[v + v] += add[v];
        add[v + v + 1] += add[v];
        add[v] = 0;
    }
}

int get_min(int v, int tl, int tr, int l, int r){
    if (l > r){
        return INF;
    }
    if (l == tl && r == tr){
        return t[v];
    }
    int tm = (tl + tr) / 2;
    push(v);
    return min(get_min(v + v, tl, tm, l, min(r, tm)),
               get_min(v + v + 1, tm + 1, tr, max(l, tm + 1), r));
}

void update(int v, int tl, int tr, int l, int r, int val){
    if (l > r){
        return;
    }
    if (tl == l && tr == r){
        t[v] += val;
        add[v] += val;
        return;
    }
    int tm = (tl + tr) / 2;
    push(v);
    update(v + v, tl, tm, l, min(r, tm), val);
    update(v + v + 1, tm + 1, tr, max(l, tm + 1), r, val);
    t[v] = min(t[v + v], t[v + v + 1]);
}

int main() {

    //freopen("sum.in", "r", stdin);
    //freopen("sum.out", "w", stdout);

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }

    build(1, 1, n);
    int q;
    cin >> q;
    while(q--){

        int l, r;
        cin >> l >> r;
        update(1, 1, n, l, r, 1);

        for (int i = 1; i <= n; i++){
            cout << get_min(1, 1, n, i, i) << ' ';
        }
        cout << endl;
    }

}