915E - Physical Education Lessons - CodeForces Solution

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <stack>
#include <ctime>
#define SEQ 19

using namespace std;

typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<int, pii> piii;
typedef pair<int, long long > pil;
typedef long long ll;
const int N = 3400086, MOD = 1e9 + 7, INF = 0x3f3f3f3f, MID = 50000;
int n, idx, w[N], m;
ll f[N], root;
struct Node
{
    int l, r;
    int sum, flag;
}tr[N << 2];

inline int lowbit(int x)
{
   return x & -x;
}

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

inline void fin()
{
    printf("-1\n");
    exit(0);
}

inline void pushup(int u)
{
    tr[u].sum = 0;
    if (tr[u].l) tr[u].sum += tr[tr[u].l].sum;
    if (tr[u].r) tr[u].sum += tr[tr[u].r].sum;
}

inline void pushdown(int u, int l, int r)
{
    if (!tr[u].flag) return;
    int mid = l + r >> 1;
    if (!tr[u].l) tr[u].l = ++idx;
    if (!tr[u].r) tr[u].r = ++idx;
    tr[tr[u].l].flag = tr[tr[u].r].flag = tr[u].flag;
    if (tr[u].flag == 1)
    {
        tr[tr[u].l].sum = mid - l + 1;
        tr[tr[u].r].sum = r - mid;
    }
    else tr[tr[u].l].sum = tr[tr[u].r].sum = 0;
    tr[u].flag = 0;
}

int query(int u, int l, int r, int pl, int pr)
{
    if (!u) return 0;
    if (l >= pl && r <= pr) return tr[u].sum;
    pushdown(u, l, r);
    int mid = l + r >> 1, res = 0;
    if (pl <= mid) res += query(tr[u].l, l, mid, pl, pr);
    if (pr > mid) res += query(tr[u].r, mid + 1, r, pl, pr);
    return res;
}

void modify(int u, int l, int r, int pl, int pr, int nv)
{
    if (l >= pl && r <= pr)
    {
        tr[u].flag = nv;
        if (nv == 1) tr[u].sum = r - l + 1;
        else tr[u].sum = 0;
    }
    else
    {
        pushdown(u, l, r);
        int mid = l + r >> 1;
        if (pl <= mid)
        {
            if (!tr[u].l) tr[u].l = ++idx;
            modify(tr[u].l, l, mid, pl, pr, nv);
        }
        if (pr > mid)
        {
            if (!tr[u].r) tr[u].r = ++idx;
            modify(tr[u].r, mid + 1, r, pl, pr, nv);
        }
        pushup(u);
    }
}

int main()
{
    cin >> n >> m;
    root = ++idx;
    while (m--)
    {
        int op, a, b;
        scanf("%d%d%d", &a, &b, &op);
        if (op == 1) modify(1, 1, n, a, b, 1);
        else modify(1, 1, n, a, b, 2);
        printf("%d\n", n - tr[1].sum);
    }
    return 0;
}