Codeforces 915E - Physical Education Lessons

动态开点只能开\(Ofast\)莽过去

#pragma GCC optimize("Ofast")
#include 
using namespace std;
const int N = 15000010;
int n, Q, root, cnt, L[N], R[N], seg[N], lazy[N];
void pushup(int u)
{
    seg[u] = seg[L[u]] + seg[R[u]];
}
void pushdown(int u, int l, int r)
{
    if (lazy[u] != -1) {
        int mid = l + r >> 1;
        if (!L[u])  L[u] = ++ cnt;
        seg[L[u]] = lazy[u] * (mid - l + 1);
        lazy[L[u]] = lazy[u];
        if (!R[u])  R[u] = ++ cnt;
        seg[R[u]] = lazy[u] * (r - mid);
        lazy[R[u]] = lazy[u];
        lazy[u] = -1;
    }
}
void modify(int &x, int ll, int rr, int l, int r, int k)
{
    if (!x) x = ++ cnt;
    if (l <= ll && rr <= r) {
        seg[x] = (rr - ll + 1) * k;
        lazy[x] = k;
        return;
    }
    pushdown(x, ll, rr);
    int mid = ll + rr >> 1;
    if (l <= mid)   modify(L[x], ll, mid, l, r, k);
    if (r > mid)    modify(R[x], mid + 1, rr, l, r, k);
    pushup(x);
}
int main() {
    scanf("%d%d", &n, &Q);
    memset(lazy, -1, sizeof lazy);
    modify(root, 1, n, 1, n, 0);
    while (Q -- ) {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        modify(root, 1, n, l, r, 2 - k);
        printf("%d\n", n - seg[1]);
    }
    return 0;
}