o57_oct_c2_fallingblocks

#include <bits/stdc++.h>

using namespace std;
const int inf = 2e9;
const int N = 1e5;
struct Node{
    int hl, hr, up, down;
};
Node tree[(1 << 18)];
int lazy[(1 << 18)];

Node Combine(Node L, Node R){
    Node cur;
    cur.hl = L.hl;
    cur.hr = R.hr;
    cur.up = L.up + R.up;
    cur.down = L.down + R.down;
    int l = L.hr, r = R.hl;
    if(l < r) cur.up ++;
    else if(l > r) cur.down ++;
    return cur;
}

void Lazy(int idx, int l, int r){
    if(lazy[idx] == 0) return;
    if(l != r){
        lazy[2 * idx] += lazy[idx];
        lazy[2 * idx + 1] += lazy[idx];
    }
    tree[idx].hl += lazy[idx];
    tree[idx].hr += lazy[idx];
    lazy[idx] = 0;
}

void Update(int idx, int l, int r, int s, int e){
    Lazy(idx, l, r);
    if(l > e or r < s) return;
    if(s <= l and r <= e){
        if(l != r){
            lazy[2 * idx] ++;
            lazy[2 * idx + 1] ++;
        }
        tree[idx].hl ++;
        tree[idx].hr ++;
        return;
    }
    int mid = (l + r) / 2;
    Update(2 * idx, l, mid, s, e);
    Update(2 * idx + 1, mid + 1, r, s, e);
    tree[idx] = Combine(tree[2 * idx], tree[2 * idx + 1]);
}

Node Query(int idx, int l, int r, int s, int e){
    Lazy(idx, l, r);
    if(l > e or r < s) return {inf, inf, inf, inf};
    if(s <= l and r <= e)
        return tree[idx];
    int mid = (l + r) / 2;
    if(mid < s) return Query(2 * idx + 1, mid + 1, r, s, e);
    else if(e < mid + 1) return Query(2 * idx, l, mid, s, e);
    Node L = Query(2 * idx, l, mid, s, e);
    Node R = Query(2 * idx + 1, mid + 1, r, s, e);
    return Combine(L, R);
}

int main(){

    int n, m;
    scanf("%d %d", &n, &m);

    for(int i=1;i<=m;i++){
        int opr, x, y;
        scanf("%d %d %d", &opr, &x, &y);
        if(opr == 1)
            Update(1, 1, n, x, y);
        else if(opr == 2){
            Node Q = Query(1, 1, n, x, y);
            printf("%d %d\n", Q.hl, Q.hr);
        }
        else {
            Node Q = Query(1, 1, n, x, y);
            printf("%d %d %d %d\n", Q.hl, Q.hr, Q.up, Q.down);
        }
    }

    return 0;
}