首页 > 代码库 > POJ3237-Tree （树链剖分，线段树区间更新+点更新+区间查询）
POJ3237-Tree （树链剖分，线段树区间更新+点更新+区间查询）
两个更新操作，一个将第i条路径权值改为w，一个是将a-b之间所有路径权值取反。
一个查询操作，求a-b之间路径中权值最大的边。
很容易想到维护一个最大最小值，取反就是把最大最小取反交换一下。
开始遇到一个问题就是我把根节点赋值0，上一道题求和没问题，但是这道题会出问题，于是线段树建树的时候从2开始建的，第一次尝试这么写，不过也没什么问题。
wa了一天。。。。
一开始的错是pushdown的时候没有把子节点的fg更新，于是我改了fg[lson]=fg[rson]=1。。。。。。。。
就这样。。。。我对着这份代码看了几个小时。。。。。找数据。。。后来自己写了发对拍。。。。
后来终于忍不了了。。。。找了别人的代码。。。。
哦，应该是fg[lson] ^= 1; fg[rson] ^= 1;
我果然不会线段树。。。。。
mdzz
#include <algorithm>#include <cstring>#include <cstdio>#include <iostream>using namespace std;const int N = 100005;//struct Edge { int to, next, cost, id;} edge[N*2];int head[N], cntE;void addedge(int u, int v, int w, int id) { edge[cntE].to = v; edge[cntE].next = head[u]; edge[cntE].cost = w; edge[cntE].id = id; head[u] = cntE++; edge[cntE].to = u; edge[cntE].next = head[v]; edge[cntE].cost = w; edge[cntE].id = id; head[v] = cntE++;}//int dep[N], sz[N], fa[N], son[N], son_cost[N];int road[N];void dfs1(int u, int par, int d) { dep[u] = d; sz[u] = 1; fa[u] = par; for (int i = head[u]; ~i; i = edge[i].next) { int v = edge[i].to; if (v != par) { road[edge[i].id] = v; dfs1(v, u, d+1); sz[u] += sz[v]; if (son[u] == -1 || sz[v] > sz[son[u]]) { son[u] = v; son_cost[u] = edge[i].cost; } } }}int top[N], dfn[N], rk[N], idx;int a[N];void dfs2(int u, int rt, int cost) { top[u] = rt; dfn[u] = ++idx; a[idx] = cost; if (son[u] == -1) return; dfs2(son[u], rt, son_cost[u]); for (int i = head[u]; ~i; i = edge[i].next) { int v = edge[i].to; if (v != fa[u] && v != son[u]) dfs2(v, v, edge[i].cost); }}//int mx[N<<2], fg[N<<2], mi[N<<2];#define lson o<<1#define rson o<<1|1void pushdown(int o) { if (fg[o]) { fg[lson] ^= 1; fg[rson] ^= 1; int tmp = mx[lson]; mx[lson] = -mi[lson]; mi[lson] = -tmp; tmp = mx[rson]; mx[rson] = -mi[rson]; mi[rson] = -tmp; fg[o] = 0; }}void pushup(int o) { mx[o] = max(mx[lson], mx[rson]); mi[o] = min(mi[lson], mi[rson]);}void build(int o, int l, int r) { fg[o] = 0; if (l == r) { mx[o] = a[l]; mi[o] = a[l]; } else { int mid = (l+r) >> 1; build(lson, l, mid); build(rson, mid+1, r); pushup(o); }}void CHANGE(int o, int l, int r, int v, int w) { if (l == r) { mi[o] = mx[o] = w; } else { pushdown(o); int mid = (l + r) >> 1; if (mid >= v) CHANGE(lson, l, mid, v, w); else CHANGE(rson, mid+1, r, v, w); pushup(o); }}void nega(int o, int l, int r, int L, int R) { if (l >= L && r <= R) { fg[o] ^= 1; int tmp = mx[o]; mx[o] = -mi[o]; mi[o] = -tmp; return; } pushdown(o); int mid = (l+r) >> 1; if (mid >= L) nega(lson, l, mid, L, R); if (mid < R) nega(rson, mid+1, r, L, R); pushup(o);}void NEGATE(int x, int y, int n) { while (top[x] != top[y]) { if (dep[top[x]] < dep[top[y]]) swap(x, y); nega(1, 2, n, dfn[top[x]], dfn[x]); x = fa[top[x]]; } if (x == y) return ; if (dep[x] > dep[y]) swap(x, y); nega(1, 2, n, dfn[son[x]], dfn[y]);}int query(int o, int l ,int r, int L, int R) { if (l >= L && r <= R) { return mx[o]; } pushdown(o); int mid = (l+r) >> 1; int ans = -(1<<30); if (L <= mid) ans = max(ans, query(lson, l, mid, L, R)); if (R > mid) ans = max(ans, query(rson, mid+1, r, L, R)); pushup(o); return ans;}int QUERY(int x, int y, int n) { if (x == y) return 0; int ans = -(1<<30); while (top[x] != top[y]) { if (dep[top[x]] < dep[top[y]]) swap(x, y); ans = max(ans, query(1, 2, n, dfn[top[x]], dfn[x])); x = fa[top[x]]; } if (x == y) return ans; if (dep[x] > dep[y]) swap(x, y); ans = max(ans, query(1, 2, n, dfn[son[x]], dfn[y])); // 注意这里是son[x] return ans;}void init() { idx = cntE = 0; memset(head, -1, sizeof head); memset(son, -1, sizeof son);}// 区间更新 点更新 区间查询int main() { int n, T; scanf("%d",&T); int cas = 0; while (T--) { scanf("%d", &n); init(); int u, v, w; for (int i = 1; i < n; ++i) scanf("%d%d%d", &u, &v, &w), addedge(u, v, w, i); dfs1(1, 0, 0); dfs2(1, 1, 0); build(1, 2, n); char op[10]; while (~scanf("%s", op)) { if (*op == ‘D‘) break; scanf("%d%d", &u, &v); if (*op == ‘Q‘) printf("%d\n", QUERY(u, v, n)); else if (*op == ‘C‘) CHANGE(1, 2, n, dfn[road[u]], v); else NEGATE(u, v, n); } } return 0;}
一组数据
/**
2
7
1 2 1
2 3 7
3 4 8
4 5 6
5 6 9
6 7 1
N 4 7
C 2 3
N 1 7
C 2 7
N 1 5
C 4 7
D
6
1 2 8
2 3 8
3 4 7
4 5 2
5 6 10
N 6 1
C 1 2
N 3 6
N 4 1
N 1 6
Q 2 6
D
Output:
8
1
7
8
10
-10
7
*/
POJ3237-Tree （树链剖分，线段树区间更新+点更新+区间查询）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。