热门搜索： 个人免签支付 素材网站源码 图片素材站源码 游戏源码 js广告 jquery选项卡 jQuery导航
2020-12-13 15:19
标签：blog io os for sp div on log ad 点更新，区间询问和，最基础的树链剖分。 #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define lson rt siz[maxson[now]]) { maxson[now] = v[i]; } } } //第二遍dfs， 划分链 void dfs2(int now, int tp) { top[now] = tp; tid[now] = ++idcnt; //遇到叶子节点就返回 if(maxson[now] == -1) return; //重链直接dfs下去 dfs2(maxson[now], tp); for(int i = head[now]; ~i; i = nxt[i]) if(v[i] != fa[now]) { //剩下的每一个节点都自己成为一条链 if(v[i] != maxson[now]) dfs2(v[i], v[i]); } } //线段树操作 void pushup(int rt) { sumv[rt] = sumv[rt > 1; if(l == r) sumv[rt] = sval[l]; else { build(lson); build(rson); pushup(rt); } } void update(int rt, int l, int r, int pos, int val) { if(l == r) sumv[rt] = val; else { int mid = (l + r) >> 1; if(pos = r) return sumv[rt]; int mid = (l + r) >> 1, ret = 0; if(ql mid) ret += query(rson, ql, qr); return ret; } int ask(int x, int y) { int ret = 0; while(top[x] != top[y]) { // printf("%d %d %d %d\n", x, y, top[x], top[y]); if(dep[top[x]] dep[y]) swap(x, y); if(x != y) ret += query(1, 1, n, tid[x] + 1, tid[y]); return ret; } int main() { while(scanf("%d%d%d", &n, &q, &s) != EOF) { init(); for(int i = 1; i dep[v[i]]) { sval[tid[u[i]]] = w[i]; rnum[eid[i]] = u[i]; } else { sval[tid[v[i]]] = w[i]; rnum[eid[i]] = v[i]; } } build(1, 1, idcnt); int cmd, v1, v2; for(int i = 0; i POJ 2763 Housewife Wind 树链剖分 标签：blog io os for sp div on log ad 原文地址：http://www.cnblogs.com/rolight/p/4074756.html
标签：blog io os for sp div on log ad
点更新，区间询问和，最基础的树链剖分。
#include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define lson rt siz[maxson[now]]) { maxson[now] = v[i]; } } } //第二遍dfs， 划分链 void dfs2(int now, int tp) { top[now] = tp; tid[now] = ++idcnt; //遇到叶子节点就返回 if(maxson[now] == -1) return; //重链直接dfs下去 dfs2(maxson[now], tp); for(int i = head[now]; ~i; i = nxt[i]) if(v[i] != fa[now]) { //剩下的每一个节点都自己成为一条链 if(v[i] != maxson[now]) dfs2(v[i], v[i]); } } //线段树操作 void pushup(int rt) { sumv[rt] = sumv[rt > 1; if(l == r) sumv[rt] = sval[l]; else { build(lson); build(rson); pushup(rt); } } void update(int rt, int l, int r, int pos, int val) { if(l == r) sumv[rt] = val; else { int mid = (l + r) >> 1; if(pos = r) return sumv[rt]; int mid = (l + r) >> 1, ret = 0; if(ql mid) ret += query(rson, ql, qr); return ret; } int ask(int x, int y) { int ret = 0; while(top[x] != top[y]) { // printf("%d %d %d %d\n", x, y, top[x], top[y]); if(dep[top[x]] dep[y]) swap(x, y); if(x != y) ret += query(1, 1, n, tid[x] + 1, tid[y]); return ret; } int main() { while(scanf("%d%d%d", &n, &q, &s) != EOF) { init(); for(int i = 1; i dep[v[i]]) { sval[tid[u[i]]] = w[i]; rnum[eid[i]] = u[i]; } else { sval[tid[v[i]]] = w[i]; rnum[eid[i]] = v[i]; } } build(1, 1, idcnt); int cmd, v1, v2; for(int i = 0; i
POJ 2763 Housewife Wind 树链剖分
原文地址：http://www.cnblogs.com/rolight/p/4074756.html
上一篇：Java对String类型的时间进行加减操作
下一篇：浅谈c++ new、delete与malloc和free