动态开点线段树求调
查看原帖
动态开点线段树求调
782210
Yu_Chengxuan楼主2024/8/6 15:52
#include <bits/stdc++.h>
using namespace std;

int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
int n, m, root;
const int maxn = 500010;
struct node {
    int l, r, sum;
} t[maxn * 55];

#define ls(x) t[x].l
#define rs(x) t[x].r


int tag[maxn], siz;
void pushdown(int l, int r, int x) {
    
    if (tag[x] != -1) {
    	if (!t[x].l)
        	t[x].l = ++siz;
    	if (!t[x].r)
        	t[x].r = ++siz;
        int mid = l + r >> 1;
        tag[t[x].l] = tag[t[x].r] = tag[x];
        t[t[x].l].sum = tag[x] * (mid - l + 1);
        t[t[x].r].sum = tag[x] * (r - mid);
        tag[x] = -1;
    }
}
void insert(int& in, int cl, int cr, int l, int r, int k) {
    if (!in) {
        in = ++siz;
    }
    if (cl <= l && r <= cr) {
        t[in].sum = k * (r - l + 1);
        tag[in] = k;
        return;
    }
    pushdown(l, r, in);
    int mid = (l + r) >> 1;
    if (cl <= mid) {
        insert(t[in].l, cl, cr, l, mid, k);
    }
    if (cr > mid) {
        insert(t[in].r, cl, cr, mid + 1, r, k);
    }
    t[in].sum = t[t[in].l].sum + t[t[in].r].sum;
}
void clean() { memset(tag, -1, sizeof(tag)); }
int main() {
    n = read(), m = read();
    clean();
    while (m--) {
        int l = read(), r = read(), opr = read();
        if (opr == 1) {
            insert(root, l, r, 1, n, 1);
        } else {
            insert(root, l, r, 1, n, 0);
        }
        cout << n - t[root].sum << "\n";
    }
}
2024/8/6 15:52
加载中...