Description
给你一个长度为 (n) 的 (01) 序列。初始全为 (1) ,让你兹磁 (m) 次操作:将区间内的各个数取反,并询问整个区间的 (1) 的个数。
(1leq nleq 10^9,1leq mleq 3cdot 10^5)
Solution
可以将所有询问离线,对于序列上端点间的一整块直接缩成一个节点。点权为区间长度,点数是 (O(m)) 的,线段树维护就好了。
然鹅,大佬都是直接动态开点做的...
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5;
struct operate {int l, r, id; }a[N+5];
int n, m, b[N*2+5], id[N*2+5], cost[N*4+5], tot, pos;
struct Segment_tree {
#define lr(o) (o<<1)
#define rr(o) (o<<1|1)
int sgm[N*16+5], sum[N*16+5], lazy[N*16+5];
void build(int o, int l, int r) {
if (l == r) {sgm[o] = sum[o] = cost[l]; return; }
int mid = (l+r)>>1;
build(lr(o), l, mid); build(rr(o), mid+1, r);
sum[o] = sum[lr(o)]+sum[rr(o)];
sgm[o] = sgm[lr(o)]+sgm[rr(o)];
}
void pushdown(int o) {
if (lazy[o] == -1) sgm[lr(o)] = sgm[rr(o)] = 0, lazy[lr(o)] = lazy[rr(o)] = -1;
else sgm[lr(o)] = sum[lr(o)], sgm[rr(o)] = sum[rr(o)], lazy[lr(o)] = lazy[rr(o)] = 1;
lazy[o] = 0;
}
void update(int o, int l, int r, int a, int b, int val) {
if (a <= l && r <= b) {
if (val == 1) sgm[o] = 0, lazy[o] = -1;
else sgm[o] = sum[o], lazy[o] = 1;
return;
}
if (lazy[o]) pushdown(o); int mid = (l+r)>>1;
if (a <= mid) update(lr(o), l, mid, a, b, val);
if (b > mid) update(rr(o), mid+1, r, a, b, val);
sgm[o] = sgm[lr(o)]+sgm[rr(o)];
}
}T;
void work() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", &a[i].l, &a[i].r, &a[i].id);
b[++tot] = a[i].l, b[++tot] = a[i].r;
}
sort(b+1, b+tot+1); tot = unique(b+1, b+tot+1)-b-1;
if (b[1] != 1) ++pos, cost[pos] = b[1]-1;
for (int i = 1; i < tot; i++) {
id[i] = ++pos, cost[pos] = 1;
if (b[i]+1 != b[i+1]) ++pos, cost[pos] = b[i+1]-b[i]-1;
}
id[tot] = ++pos, cost[pos] = 1;
if (b[tot] != n) ++pos, cost[pos] = n-b[tot];
T.build(1, 1, pos);
for (int i = 1; i <= m; i++) {
int l = id[lower_bound(b+1, b+tot+1, a[i].l)-b], r = id[lower_bound(b+1, b+tot+1, a[i].r)-b];
T.update(1, 1, pos, l, r, a[i].id);
printf("%d
", T.sgm[1]);
}
}
int main() {work(); return 0; }