BalanceSegment @ 2023-07-25 14:28:40
板子是直接从上一题改过来的,所以一些写法很怪。
不知道是不是写法的原因。
#include <bits/stdc++.h>
#define lc id << 1
#define rc id << 1 | 1
using namespace std;
const int maxn = 2e5 + 10;
int h[maxn * 2], nxt[maxn * 2], to[maxn * 2], w[maxn * 2];
int st[maxn], ed[maxn];
int dfn[maxn], top[maxn], siz[maxn];
int fa[maxn], son[maxn], va[maxn], val[maxn], dep[maxn];
int n, m, cnt, cur;
void add(int u, int v, int val) {
to[++cnt] = v;
nxt[cnt] = h[u];
h[u] = cnt;
w[cnt] = val;
}
void dfs1(int x, int f){
fa[x] = f;
siz[x] = 1;
dep[x] = dep[f] + 1;
int sz = -1;
for(int i = h[x]; i; i = nxt[i]) {
int v = to[i];
if(v == f) continue;
va[v] = w[i];
dfs1(v, x);
siz[x] += siz[v];
if(sz < siz[v])
sz = siz[v], son[x] = v;
}
}
void dfs2(int x, int t) {
top[x] = t;
dfn[x] = ++cur;
val[cur] = va[x];
if(!son[x]) return;
dfs2(son[x], t);
for(int i = h[x]; i; i = nxt[i]) {
int v = to[i];
if(v == fa[x] || v == son[x])
continue;
dfs2(v, v);
}
}
struct Seg {
struct node{
int l, r;
int sum, laz;
}a[maxn * 4];
void maintain(int id) {
a[id].sum = a[lc].sum + a[rc].sum;
}
void maketag(int id) {
a[id].laz = 1;
a[id].sum += (a[id].r - a[id].l + 1);
}
void pushdown(int id) {
if(!a[id].laz) return;
maketag(lc);
maketag(rc);
a[id].laz = 0;
}
void build(int id, int l, int r) {
a[id].l = l;
a[id].r = r;
if(l == r) {
a[id].sum = 0;
return;
}
int mid = (l + r) >> 1;
build(lc, l, mid);
build(rc, mid + 1, r);
maintain(id);
}
void modify(int id, int l, int r) {
if(a[id].l >= l && a[id].r <= r) {
maketag(id);
return;
}
pushdown(id);
int mid = (a[id].l + a[id].r) >> 1;
if(l <= mid) modify(lc, l, r);
if(mid < r) modify(rc, l, r);
maintain(id);
}
int qsum(int id, int l, int r) {
if(a[id].l >= l && a[id].r <= r)
return a[id].sum;
pushdown(id);
int ret = 0;
int mid = (a[id].l + a[id].r) >> 1;
if(l <= mid) ret += qsum(lc, l, r);
if(mid < r) ret += qsum(rc, l, r);
return ret;
}
}T;
int getsum(int x, int y) {
int ret = 0;
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]])
swap(x, y);
ret += T.qsum(1, dfn[top[x]], dfn[x]);
x = fa[top[x]];
}
if(dep[x] < dep[y]) swap(x, y);
ret += T.qsum(1, dfn[y] + 1, dfn[x]);
return ret;
}
void change(int x, int y) {
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]])
swap(x, y);
T.modify(1, dfn[top[x]], dfn[x]);
x = fa[top[x]];
}
if(dep[x] < dep[y]) swap(x, y);
T.modify(1, dfn[y] + 1, dfn[x]);
}
int main() {
char opt;
cin >> n >> m;
for(int i = 1, u, v; i < n; i++) {
cin >> u >> v;
add(u, v, 0);
add(v, u, 0);
}
dfs1(1, 0);
dfs2(1, 1);
T.build(1, 1, n);
int u, v;
while(m--){
cin >> opt >> u >> v;
if(opt == 'P') change(u, v);
if(opt == 'Q') cout << getsum(u, v) << endl;
}
return 0;
}
by MAZHIYUAN @ 2023-11-16 16:31:02
void maketag(int id) {
a[id].laz = 1;
a[id].sum += (a[id].r - a[id].l + 1);
}
应该改为
void maketag(int id) {
a[id].laz += 1;
a[id].sum += (a[id].r - a[id].l + 1);
}
因为懒标记可能被更新不止一次
附hack数据
in
6 3
1 2
1 3
3 4
4 5
5 6
P 3 6
P 3 6
Q 5 6
out
2
by MAZHIYUAN @ 2023-11-16 17:00:50
还有pushdown不能共用maketag函数,应改为
void pushdown(int id) {
if(!a[id].laz) return;
a[lc].sum += (a[lc].r - a[lc].l + 1) * a[id].laz;
a[rc].sum += (a[rc].r - a[rc].l + 1) * a[id].laz;
a[lc].laz += a[id].laz;
a[rc].laz += a[id].laz;
a[id].laz = 0;
}
改完就过了