热门搜索： 个人免签支付 素材网站源码 图片素材站源码 游戏源码 js广告 jquery选项卡 jQuery导航
2020-12-13 15:45
标签：style blog io color os for sp div on 边查询，点更新的模板题。 #include #include #include #include #include #includeusing namespace std; typedef long long LL; const int maxn = 222222; struct Node { int to;int next; }e[maxn*2]; #define lson l,mid,rt#define rson mid+1,r,rtint head[maxn]; int son[maxn]; int top[maxn]; int father[maxn]; int deep[maxn]; int len;int z; int size[maxn]; int pos[maxn]; int sum[maxn2]; void add(int from, int to) { e[len].to = to; e[len].next = head[from]; head[from] = len++; } int edge[maxn][10]; void init(int x) { son[x] = 0; size[x] = 1; for (int i = head[x]; i != -1; i = e[i].next){ int cc = e[i].to; if (cc == father[x]) continue; deep[cc] = deep[x] + 1; father[cc] = x; init(cc); size[x] += size[cc]; if (size[son[x]] cc; } } void dfs(int x, int tp) { pos[x] = ++z;top[x] = tp; if (son[x]) dfs(son[x], tp); for (int i = head[x]; i != -1; i = e[i].next){ int cc = e[i].to; if (cc == father[x] || cc == son[x]) continue; dfs(cc, cc); } } void up(int rt) { sum[rt] = sum[rt 1] + sum[rt 1 | 1]; } void update(int key, int ans, int l, int r, int rt) { if (l == r){ sum[rt] = ans; return; } int mid = (l + r) >> 1; if (key mid) update(key, ans, lson); else update(key, ans, rson); up(rt); } int ask(int L, int R, int l, int r, int rt) { if (L return sum[rt]; int mid = (l + r) >> 1; int ans = 0; if (L ask(L, R, lson); if (R > mid) ans += ask(L, R, rson); return ans; } int gao(int x, int y) { int ans = 0; int fx = top[x]; int fy = top[y]; while (fx != fy){ if (deep[fx] deep[fy]){ swap(fx, fy); swap(x, y); } ans += ask(pos[fx], pos[x], 1, z, 1); x = father[fx]; fx = top[x]; } if (x == y) return ans; if (deep[x]>deep[y]) swap(x, y); ans += ask(pos[x] + 1, pos[y], 1, z, 1); return ans; } int main() { int n,q,s; int a,b,c; while (cin >> n >> q >> s){ memset(sum,0,sizeof(sum)); len = 0;z =0; memset(head,-1,sizeof(head)); deep[s]=1 ; for (int i = 1; i ){ scanf("%d%d%d", &edge[i][0], &edge[i][1], &edge[i][2]); add(edge[i][0], edge[i][1]); add(edge[i][1], edge[i][0]); } init(1); dfs(1, 1); for (int i = 1; i ){ int a = edge[i][0]; int b = edge[i][1]; int c = edge[i][2]; if (deep[a]>deep[b]) swap(edge[i][0], edge[i][1]); update(pos[edge[i][1]], c, 1, z, 1); } while (q--){ scanf("%d", &a); if (a == 0){ scanf("%d", &b); int t = gao(b, s); cout endl; s = b; } else { scanf("%d%d", &b, &c); edge[b][2] = c; update(pos[edge[b][1]], c, 1, z, 1); } } } return 0; } Poj2763Housewife Wind树链剖分 标签：style blog io color os for sp div on 原文地址：http://www.cnblogs.com/yigexigua/p/4076521.html
标签：style blog io color os for sp div on
边查询，点更新的模板题。
#include #include #include #include #include #includeusing namespace std; typedef long long LL; const int maxn = 222222; struct Node { int to;int next; }e[maxn*2]; #define lson l,mid,rt#define rson mid+1,r,rtint head[maxn]; int son[maxn]; int top[maxn]; int father[maxn]; int deep[maxn]; int len;int z; int size[maxn]; int pos[maxn]; int sum[maxn2]; void add(int from, int to) { e[len].to = to; e[len].next = head[from]; head[from] = len++; } int edge[maxn][10]; void init(int x) { son[x] = 0; size[x] = 1; for (int i = head[x]; i != -1; i = e[i].next){ int cc = e[i].to; if (cc == father[x]) continue; deep[cc] = deep[x] + 1; father[cc] = x; init(cc); size[x] += size[cc]; if (size[son[x]] cc; } } void dfs(int x, int tp) { pos[x] = ++z;top[x] = tp; if (son[x]) dfs(son[x], tp); for (int i = head[x]; i != -1; i = e[i].next){ int cc = e[i].to; if (cc == father[x] || cc == son[x]) continue; dfs(cc, cc); } } void up(int rt) { sum[rt] = sum[rt 1] + sum[rt 1 | 1]; } void update(int key, int ans, int l, int r, int rt) { if (l == r){ sum[rt] = ans; return; } int mid = (l + r) >> 1; if (key mid) update(key, ans, lson); else update(key, ans, rson); up(rt); } int ask(int L, int R, int l, int r, int rt) { if (L return sum[rt]; int mid = (l + r) >> 1; int ans = 0; if (L ask(L, R, lson); if (R > mid) ans += ask(L, R, rson); return ans; } int gao(int x, int y) { int ans = 0; int fx = top[x]; int fy = top[y]; while (fx != fy){ if (deep[fx] deep[fy]){ swap(fx, fy); swap(x, y); } ans += ask(pos[fx], pos[x], 1, z, 1); x = father[fx]; fx = top[x]; } if (x == y) return ans; if (deep[x]>deep[y]) swap(x, y); ans += ask(pos[x] + 1, pos[y], 1, z, 1); return ans; } int main() { int n,q,s; int a,b,c; while (cin >> n >> q >> s){ memset(sum,0,sizeof(sum)); len = 0;z =0; memset(head,-1,sizeof(head)); deep[s]=1 ; for (int i = 1; i ){ scanf("%d%d%d", &edge[i][0], &edge[i][1], &edge[i][2]); add(edge[i][0], edge[i][1]); add(edge[i][1], edge[i][0]); } init(1); dfs(1, 1); for (int i = 1; i ){ int a = edge[i][0]; int b = edge[i][1]; int c = edge[i][2]; if (deep[a]>deep[b]) swap(edge[i][0], edge[i][1]); update(pos[edge[i][1]], c, 1, z, 1); } while (q--){ scanf("%d", &a); if (a == 0){ scanf("%d", &b); int t = gao(b, s); cout endl; s = b; } else { scanf("%d%d", &b, &c); edge[b][2] = c; update(pos[edge[b][1]], c, 1, z, 1); } } } return 0; }
Poj2763Housewife Wind树链剖分
原文地址：http://www.cnblogs.com/yigexigua/p/4076521.html
上一篇：Java 之 函数式接口
下一篇：apache在window server 2003下的安全配置