E. Physical Education Lessons

This year Alex has finished school, and now he is a first-year student of Berland State University. For him it was a total surprise that even though he studies programming, he still has to attend physical education lessons. The end of the term is very soon, but, unfortunately, Alex still hasn't attended a single lesson!

Since Alex doesn't want to get expelled, he wants to know the number of working days left until the end of the term, so he can attend physical education lessons during these days. But in BSU calculating the number of working days is a complicated matter:

There are n days left before the end of the term (numbered from $1$ to $n$), and initially all of them are working days. Then the university staff sequentially publishes q orders, one after another. Each order is characterised by three numbers $l$, $r$ and $k$:

• If $k = 1$, then all days from $l$ to $r$ (inclusive) become non-working days. If some of these days are made working days by some previous order, then these days still become non-working days;
• If $k = 2$, then all days from $l$ to $r$ (inclusive) become working days. If some of these days are made non-working days by some previous order, then these days still become working days.
  Help Alex to determine the number of working days left after each order!

Input

The first line contains one integer $n$, and the second line — one integer $q$ ($1 \leq n \leq 10^9$, $1 \leq q \leq 3 \cdot 10^5$) — the number of days left before the end of the term, and the number of orders, respectively.

Then $q$ lines follow, $i$-th line containing three integers $l_i$, $r_i$ and $k_i$ representing $i$-th order ($1 \leq l_i \leq r_i \leq n$, $1 \leq k_i \leq 2$).

Output

Print q integers. i-th of them must be equal to the number of working days left until the end of the term after the first i orders are published.

Example

input

4
6
1 2 1
3 4 1
2 3 2
1 3 2
2 4 1
1 4 2

output

2
0
2
3
1
4

解题思路

  这里提供两种做法，一个是离散化加静态线段树，另一个是动态开点线段树。

  首先 $n$ 最大是 $10^9$，我们不可能开这么大的内存空间，因此需要对询问的下标进行离散化，同时用离散化后的下标来表示划分得到的区间。另外为了方便，如果询问的区间是 $l$ 和 $r$，那么对 $l$ 和 $r+1$进行离散化。例如有 $n=10$，询问的区间有 $[1,4]$，$[4,4]$ 和 $[1,10]$，则对 $[1,4,5,11]$ 进行离散化得到 $[1,2,3,4]$。长度为 $n=10$ 的区间则被这些下标被分成三段，分别用 $1$ 来表示区间$[1,3]$，$2$ 来表示区间 $[4,4]$，$3$ 来表示区间$[5,10]$。

  用 $\text{xs}[i]$ 来表示离散化后是 $i$ 所对应的值。在上例中有 $\text{xs}[1] = 1$，$\text{xs}[2] = 4$，$\text{xs}[3] = 5$，$\text{xs}[4] = 11$。

  因此线段树节点维护的区间 $[l,r]$ 是关于离散化后下标的区间，对应 $l$ 到 $r$ 所表示的原本长度为 $n$ 的区间段，即 $\left[ \text{xs}[l], \, \text{xs}[r+1] - 1 \right]$。

  另外询问的修改操作是对某个区间的值全部修改成 $1$ 或 $0$，查询操作是求某个区间的总和。因此线段树节点需要维护一个懒标记 $\text{tag} = 0/1$ 表示当前区间被修改成的值，如果 $\text{tag} = -1$ 则表示该区间没有被修改或者是懒标记已经下传了。同时维护区间和 $s$，表示区间 $\left[ \text{xs}[l], \, \text{xs}[r+1] - 1 \right]$ 的总和。当 $\text{tag}$ 被更新，则 $s$ 对应的更新是 $s = \left( \text{xs}[r+1] - \text{xs}[l] \right) \cdot \text{tag}$。

  另外需要注意的是本题中用 scanf 和 printf 会超时。

  AC 代码如下，时间复杂度为 $O(q \log{q})$：

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

const int N = 3e5 + 10, M = N * 2;

struct Query {
    int l, r, k;
}q[N];
struct Node {
    int l, r, s, tag;
}tr[M * 4];
int xs[M], sz;

void build(int u, int l, int r) {
    tr[u] = {l, r, 0, -1};
    if (l == r) {
        tr[u].s = xs[r + 1] - xs[l];
    }
    else {
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        tr[u].s = tr[u << 1].s + tr[u << 1 | 1].s;
    }
}

void pushdown(int u) {
    if (tr[u].tag != -1) {
        tr[u << 1].s = (xs[tr[u << 1].r + 1] - xs[tr[u << 1].l]) * tr[u].tag;
        tr[u << 1].tag = tr[u].tag;
        tr[u << 1 | 1].s = (xs[tr[u << 1 | 1].r + 1] - xs[tr[u << 1 | 1].l]) * tr[u].tag;
        tr[u << 1 | 1].tag = tr[u].tag;
        tr[u].tag = -1;
    }
}

void modify(int u, int l, int r, int c) {
    if (tr[u].l >= l && tr[u].r <= r) {
        tr[u].tag = c;
        tr[u].s = (xs[tr[u].r + 1] - xs[tr[u].l]) * c;
    }
    else {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u << 1, l, r, c);
        if (r >= mid + 1) modify(u << 1 | 1, l, r, c);
        tr[u].s = tr[u << 1].s + tr[u << 1 | 1].s;
    }
}

int find(int x) {
    int l = 1, r = sz;
    while (l < r) {
        int mid = l + r >> 1;
        if (xs[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return l;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> q[i].l >> q[i].r >> q[i].k;
        xs[++sz] = q[i].l;
        xs[++sz] = q[i].r + 1;
    }
    xs[++sz] = 1, xs[++sz] = n + 1;
    sort(xs + 1, xs + sz + 1);
    sz = unique(xs + 1, xs + sz + 1) - xs - 1;
    build(1, 1, sz - 1);
    for (int i = 0; i < m; i++) {
        modify(1, find(q[i].l), find(q[i].r + 1) - 1, ~q[i].k & 1);
        cout << tr[1].s << '\n';
    }
    
    return 0;
}

  下面给出动态开点的做法，与上面的分析一样，不过由于动态开点因此不需要进行离散化。不过动态开点所需要的空间大概是 $3 \times 10^5 \cdot 2 \cdot \log{10^9} \cdot 4 \cdot 4 \, / \, 2^{20} \approx 273 \text{ MB} > 256 \text{ MB}$，当然这是最坏情况下的，实际上只需开 $3 \times 10^5 \times 50$ 大小的 $4$ 个 int 数组即可。

  AC 代码如下，时间复杂度为 $O(q \log{q})$：

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

const int N = 3e5 + 10;

struct Node {
    int l, r, s, tag;
}tr[N * 50];
int root, idx;

int get_node() {
    tr[++idx] = {0, 0, 0, -1};
    return idx;
}

void pushdown(int u, int l, int r) {
    if (tr[u].tag != -1) {
        if (!tr[u].l) tr[u].l = get_node();
        if (!tr[u].r) tr[u].r = get_node();
        int mid = l + r >> 1;
        tr[tr[u].l].s = (mid - l + 1) * tr[u].tag;
        tr[tr[u].l].tag = tr[u].tag;
        tr[tr[u].r].s = (r - mid) * tr[u].tag;
        tr[tr[u].r].tag = tr[u].tag;
        tr[u].tag = -1;
    }
}

void modify(int &u, int l, int r, int ql, int qr, int c) {
    if (!u) u = get_node();
    if (l >= ql && r <= qr) {
        tr[u].s = (r - l + 1) * c;
        tr[u].tag = c;
    }
    else {
        pushdown(u, l, r);
        int mid = l + r >> 1;
        if (ql <= mid) modify(tr[u].l, l, mid, ql, qr, c);
        if (qr >= mid + 1) modify(tr[u].r, mid + 1, r, ql, qr, c);
        tr[u].s = tr[tr[u].l].s + tr[tr[u].r].s;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    while (m--) {
        int l, r, k;
        cin >> l >> r >> k;
        modify(root, 1, n, l, r, k & 1);
        cout << n - tr[root].s << '\n';
    }
    
    return 0;
}

  另外给出这题的扩展版：扶苏的问题。

参考资料

  234 线段树+动态开点 CF915E Physical Education Lessons：https://www.bilibili.com/BV1Uh4y1i7hm/