You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
91 lines
2.6 KiB
91 lines
2.6 KiB
// https://blog.csdn.net/sdut16szq/article/details/79103796
|
|
// https://blog.csdn.net/why932346109/article/details/95165717
|
|
#include <iostream>
|
|
#include <cstdio>
|
|
#include <cstring>
|
|
#include <algorithm>
|
|
|
|
#define LL long long
|
|
#define lson ins << 1
|
|
#define rson ins << 1 | 1
|
|
#define mid (r + l) / 2
|
|
|
|
using namespace std;
|
|
|
|
const int Max = 6e5 + 100;
|
|
LL Hash[Max << 1], len;
|
|
LL num[Max << 1];
|
|
struct Tree {
|
|
int l, r, lazy;
|
|
LL sum;
|
|
void updata(int x) {
|
|
if (x == 1)
|
|
sum = 0;
|
|
else if (x == 2) {
|
|
LL ls = l - 1 < 0 ? 0 : num[l - 1];
|
|
sum = num[r] - ls;
|
|
}
|
|
lazy = x;
|
|
}
|
|
} tree[Max << 2];
|
|
LL Ran[Max];
|
|
|
|
inline void push_down(int ins) {
|
|
int lazyval = tree[ins].lazy;
|
|
if (lazyval) {
|
|
tree[lson].updata(lazyval);
|
|
tree[rson].updata(lazyval);
|
|
tree[ins].lazy = 0;
|
|
}
|
|
}
|
|
|
|
inline void push_up(int ins) {
|
|
tree[ins].sum = tree[lson].sum + tree[rson].sum;
|
|
}
|
|
|
|
inline void build(int l, int r, int ins) {
|
|
tree[ins].l = l, tree[ins].r = r, tree[ins].sum = tree[ins].lazy = 0;
|
|
if (r == l) {
|
|
tree[ins].sum = Ran[l];
|
|
} else if (r > l) {
|
|
build(l, mid, lson);
|
|
build(mid + 1, r, rson);
|
|
push_up(ins);
|
|
}
|
|
}
|
|
|
|
inline void updata_tree(int ql, int qr, int x, int ins) {
|
|
int l = tree[ins].l, r = tree[ins].r;
|
|
if (ql <= l && r <= qr)
|
|
tree[ins].updata(x);
|
|
else {
|
|
push_down(ins);
|
|
if (ql <= mid) updata_tree(ql, qr, x, lson);
|
|
if (qr > mid) updata_tree(ql, qr, x, rson);
|
|
push_up(ins);
|
|
}
|
|
}
|
|
struct node {
|
|
int x, y, k;
|
|
} data[Max];
|
|
int main() {
|
|
int n, m;
|
|
while (~scanf("%d%d", &n, &m)) {
|
|
for (int a = 0; a < m; a++) scanf("%d%d%d", &data[a].x, &data[a].y, &data[a].k);
|
|
for (int a = 0; a < m; a++) Hash[len++] = data[a].x, Hash[len++] = data[a].y + 1;
|
|
Hash[len++] = 1, Hash[len++] = n + 1;
|
|
sort(Hash, Hash + len);
|
|
len = unique(Hash, Hash + len) - Hash;
|
|
for (int a = 0; a < len - 1; a++) Ran[a] = Hash[a + 1] - Hash[a];
|
|
for (int a = 0; a < len - 1; a++) a == 0 ? num[a] = Ran[a] : num[a] = num[a - 1] + Ran[a];
|
|
build(0, len - 2, 1);
|
|
for (int a = 0; a < m; a++) {
|
|
int x = lower_bound(Hash, Hash + len, data[a].x) - Hash;
|
|
int y = lower_bound(Hash, Hash + len, data[a].y + 1) - Hash; // 理解为什么这样离散
|
|
y -= 1;
|
|
updata_tree(x, y, data[a].k, 1);
|
|
printf("%lld\n", tree[1].sum);
|
|
}
|
|
}
|
|
return 0;
|
|
} |