華東交通大學2021年ACM“雙基”程式設計競賽 F.擺花

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int tree[N << 2], lazy[N << 2];

#define ls rt << 1
#define rs rt << 1 | 1
#define lson ls, l,
#define rson rs, mid + 1,

inline void push_up(int rt){ tree[rt] = tree[ls] + tree[rs]; }

inline void push_down(int rt, int m){
    if(lazy[rt] == -1) return;
    lazy[ls] = lazy[rt], lazy[rs] = lazy[rt];
    tree[ls] = lazy[rt] * (m - (m >> 1));
    tree[rs] = lazy[rt] * (m >> 1);
    lazy[rt] = -1;
}

inline void build(int rt, int l, int r){
    lazy[rt] = -1;
    if(l == r){ tree[rt] = 1; return;}
    int mid = l + r >> 1;
    build(lson), build(rson);
    push_up(rt);
}

inline void update(int rt, int l, int r, int ql, int qr, int val){
    if(l >= ql && r <= qr){
        lazy[rt] = val, tree[rt] = (r - l + 1) * val;
        return;
    }
    int mid = l + r >> 1;
    push_down(rt, r - l + 1);
    if(mid >= ql) update(lson, ql, qr, val);
    if(mid < qr) update(rson, ql, qr, val);
    push_up(rt);
}

inline int query(int rt, int l, int r, int ql, int qr){
    if(l >= ql && r <= qr) return tree[rt];
    int mid = l + r >> 1, ans = 0;
    push_down(rt, r - l + 1);
    if(mid >= ql) ans += query(lson, ql, qr);
    if(mid < qr) ans += query(rson, ql, qr);
    return ans;
}

inline void solve(){
    int n, m; cin >> n >> m;
    build(1, 1, n);
    while(m--){
        int op, a, b; cin >> op >> a >> b;
        if(op == 1){
            if(query(1, 1, n, a, n) < b){
                update(1, 1, n, a, n, 0);
                puts("0");
                continue;
            }
            int ll = a, rr = n;
            while(ll <= rr){
                int mid = ll + rr >> 1;
                if(query(1, 1, n, a, mid) >= 1) rr = mid - 1;
                else ll = mid + 1;
            }
            int ql = ll;
            ll = a, rr = n;
            while(ll <= rr){
                int mid = ll + rr >> 1;
                if(query(1, 1, n, a, mid) < b) ll = mid + 1;
                else rr = mid - 1;
            }
            int qr = ll;
            cout << ql << ' ' << qr << endl;
            update(1, 1, n, ql, qr, 0);
        }
        else if(op == 2){
            cout << b - a + 1 - query(1, 1, n, a, b) << endl;
            update(1, 1, n, a, b, 1);
        }
    }
    
}

signed main(){
    solve();
    return 0;
}