M_sea 的博客 - 树链剖分
type: channel
link: https://m-sea-blog.com/tag/树链剖分/
items: JOISC2020 部分题解
items: 洛谷4606 [SDOI2018]战略游戏
items: CF757G Can Bash Save the Day?
items: 洛谷5891 Fracture Ray
items: CF487E Tourists
items: 洛谷3703 [SDOI2017]树点涂色
items: SPOJ GSS 系列简要题解
items: SPOJ QTREE 系列简要题解

JOISC2020 部分题解
type: item
date: 2021-02-02T14:10:00+00:00
description: 先放一点上来，剩下的慢慢更。 ビルの飾り付け 4 / Building 4 不难想到一个 $\mathcal{O}(n^2)$ 的 DP：设 $f_{i, j, 0/1}$ 表示前 $i$ 个数选了 $j$ 个 A，最后一个是 A/B 是否可行，转移显然。最后逆序构造方案即可。 可以发现对于某个 $i, 0/1$，为真的 $j$ 一定是一段区间，因此我们只需要维护这段区间，即可去掉 $j$ 一维。这样子复杂度变为 $\mathcal{O}(n)$。 代码 美味しい美味しいハンバーグ / Hamburg Steak 咕咕咕 掃除 / Sweeping 先考虑只有 V 操作和查询的情况，每次相当于把一段横坐标区间的纵坐标取 $\max$，线段树维护即可。 然后考虑加入 H 操作。可以发现，设之前的 V 操作影响到的最大坐标为 $x$，当前 H 操作能影响到的横坐标范围为 $(x, n - l]$，因为更左边的都被扫走了。 可以发现这样子两维就互不影响了（？），因此可以用两棵线段树维护。 最后再考虑加入插入操作。对于每个询问，我们把对应的插入到它的这段区间丢到线段树上，拆分为 $\mathcal{O}(\log Q)$ 个区间，然后计算操作对每段区间的贡献即可。 代码 カメレオンの恋 / Chameleon’s Love 先考虑知道性别的情况。 设 $S$ 是另一侧的某个集合，考虑询问 $\{u\}\cup S$ 可能出现的结果。如果 $S$ 中有喜欢 $u$ 的 / $u$ 喜欢的 / 与 $u$ 同色的变色龙，那么结果为 $\lvert S\rvert$。这样子就可以通过至多 $3$ 次二分找到和 $u$ 有特殊关系的点。 显然 $u$ 有特殊关系的点只可能有 $1$ 个或 $3$ 个。如果为 $1$ 个，那一定是同色的；否则我们可以每次询问其中的两个和 $u$ 来找到 $u$ 喜欢的那一只。 在确定所有喜欢的关系后，剩下的就是同色的了。 现在考虑不知道性别的情况，此时的主要问题在于分离二分图两侧的点集。 但事实上我们并不需要分离两侧的点集，我们只需要让 $S$ 内部没有特殊关系即可。于是我们把之前已经确定的特殊关系拿出来二分图染色，对两侧的点分别跑一遍即可。 代码 ジョイッターで友達をつくろう / Making Friends on Joitter is Fun 可以发现一个大小为 $s$、入边数为 $k$ 的强连通分量的贡献为 $s(s-1)+sk$，于是我们只需要动态维护这个东西。 用并查集维护每个点所在的强连通分量，用 set 维护每个强连通分量的入边、出边，合并时只需要讨论一下几种情况即可。 需要注意的是，合并两个强连通分量后可能会引起新的合并，需要开一个队列存下所有会合并的强连通分量对。 代码 最古の遺跡 3 / Ruins 3 咕咕咕 星座 3 / Constellation 3 从下往上扫描，并对每个纵坐标维护其下方选了的且与它冲突星星的权值和。 如果它的权值比这个权值和小，则我们会删去它，否则我们会删去下面选了的星星。 用树状数组维护，并用并查集维护左、右两边第一个白色格子即可。 代码 収穫 / Harvest 咕咕咕 迷い猫 / Stray Cat 咕咕咕 首都 / Capital City 考虑建这样一张图：如果所有颜色为 $i$ 的点构成的极小连通块中有颜色为 $j$ 的点，则从 $i$ 向 $j$ 连边。 一条边 $(u,v)$ 的实际意义就是，如果想让 $u$ 连通，则必须把 $u,v$ 合并。 一个强连通分量显然需要合并 $sz-1$ 次，这样子可以缩点成一张 DAG，那么一条到出度为 $0$ 的点的路径是合法的。这样子最短的路径一定是某个出度为 $0$ 的点到自己，直接枚举这样的点，求 $sz-1$ 的最小值即可。 现在考虑建图的问题。对于每种颜色，求出颜色为它的点的 LCA，极小连通块即为这些点到 LCA 的链并。不妨让每个点都向其颜色连边，这样子只需要一种颜色向若干条链上的点连边，树剖+线段树优化即可。 代码 伝説の団子職人 / Legendary Dango Maker 考虑随机调整。我们每次随机一个 W，然后找到以其为中心的一串团子，并进行讨论： 如果这串团子与已有的不冲突，则直接放上去； 如果这串团子与已有的恰好一串冲突，则以 $\frac{1}{2}$ 的概率替换掉之前的那一串。 这样子有可能在局部最优解中出不来，所以最好多开几个一起跑。如果 RP 还行的话可以在 $20$ 分钟内跑出任意一个点。 一个小小的优化：只随机那些有可能组成合法团子串的 W，这样子在某些点上可以快许多。 [collapse status="false" title="参考代码"] // ===========…

洛谷4606 [SDOI2018]战略游戏
type: item
date: 2020-08-12T09:12:39+00:00
description: Luogu LOJ 分析 考虑哪些点是满足条件的。可以发现任意两个关键点路径上的割点都满足条件。 于是可以考虑广义圆方树，因为两个点路径上的割点即对应在圆方树路径上的圆点。 又因为关键点两两之间路径的并就等于这些关键点的虚树，所以我们把问题转化成了求虚树上圆点个数（等价于求点权和）。 这个并不好做，但是我们知道边权和是很好求的（等于所有点按 DFS 序排序后相邻两个点的距离之和再除以二），所以可以考虑把点权放到父边上，再加上虚树的根的点权即可。 需要注意的是关键点也是虚树上的圆点，所以我们还要把关键点减掉。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/stdc++.h> #define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout) using namespace std; typedef long long ll; int read() { int X=0,w=1; char c=getchar(); while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); } while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar(); return X*w; } const int N=300000+10; int n,m,tot,p[N]; vector<int> E[N],T[N]; namespace tarjan { int dfn[N],low[N],tim=0,sta[N],top=0; void tarjan(int u) { dfn[u]=low[u]=++tim,sta[++top]=u; for (int v:E[u]) { if (!dfn[v]) { tarjan(v),low[u]=min(low[u],low[v]); if (low[v]>=dfn[u]) { ++tot; T[tot].emplace_back(u),T[u].emplace_back(tot); while (1) { int t=sta[top--]; T[tot].emplace_back(t),T[t].emplace_back(tot); if (t==v) break; } } } else low[u]=min(low[u],dfn[v]); } } } int dep[N],fa[N],sz[N],hson[N],top[N],dis[N]; int dfn[N],tim=0; void dfs1(int u,int f) { dep[u]=dep[fa[u]=f]+1,sz[u]=1,hson[u]=0; for (int v:T[u]) { if (v==f) continue; dis[v]=dis[u]+(v<=n); dfs1(v,u); sz[u]+=sz[v]; if (sz[v]>sz[hson[u]]) hson[u]=v; } } void dfs2(int u,int anc) { top[u]=anc,dfn[u]=++tim; if (hson[u]) dfs2(hson[u],anc); for (int v:T[u]) if (v!=fa[u]&&v!=hson[u]) 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; } int getdis(int u,int v) { return dis[u]+dis[v]-(dis[LCA(u,v)]<<1); } int main() { for (int _=read();_;--_) { n=read(),m=read(); for (int i=1;i<=n;++i) E[i].clear(); for (int i=1;i<=tot;++i) T[i].clear(); for (int i=1;i<=n;++i) tarjan::dfn[i]=0; tarjan::tim=tarjan::top=dep[0]=dis[1]=tim=0; for (int i=1;i<=m;++i) { i…

CF757G Can Bash Save the Day?
type: item
date: 2020-07-30T13:05:59+00:00
description: Codeforces Luogu 分析 考虑把每个询问拆成 $\sum_{i=1}^r\operatorname{dis}(p_i,u)-\sum_{i=1}^{l-1}\operatorname{dis}(p_i,u)$。 我们考虑怎么求 $\sum_{i=1}^t\operatorname{dis}(p_i,u)$，这个东西可以拆成 $t\times dep_u+\sum_{i=1}^t dep_{p_i}-2\sum_{i=1}^t dep_{\operatorname{LCA}(p_i,u)}$。 前两个很好维护，我们只要考虑求 $\sum_{i=1}^t dep_{\operatorname{LCA}(p_i,u)}$。 这是一个经典问题。我们把每个 $p_{1..t}$ 到根的路径全部加上 $1$，然后查询 $u$ 到根的路径的和即可。 这样子就可以直接树链剖分+可持久化线段树预处理，修改时可以发现只会修改第 $x$ 个版本，直接从上个版本重新修改一次即可。 因为有区间加，所以需要标记永久化。 然而空间可能开不下，有两个优化：第一个是在跳重链修改时不新建本次跳重链过程中新建的点，另一个是在修改达到一定次数时直接清空可持久化线段树然后重建。这样子就可以卡过去了。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/stdc++.h> #define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout) using namespace std; typedef long long ll; int read() { int X=0,w=1; char c=getchar(); while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); } while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar(); return X*w; } const int N=200000+10; int n,Q,p[N]; ll sum[N],pre[N]; struct edge { int v,w,nxt; } e[N<<1]; int head[N]; void addEdge(int u,int v,int w) { static int cnt=0; e[++cnt]=(edge){v,w,head[u]},head[u]=cnt; } int fa[N],sz[N],hson[N],top[N],fw[N]; ll dep[N]; int dfn[N],pos[N],tim=0; void dfs1(int u,int f) { fa[u]=f,sz[u]=1; for (int i=head[u];i;i=e[i].nxt) { int v=e[i].v,w=e[i].w; if (v==f) continue; fw[v]=w,dep[v]=dep[u]+w,dfs1(v,u),sz[u]+=sz[v]; if (sz[v]>sz[hson[u]]) hson[u]=v; } } void dfs2(int u,int anc) { top[u]=anc,dfn[u]=++tim,pos[tim]=u; if (hson[u]) dfs2(hson[u],anc); for (int i=head[u];i;i=e[i].nxt) if (e[i].v!=fa[u]&&e[i].v!=hson[u]) dfs2(e[i].v,e[i].v); } #define ls(o) t[o].ls #define rs(o) t[o].rs int rt[N],tot=0,lim; struct node { ll sumv; int addv,ls,rs;} t[N*150]; void modify(int& o,int l,int r,int ql,int qr) { if (o<=lim) t[++tot]=t[o],o=tot; if (ql<=l&&r<=qr) { t[o].sumv+=pre[r]-pre[l-1],++t[o].addv; return; } int mid=(l+r)>>1; if (ql<=mid) modify(ls(o),l,mid,ql,qr); if (qr>mid) modify(rs(…

洛谷5891 Fracture Ray
type: item
date: 2020-06-28T08:58:00+00:00
description: Luogu 分析 对于每个数 $x$ 从 $x+\operatorname{count}(x)$ 向 $x$ 连边，则应该是一个森林。为了方便我们再建一个点向每棵树的根连边。 然而点数是 $2^{30}$ 级别的，所以并不能直接拿树剖+线段树搞。 但实际上只有 $2\times 10^5$ 个操作，所以可以考虑建虚树，并对虚树上的每个点求出 $cnt_x$ 表示向上走多少条边能到达虚树上的父亲 $f$，那么原树上将 $u\to f$ 这条链（不包括 $f$）加上 $w$ 等价于虚树上将 $u$ 加上 $cnt_x\times w$。 那么就可以直接对虚树树剖+线段树维护了。现在的问题主要在于如何建出虚树。 首先想办法找到所有在虚树中的点。显然每个操作中的点都在虚树中；剩下的部分可以开一个大小为 $2^{30}$ 的 std::bitset 来记录每个点是否到过，对于每个操作中的点，暴力向上跳父亲直到当前点之前到过或 $>v$，则最后跳到的这个点也在虚树中。 然后我们要确定每个点在虚树上的父亲。注意到某个点的祖先一定比它大，所以我们可以把这些点从大到小排序后再依次拿出来做上面的过程，最后跳到的点即为虚树上的父亲。 这样子看似很暴力，但是实际上访问到的点数不多，所以是可以过的。 如果被卡常了可以手写 std::bitset。然而应该只有我被卡常了 /dk 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/stdc++.h> #define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout) #define popcount __builtin_popcount #pragma GCC optimize("Ofast,no-stack-protector,fast-math,unroll-loops") using namespace std; typedef long long ll; namespace IO { const int SIZE=1<<21; char ibuf[SIZE|1],*iS,*iT,obuf[SIZE|1],*oS=obuf,*oT=obuf+SIZE-1; void flush() { fwrite(obuf,1,oS-obuf,stdout); oS=obuf; } char getc() { if (iS==iT) { iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin); if (iS==iT) return EOF; } return *iS++; } void putc(char x) { *oS++=x; if (oS==oT) flush(); } int read() { int X=0,w=1; char c=getc(); while (c<'0'||c>'9') { if (c=='-') w=-1; c=getc(); } while (c>='0'&&c<='9') X=X*10+c-'0',c=getc(); return X*w; } void write(ll x) { static char sta[65]; int top=0; if (!x) putc('0'); if (x<0) putc('-'),x=-x; while (x) sta[++top]=x%10+'0',x/=10; while (top) putc(sta[top--]); } struct flusher { ~flusher() { flush(); } } io_flusher; } using IO::getc; using IO::putc; using IO::read; using IO::write; const int N=800000+10; int Q,lim,rt,cnt[N]; struct query { int op,u,w; } q[N]; unsigned bit[1<<25|1]; bool get(int x) { return (bit[x>>5]>>(x&31))&1; } vector<int> v,E[N]; unordered_map<int,int> id; int tot=0; int fa[N],dep[N],sz[N],hson[N],top[N]; int dfn[N],pos[N],tim…

CF487E Tourists
type: item
date: 2020-06-03T12:29:55+00:00
description: Codeforces Luogu 分析 可以发现，在从 $u$ 走到 $v$ 的过程中如果经过了一个点双联通分量，那么对于其中的每个点都存在一条经过它的路径。因此，我们一定会经过每个点双中权值最小的点。 从而可以想到广义圆方树。对于每个方点，它的权值应为与它相连的圆点中的最小值。这样子查询直接树剖+线段树即可。因为有修改圆点权值的操作，用 std::multiset 维护每个方点相连的圆点的权值，修改圆点权值时直接 erase 再 insert 一下，如果发生了变化在线段树上单点修改即可。 这样子有一个问题，就是当圆方树是一个菊花的形状时每次修改都是 $\mathcal{O}(n)$ 级别的，会 GG。注意到广义圆方树上圆方点是相间的，所以方点的 multiset 中可以只维护子节点的权值，在查询时如果 LCA 为方点就把它的父节点也算上即可。 写起来挺休闲的，只要码一堆板子上去就行了，没有什么细节。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/stdc++.h> #define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout) using namespace std; typedef long long ll; int read() { int X=0,w=1; char c=getchar(); while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); } while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar(); return X*w; } const int N=200000+10; int n,m,Q,w[N],tot; vector<int> E[N],T[N]; multiset<int> S[N]; namespace Tarjan { int dfn[N],low[N],tim=0; int sta[N],top=0; void tarjan(int u) { dfn[u]=low[u]=++tim,sta[++top]=u; for (int v:E[u]) { if (!dfn[v]) { tarjan(v),low[u]=min(low[u],low[v]); if (low[v]>=dfn[u]) { ++tot,T[tot].emplace_back(u),T[u].emplace_back(tot); while ("Nin Diao Da Wo") { int t=sta[top--]; T[tot].emplace_back(t),T[t].emplace_back(tot); if (t==v) break; // 注意这里不是 t==u } } } else low[u]=min(low[u],dfn[v]); } } } // namespace Tarjan int fa[N],dep[N],sz[N],hson[N],top[N]; int dfn[N],pos[N],tim=0; void dfs1(int u,int f) { dep[u]=dep[fa[u]=f]+1,sz[u]=1; if (u<=n&&f) S[f].insert(w[u]); for (int v:T[u]) { if (v==f) continue; dfs1(v,u),sz[u]+=sz[v]; if (sz[v]>sz[hson[u]]) hson[u]=v; } } void dfs2(int u,int anc) { top[u]=anc,dfn[u]=++tim,pos[tim]=u; if (hson[u]) dfs2(hson[u],anc); for (int v:T[u]) if (v!=fa[u]&&v!=hson[u]) dfs2(v,v); } #define ls (o<<1) #define rs (o<<1|1) int minv[N<<2]; void pushup(int o) { minv[o]=min(minv[ls],minv[rs]); } void build(int o,int l,int r) { if (l==r) { minv[o]=pos[l]<=n?w[pos[l]]:*S[pos[l]].begin(); return; } i…

洛谷3703 [SDOI2017]树点涂色
type: item
date: 2020-06-02T08:56:00+00:00
description: Luogu LOJ 分析 可以发现每种颜色一定是一条链，则整棵树相当于被剖分成了若干条链。 考虑 LCT 维护，则 1 操作相当于 access(x)，2 操作相当于询问一条路径上的链数，3 操作相当于求子树中到根路径上链数最大的点。 考虑将 2 操作差分，则只需要用一个数据结构维护每个点到根路径的链数，要求支持区间求最大值。 考虑 access(x) 时对每个点到根路径上的链数的影响。对于当前的 $x$，它的重儿子所在子树的答案会加上 $1$（因为这条链被断开了），它的新重儿子所在子树的答案会减去 $1$（因为这条链连上了）。用 DFS 序+线段树维护即可。 剩下的问题是如何求某个点的重儿子所在子树的根节点。我们改一下 findroot，让它跳左儿子之前不 access 和 splay，这样子 findroot(rs(x)) 找到的就是 $x$ 的重儿子所在子树的根节点了。 因为魔改了 findroot 所以复杂度不会算。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/stdc++.h> #define file(x) freopen(x".in","r",stdin); freopen(x".out","w",stdout) using namespace std; typedef long long ll; int read() { int X=0,w=1; char c=getchar(); while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); } while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar(); return X*w; } const int N=100000+10; int n,m; vector<int> E[N]; int dep[N],fa[N],sz[N],hson[N],top[N]; int dfn[N],low[N],pos[N],tim=0; void dfs1(int u,int f) { dep[u]=dep[fa[u]=f]+1,sz[u]=1; for (int v:E[u]) { if (v==f) continue; dfs1(v,u); sz[u]+=sz[v]; if (sz[v]>sz[hson[u]]) hson[u]=v; } } void dfs2(int u,int anc) { top[u]=anc,dfn[u]=++tim,pos[tim]=u; if (hson[u]) dfs2(hson[u],anc); for (int v:E[u]) if (v!=fa[u]&&v!=hson[u]) dfs2(v,v); low[u]=tim; } int getlca(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; } #define ls (o<<1) #define rs (o<<1|1) int maxv[N<<2],addv[N<<2]; void pushup(int o) { maxv[o]=max(maxv[ls],maxv[rs]); } void pushdown(int o) { if (addv[o]) { maxv[ls]+=addv[o],addv[ls]+=addv[o]; maxv[rs]+=addv[o],addv[rs]+=addv[o]; addv[o]=0; } } void build(int o,int l,int r) { if (l==r) { maxv[o]=dep[pos[l]]; return; } int mid=(l+r)>>1; build(ls,l,mid),build(rs,mid+1,r); pushup(o); } void modify(int o,int l,int r,int ql,int qr,int w) { if (ql<=l&&r<=qr) { maxv[o]+=w,addv[o]+=w; return; } int mid=(l+r)>>1; pushdown(o); if (ql<=mid) modify(ls,l,mid,ql,qr,w); if…

SPOJ GSS 系列简要题解
type: item
date: 2019-08-06T12:30:00+00:00
description: GSS1 线段树上维护以下 $4$ 个东西： 区间和 区间最大前缀和 区间最大后缀和 区间最大子段和 合并两个区间应该比较简单，这里不再赘述。 [collapse status="false" title="代码"] // =================================== // author: M_sea // website: http://m-sea-blog.com/ // =================================== #include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <cmath> #define re register using namespace std; inline int read() { int X=0,w=1; char c=getchar(); while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); } while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar(); return X*w; } const int N=50000+10; int n,Q,a[N]; struct node { int sum,lmax,rmax,ans; }; node operator +(node a,node b) { node c; c.sum=a.sum+b.sum; c.lmax=max(a.lmax,a.sum+b.lmax); c.rmax=max(b.rmax,b.sum+a.rmax); c.ans=max(max(a.ans,b.ans),a.rmax+b.lmax); return c; } #define ls (o<<1) #define rs (o<<1|1) node t[N<<2]; inline void build(int o,int l,int r) { if (l==r) { t[o].sum=t[o].lmax=t[o].rmax=t[o].ans=a[l]; return; } int mid=(l+r)>>1; build(ls,l,mid),build(rs,mid+1,r); t[o]=t[ls]+t[rs]; } inline node query(int o,int l,int r,int ql,int qr) { if (ql<=l&&r<=qr) return t[o]; int mid=(l+r)>>1; if (qr<=mid) return query(ls,l,mid,ql,qr); else if (ql>mid) return query(rs,mid+1,r,ql,qr); else return query(ls,l,mid,ql,mid)+query(rs,mid+1,r,mid+1,qr); } #undef ls #undef rs int main() { n=read(); for (re int i=1;i<=n;++i) a[i]=read(); build(1,1,n); Q=read(); while (Q--) { int l=read(),r=read(); printf("%d\n",query(1,1,n,l,r).ans); } return 0; } [/collapse] GSS2 这题就很神仙了。 把所有询问离线并按右端点排序，然后从左往右扫。 对于线段树的每个叶子节点 $[i,i]$，假设当前扫到了 $p$ ，那么该节点存的是 $\displaystyle\sum_{j=i}^pa_j$ 。 设 $pre_i$ 表示上一个和 $a_i$ 相同的数，那么每次把 $[pre_i+1,i]$ 加上 $a+i$ 即可。 再额外维护一个历史最大值，这样子扫到 $r$ 时就只要询问 $[l,r]$ 的历史最大值的最大值就可以得到答案了。 那么线段树维护这些东西即可： 和 和的历史最大值 和的懒标记 和的历史最大值的懒标记 合并两个区间应该也比较简单，详见代码。 [collapse status="false" title="代码"] // =================================== // author: M_sea // website: http://m-sea-blog.com/ // =================================== #include <algorithm> …

SPOJ QTREE 系列简要题解
type: item
date: 2019-08-04T13:43:00+00:00
description: QTREE1 把 $(fa_i,i)$ 的边权作为 $i$ 的点权，然后就是个树剖板子了... 但是注意查询时 LCA 是不能查的，需要判一下。 而且这题竟然不能交 C++ ，然后我改了半个小时才把 C++ 改成 C QAQ [collapse status="false" title="SPOJ AC代码"] // =================================== // author: M_sea // website: http://m-sea-blog.com/ // =================================== #include <stdlib.h> #include <string.h> #include <stdio.h> #include <math.h> #define re register #define swap(x,y) { int tmp=x; x=y; y=tmp; } int max(int a,int b) { return a>b?a:b; } int read() { int X=0,w=1; char c=getchar(); while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); } while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar(); return X*w; } #define N (10000+10) int n,val[N]; struct edge { int v,w,nxt; } e[N<<1]; int head[N],x[N],y[N],e_cnt=0; void addEdge(int u,int v,int w) { ++e_cnt; e[e_cnt].v=v,e[e_cnt].w=w,e[e_cnt].nxt=head[u],head[u]=e_cnt; } int fa[N],dep[N],sz[N],hson[N],top[N]; int dfn[N],rl[N],tim=0; void dfs1(int u,int f) { fa[u]=f,dep[u]=dep[f]+1,sz[u]=1; for (re int i=head[u];i;i=e[i].nxt) { int v=e[i].v,w=e[i].w; if (v==f) continue; val[v]=w,dfs1(v,u),sz[u]+=sz[v]; if (sz[v]>sz[hson[u]]) hson[u]=v; } } void dfs2(int u,int anc) { dfn[u]=++tim,rl[tim]=u,top[u]=anc; if (hson[u]) dfs2(hson[u],anc); for (re int i=head[u];i;i=e[i].nxt) if (e[i].v!=fa[u]&&e[i].v!=hson[u]) dfs2(e[i].v,e[i].v); } #define ls (o<<1) #define rs (o<<1|1) int maxv[N<<2]; void pushup(int o) { maxv[o]=max(maxv[ls],maxv[rs]); } void build(int o,int l,int r) { if (l==r) { maxv[o]=val[rl[l]]; return; } int mid=(l+r)>>1; build(ls,l,mid),build(rs,mid+1,r); pushup(o); } void modify(int o,int l,int r,int p,int w) { if (l==r) { maxv[o]=w; return; } int mid=(l+r)>>1; if (p<=mid) modify(ls,l,mid,p,w); else modify(rs,mid+1,r,p,w); pushup(o); } int query(int o,int l,int r,int ql,int qr) { if (ql<=l&&r<=qr) return maxv[o]; int mid=(l+r)>>1,res=0; if (ql<=mid) res=max(res,query(ls,l,mid,ql,qr)); if (qr>mid) res=max(res,query(rs,mid+1,r,ql,qr)); return res; } #undef ls #undef rs int Query(int u,int v) { int tu=top[u…