福田网站建设多少钱,外贸国际站有哪些平台,安徽省建设干部学校网站关停,中国大连网站线段树合并
前置知识#xff1a;权值线段树、动态开点
将两棵线段树的信息合并成一棵线段树。 可以新建一颗线段树保存原来两颗线段树的信息#xff0c;也可以将第二棵线段树维护的信息加到第一棵线段树上。
前者的空间复杂度较高#xff0c;如果合并之前的线段树不会再用…线段树合并
前置知识权值线段树、动态开点
将两棵线段树的信息合并成一棵线段树。 可以新建一颗线段树保存原来两颗线段树的信息也可以将第二棵线段树维护的信息加到第一棵线段树上。
前者的空间复杂度较高如果合并之前的线段树不会再用到的话可以将第二颗线段树的信息加到第一棵线段树上。
P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并
题意
一棵树有 n n n 个点。每次操作 ( x , y , z ) (x,y,z) (x,y,z) 在路径 ( x , y ) (x,y) (x,y) 上的每一个点放一个救济粮 z z z。询问每个点存放最多的是哪种救济粮
解析
对于树上一条路径上的点进行相同的操作可以想到树上差分。
然后统计每个点最多的东西可以用权值线段树维护每种救济粮的数目。
因为将发放救济粮转化成树上差分求答案的时候需要合并所以从下向上合并线段树。
代码
#includebits/stdc.h
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
#define debug(x) cerr #x : (x) endl
#define rep(i, a, b) for(int i (a); i (b); i)
const int maxn 1e510;
const int maxm 1e510;
const int INF 0x3f3f3f3f;
typedef pairint, int pii;int head[maxn], tot;
struct edge{int to, nxt;
}e[maxn 1];
struct node{int mcnt, id;int ls, rs;
}t[maxn * 60];
struct query{int x, y, z;
}q[maxn];int cnt;
int n, m, MAX;
int rt[maxn], ans[maxn];
void add(int a, int b){e[tot].nxt head[a];e[tot].to b;head[a] tot;
}
int dep[maxn], siz[maxn], top[maxn], son[maxn], fa[maxn];
void dfs1(int u, int p){dep[u] dep[p] 1;siz[u] 1;fa[u] p;for(int i head[u]; i; i e[i].nxt){int v e[i].to;if(v p)continue;dfs1(v, u);siz[u] siz[v];if(siz[v] siz[son[u]])son[u] v;}
}
void dfs2(int u, int tp){top[u] tp;if(son[u])dfs2(son[u], tp);for(int i head[u]; i; i e[i].nxt){int v e[i].to;if(v fa[u] || v son[u])continue;dfs2(v, v);}
}
int LCA(int u, int v){while(top[u] ! top[v]){if(dep[top[u]] dep[top[v]])swap(u, v);u fa[top[u]];}return dep[u] dep[v] ? u : v;
}
void pushup(int k){if(t[t[k].ls].mcnt t[t[k].rs].mcnt){t[k].mcnt t[t[k].ls].mcnt;t[k].id t[t[k].ls].id;}else{t[k].mcnt t[t[k].rs].mcnt;t[k].id t[t[k].rs].id;}
}
void update(int k, int l, int r, int pos, int v){if(k 0)k cnt;if(l r l pos){t[k].mcnt v;t[k].id l;return;}int mid (lr) 1;if(pos mid)update(t[k].ls, l, mid, pos, v);elseupdate(t[k].rs, mid1, r, pos, v);pushup(k);
}
void merge(int a, int b, int l, int r){if(!a || !b){a (!a ? b : a);return;} if(l r){t[a].mcnt t[b].mcnt;t[a].id l;return;}int mid (lr) 1;merge(t[a].ls, t[b].ls, l, mid);merge(t[a].rs, t[b].rs, mid1, r);pushup(a);
}
void dfs(int u){for(int i head[u]; i; i e[i].nxt){int v e[i].to;if(v fa[u])continue;dfs(v);merge(rt[u], rt[v], 1, MAX);}if(t[rt[u]].mcnt ! 0)ans[u] t[rt[u]].id;
}
int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin n m;for(int i 1, u, v; i n; i){cin u v;add(u, v);add(v, u);}dfs1(1, 0);dfs2(1, 1);for(int i 1; i m; i){cin q[i].x q[i].y q[i].z;MAX max(MAX, q[i].z);}for(int i 1; i m; i){int u q[i].x, v q[i].y;int w q[i].z;int lca LCA(u, v);update(rt[u], 1, MAX, w, 1);update(rt[v], 1, MAX, w, 1);update(rt[lca], 1, MAX, w, -1);if(fa[lca])update(rt[fa[lca]], 1, MAX, w, -1);}dfs(1);for(int i 1; i n; i)cout ans[i] endl;return 0;
} P1600 [NOIP2016 提高组] 天天爱跑步
题意
一棵 n n n 节点的树有 m m m 条路径每个节点有参数 w i w_i wi。询问有多少条路径的第 w i 1 w_i1 wi1 个点是节点 i i i。
解析
对于每条路径 ( s , t ) (s, t) (s,t)可以分成两条路径 ( s , l c a ) (s,lca) (s,lca) 和 ( l c a , t ) (lca,t) (lca,t)如果模拟这个过程的话时间复杂度为 O ( n m ) O(nm) O(nm) 不能接受。
换个角度考虑对于每个点有多少条路径会对该点产生贡献。
设节点 i i i 的深度为 d e p i dep_i depi
设路径 ( s , t ) (s,t) (s,t) 对节点 u u u 产生贡献。 u u u 在 ( s , l c a ) (s,lca) (s,lca) 上。 d e p s − d e p u w u dep_s-dep_u w_u deps−depuwu u u u 在 ( l c a , t ) (lca, t) (lca,t) 上。 d e p s d e p u − 2 d e p l c a w u dep_sdep_u-2dep_{lca} w_u depsdepu−2deplcawu
即满足条件的路径会对节点 u u u 有贡献。
考虑树上差分在 s s s 插入 d e p s dep_s deps在 t t t 处插入 2 d e p l c a − d e p s 2dep_{lca}-dep_s 2deplca−deps在 l c a lca lca 处插入 − d e p s -dep_s −deps在 f a ( l c a ) fa(lca) fa(lca) 处插入 d e p s − 2 d e p l c a dep_s-2dep_{lca} deps−2deplca。后两者可以交换然后线段树合并即可。
代码
#includebits/stdc.h
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
#define debug(x) cerr #x : (x) endl
#define rep(i, a, b) for(int i (a); i (b); i)
const int maxn 3e510;
const int maxm 1e510;
const int INF 0x3f3f3f3f;
typedef pairint, int pii;int head[maxn], cnt;
struct edge{int to, nxt;
}e[maxn 1];
struct node{int v;int ls, rs;
}t[maxn * 60];
int n, m;
int rt[maxn], MAX, ans[maxn], w[maxn], tot;
void add(int a, int b){e[cnt].nxt head[a];e[cnt].to b;head[a] cnt;
}
int siz[maxn], son[maxn], dep[maxn], fa[maxn], top[maxn];
void dfs1(int u, int p){dep[u] dep[p]1;siz[u] 1;fa[u] p;for(int i head[u]; i; i e[i].nxt){int v e[i].to;if(v p)continue;dfs1(v, u);siz[u] siz[v]; if(siz[v] siz[son[u]])son[u] v;}
}
void dfs2(int u, int tp){top[u] tp;if(son[u])dfs2(son[u], tp);for(int i head[u]; i; i e[i].nxt){int v e[i].to;if(v son[u] || v fa[u])continue;dfs2(v, v);}
}
int LCA(int u, int v){while(top[u] ! top[v]){if(dep[top[u]] dep[top[v]])swap(u, v);u fa[top[u]];}return dep[u] dep[v] ? u : v;
}
void update(int k, int l, int r, int pos, int v){if(k 0)k tot;if(l r l pos){t[k].v v;return;}int mid (lr) 1;if(pos mid)update(t[k].ls, l, mid, pos, v);elseupdate(t[k].rs, mid1, r, pos, v);return;
}
void merge(int a, int b, int l, int r){if(!a || !b){a (!a ? b : a);return;}if(l r){t[a].v t[b].v;return;}int mid (lr) 1;merge(t[a].ls, t[b].ls, l, mid);merge(t[a].rs, t[b].rs, mid1, r);
}
int query(int k, int l, int r, int pos){if(!k)return 0;if(l r)return t[k].v;int mid (lr) 1;if(pos mid)return query(t[k].ls, l, mid, pos);elsereturn query(t[k].rs, mid1, r, pos);
}
void dfs(int u){for(int i head[u]; i; i e[i].nxt){int v e[i].to;if(v fa[u])continue;dfs(v);merge(rt[u], rt[v], 1, MAX);}if(w[u] n dep[u] w[u] MAX)ans[u] query(rt[u], 1, MAX, n dep[u] w[u]);ans[u] query(rt[u], 1, MAX, n dep[u] - w[u]);}int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin n m;MAX n 1;int u, v;for(int i 1; i n; i){cin u v;add(u, v);add(v, u);}dfs1(1, 0);dfs2(1, 1);for(int i 1; i n; i)cin w[i];for(int i 1; i m; i){cin u v;int lca LCA(u, v);update(rt[u], 1, MAX, n dep[u], 1);update(rt[v], 1, MAX, n dep[lca] * 2 - dep[u], 1);update(rt[lca], 1, MAX, n dep[u], -1);update(rt[fa[lca]], 1, MAX, n dep[lca] * 2 - dep[u], -1);}dfs(1);for(int i 1; i n; i)cout ans[i] ;cout endl;return 0;
} P3224 [HNOI2012]永无乡
题意
有 n n n 个节点每个节点有互不相同的重要程度。两种操作
在 ( x , y ) (x,y) (x,y) 之间建桥询问与节点 x x x 所在连通块中重要程度排名第 k k k 小的节点编号
解析
查询第 k k k 小考虑权值线段树维护联通性考虑并查集。在合并两个连通块时也合并权值线段树
代码
#includebits/stdc.h
using namespace std;
typedef long long ll;
typedef double db;
#define fi first
#define se second
#define debug(x) cerr #x : (x) endl
#define rep(i, a, b) for(int i (a); i (b); i)
const int maxn 3e510;
const int maxm 1e510;
const int INF 0x3f3f3f3f;
typedef pairint, int pii;struct node{int sum, id;int ls, rs;
}t[maxn * 60];
int rt[maxn];
int tot, n, m, q;
int fa[maxn];
int find(int x){return fa[x] x ? x : fa[x] find(fa[x]);
}
int pushup(int k){t[k].sum t[t[k].ls].sum t[t[k].rs].sum;
}
void update(int k, int l, int r, int pos, int idx){if(k 0)k tot;if(l r){t[k].sum;t[k].id idx;return;}int mid (lr) 1;if(pos mid)update(t[k].ls, l, mid, pos, idx);elseupdate(t[k].rs, mid1, r, pos, idx);pushup(k);
}
void merge(int a, int b, int l, int r){if(!a || !b){a (a 0 ? b : a);return;}if(l r){t[a].sum t[b].sum;return;}int mid (lr) 1;merge(t[a].ls, t[b].ls, l, mid);merge(t[a].rs, t[b].rs, mid1, r);pushup(a);
}
int query(int a, int k, int l, int r){if(t[a].sum k || !a)return 0;if(l r)return t[a].id;int mid (lr) 1;int ans 0;if(k t[t[a].ls].sum)ans query(t[a].ls, k, l, mid);elseans query(t[a].rs, k-t[t[a].ls].sum, mid1, r);return ans;
}
int main(){ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin n m;for(int i 1, p; i n; i){fa[i] i;cin p;update(rt[i], 1, n, p, i);}for(int i 1, x, y; i m; i){cin x y;int fx find(x);int fy find(y);fa[fy] fx;merge(rt[fx], rt[fy], 1, n);}cin q;string op;for(int i 1, x, y; i q; i){cin op x y;if(op B){int fx find(x);int fy find(y);if(fx fy)continue;fa[fy] fx;merge(rt[fx], rt[fy], 1, n); }else if(op Q){int fx find(x);int res query(rt[fx], y, 1, n);if(res 0)cout -1 endl;elsecout res endl;}} return 0;
}
