会场预约

洛谷-P2161-会场预约

实现

#include <iostream>
#define end EnD
using namespace std;

const int N = 100010;
int n, res;
int end[N]; // end[i] 记录在时刻 i 开始的预约的结束时刻
int c[N];

int lowbit (int x) {
    return x & -x;
}
void add (int idx, int val) {
    while (idx <= 100000) {
        c[idx] += val;
        idx += lowbit(idx);
    }
}
int sum (int idx) {
    int res = 0;
    while (idx >= 1) {
        res += c[idx];
        idx -= lowbit(idx);
    }
    return res;
}

int main () {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++ i) {
        char opt[5];
        scanf("%s", opt);
        if (opt[0] == 'A') {
            int b, e;
            scanf("%d%d", &b, &e);

            int cnt = 0, temp;
            while ((temp = sum(e)) >= 1) {
                int l = 0, r = e;
                while (l < r) {
                    int mid = l + r >> 1;
                    if (sum(mid) >= temp)
                        r = mid;
                    else
                        l = mid + 1;
                }
                if (end[l] >= b) { // 冲突
                    add(l, -1);
                    ++ cnt;
                    -- res;
                } else {
                    break;
                }
            }
            add(b, 1);
            end[b] = e;
            ++ res;
            printf("%d\n", cnt);
        } else {
            printf("%d\n", res);
        }
    }
    return 0;
}