2020-2021:teams:legal_string:jxm2001:contest:ccpc_wannafly_winter_camp_day5
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:jxm2001:contest:ccpc_wannafly_winter_camp_day5 [2021/05/26 21:35] jxm2001 |
2020-2021:teams:legal_string:jxm2001:contest:ccpc_wannafly_winter_camp_day5 [2021/05/27 16:07] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 2: | 行 2: | ||
| [[https://ac.nowcoder.com/acm/contest/4120|比赛链接]] | [[https://ac.nowcoder.com/acm/contest/4120|比赛链接]] | ||
| + | |||
| + | ===== B. Bitset Master ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给定 $n$ 阶树和 $m$ 个操作。每个点 $u$ 维护一个集合 $S(u)$，初始时 $S(u)=\{u\}$。 | ||
| + | |||
| + | 每次操作选定一条树边 $u\to v$，令 $S(u)=S(v)=\text{\old}(S(u)\cup S(v))$。 | ||
| + | |||
| + | 对每个 $u$，输出有多少个 $v$ 满足 $u\in S(v)$。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 设 $m$ 次操作选择的边为 $e_1,e_2\cdots e_m$。观察 $u\in S(v)$，这等价于序列 $\{e\}$ 中存在某个子序列 $e_{p_1},e_{p_2}\cdots e_{p_k}$ 恰好是连接 $u,v$ 的路径。 | ||
| + | |||
| + | 如果逆序操作，即序列变为 $e_{p_k},e_{p_{k-1}}\cdots e_{p_1}$，则有 $v\in S(u)$。 | ||
| + | |||
| + | 于是正序操作 $\sum_{v=1}^n [u\in S(v)]=$ 逆序操作 $\sum_{v=1}^n [v\in S(u)]=$ 逆序操作 $|S(u)|$。 | ||
| + | |||
| + | 接下来考虑怎样维护 $|S(u)|$。根据容斥定理，有 $|S(u)\cup S(v)|=|S(u)|+|S(v)|-|S(u)\cap S(V)|$。 | ||
| + | |||
| + | 对 $t\in S(u)\cap S(v)$，由于树形结构约束，必存在子序列 $e_{p_1},e_{p_2}\cdots e_{p_k}$ 代表路径 $k\to \cdots v\to u$ 或 $k\to \cdots u\to v$。 | ||
| + | |||
| + | 于是不难发现 $|S(u)\cap S(V)|$ 恰好为上次合并 $S(u),S(v)$ 的结果，维护一下即可。时间复杂度 $O(n+m)$。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=5e5+5; | ||
| + | struct Edge{ | ||
| + | int u,v,w; | ||
| + | }edge[MAXN]; | ||
| + | int c[MAXN],p[MAXN]; | ||
| + | int main() | ||
| + | { | ||
| + | int n=read_int(),m=read_int(); | ||
| + | _rep(i,1,n)c[i]=1; | ||
| + | _for(i,1,n){ | ||
| + | int u=read_int(),v=read_int(); | ||
| + | edge[i]=Edge{u,v,0}; | ||
| + | } | ||
| + | _for(i,0,m) | ||
| + | p[i]=read_int(); | ||
| + | for(int i=m-1;i>=0;i--){ | ||
| + | int u=edge[p[i]].u,v=edge[p[i]].v,cc=c[u]+c[v]-edge[p[i]].w; | ||
| + | c[u]=cc,c[v]=cc,edge[p[i]].w=cc; | ||
| + | } | ||
| + | _rep(i,1,n) | ||
| + | space(c[i]); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| ===== C. Self-Adjusting Segment Tree ===== | ===== C. Self-Adjusting Segment Tree ===== | ||
2020-2021/teams/legal_string/jxm2001/contest/ccpc_wannafly_winter_camp_day5.1622036156.txt.gz · 最后更改: 2021/05/26 21:35 由 jxm2001
