先放一点上来，剩下的慢慢更。 ビルの飾り付け 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="参考代码"] // ==================================== // 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 debug(...) fprintf(stderr, __VA_ARGS__) 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 = 500 + 10; const int LIM = 47220; // Z const int dx[4] = {1, 0, 1, 1}; const int dy[4] = {0, 1, 1, -1}; mt19937 rnd(time(0)); int n, m, vis[N][N], bld[N][N]; pair<int, int> bl[N][N]; char s[N][N], ans[N][N]; vector<pair<int, int>> white_dango; bool check(char a, char b, char c) { return (a == 'P' && b == 'W' && c == 'G') || (a == 'G' && b == 'W' && c == 'P'); } int findd(int x, int y) { int p[4] = {0, 1, 2, 3}; shuffle(p, p + 4, rnd); for (int i = 0; i < 4; ++i) { int d = p[i], x1 = x - dx[d], y1 = y - dy[d], x2 = x + dx[d], y2 = y + dy[d]; if (x1 < 1 || x1 > n || y1 < 1 || y1 > m || x2 < 1 || x2 > n || y2 < 1 || y2 > m) continue; if (check(s[x1][y1], s[x][y], s[x2][y2])) return d; } return -1; } int main() { n = read(), m = read(); for (int i = 1; i <= n; ++i) scanf("%s", s[i] + 1); for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) if (s[i][j] == 'W' && findd(i, j) >= 0) white_dango.emplace_back(i, j); for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) ans[i][j] = s[i][j]; int cnt = 0; while (cnt < LIM) { int p = rnd() % white_dango.size(); int x = white_dango[p].first, y = white_dango[p].second; int d = findd(x, y); if (d < 0) continue; int x1 = x - dx[d], y1 = y - dy[d], x2 = x + dx[d], y2 = y + dy[d]; if (!vis[x1][y1] && !vis[x][y] && !vis[x2][y2]) { vis[x1][y1] = vis[x][y] = vis[x2][y2] = 1; bl[x1][y1] = bl[x][y] = bl[x2][y2] = make_pair(x, y); bld[x1][y1] = bld[x][y] = bld[x2][y2] = d; ans[x][y] = "|-\\/"[d], ++cnt; debug("cnt = %d\n", cnt); } else if (vis[x1][y1] + vis[x][y] + vis[x2][y2] == 1 && (rnd() & 1)) { int X, Y, D; if (vis[x1][y1]) X = bl[x1][y1].first, Y = bl[x1][y1].second, D = bld[x1][y1]; else if (vis[x][y]) X = bl[x][y].first, Y = bl[x][y].second, D = bld[x][y]; else X = bl[x2][y2].first, Y = bl[x2][y2].second, D = bld[x2][y2]; int X1 = X - dx[D], Y1 = Y - dy[D], X2 = X + dx[D], Y2 = Y + dy[D]; vis[X1][Y1] = vis[X][Y] = vis[X2][Y2] = 0; ans[X][Y] = s[X][Y]; vis[x1][y1] = vis[x][y] = vis[x2][y2] = 1; bl[x1][y1] = bl[x][y] = bl[x2][y2] = make_pair(x, y); bld[x1][y1] = bld[x][y] = bld[x2][y2] = d; ans[x][y] = "|-\\/"[d]; } } debug("ans = %d\n", cnt); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) putchar(ans[i][j]); puts(""); } return 0; } [/collapse] 治療計画 / Treatment Project 先考虑一个 DP。设 $dp_i$ 表示 $t_i$ 时刻 $[1, r_i]$ 均已治愈的最小代价，$i$ 能转移到 $j$ 当且仅当 $r_i - l_j + 1 \geq \lvert t_i - t_j \rvert$。 可以发现转移类似于最短路，我们需要快速转移。 显然把绝对值拆掉。把所有计划按 $t_i$ 从小到大排序，用两棵线段树维护 $l_i-t_i$ 的最小值和 $l_i+t_i$ 的最小值，每次暴力在线段树上找到满足条件的点即可。找到之后，需要把线段树上这些点的权值改成 $+\infty$。 因为是点权，所以每个点只会被松弛一次，因此复杂度是对的。 代码
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) { int u=read(),v=read(); E[u].emplace_back(v),E[v].emplace_back(u); } tot=n; tarjan::tarjan(1); dfs1(1,0),dfs2(1,1); for (int Q=read();Q;--Q) { int k=read(); for (int i=1;i<=k;++i) p[i]=read(); sort(p+1,p+k+1,[](int x,int y) { return dfn[x]<dfn[y]; }); int ans=0; for (int i=1;i<=k;++i) ans+=getdis(p[i],p[i%k+1]); ans=ans/2+(LCA(p[1],p[k])<=n); printf("%d\n",ans-k); } } return 0; }
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(o),mid+1,r,ql,qr); t[o].sumv=t[ls(o)].sumv+t[rs(o)].sumv+t[o].addv*(pre[r]-pre[l-1]); } ll query(int o,int l,int r,int ql,int qr,int tag) { if (!o) return tag*(pre[min(r,qr)]-pre[max(l,ql)-1]); if (ql<=l&&r<=qr) return t[o].sumv+tag*(pre[r]-pre[l-1]); int mid=(l+r)>>1; ll res=0; if (ql<=mid) res+=query(t[o].ls,l,mid,ql,qr,tag+t[o].addv); if (qr>mid) res+=query(t[o].rs,mid+1,r,ql,qr,tag+t[o].addv); return res; } #undef ls #undef rs void modify(int u,int t) { lim=tot; while (u) { modify(rt[t],1,n,dfn[top[u]],dfn[u]); u=fa[top[u]]; } } ll query(int u,int t) { ll res=t*dep[u]+sum[t]; while (u) { res-=2*query(rt[t],1,n,dfn[top[u]],dfn[u],0); u=fa[top[u]]; } return res; } int main() { n=read(),Q=read(); for (int i=1;i<=n;++i) p[i]=read(); for (int i=1;i<n;++i) { int u=read(),v=read(),w=read(); addEdge(u,v,w),addEdge(v,u,w); } dfs1(1,0),dfs2(1,1); for (int i=1;i<=n;++i) sum[i]=sum[i-1]+dep[p[i]]; for (int i=1;i<=n;++i) pre[i]=pre[i-1]+fw[pos[i]]; for (int i=1;i<=n;++i) rt[i]=rt[i-1],modify(p[i],i); int lastans=0,cnt=0; while (Q--) { int op=read(); if (op==1) { int l=read()^lastans,r=read()^lastans,u=read()^lastans; ll ans=query(u,r)-query(u,l-1); printf("%lld\n",ans); lastans=ans&1073741823; } else { int x=read()^lastans; swap(p[x],p[x+1]),sum[x]=sum[x-1]+dep[p[x]]; if (++cnt==50000) { cnt=tot=0; for (int i=1;i<=n;++i) rt[i]=rt[i-1],modify(p[i],i); } else rt[x]=rt[x-1],modify(p[x],x); } } return 0; }
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=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); } namespace T { #define ls (o<<1) #define rs (o<<1|1) ll sumv[N<<2],sumtag[N<<2],addv[N<<2]; void pushup(int o) { sumv[o]=sumv[ls]+sumv[rs]; } void pushdown(int o) { if (addv[o]) { addv[ls]+=addv[o],sumv[ls]+=sumtag[ls]*addv[o]; addv[rs]+=addv[o],sumv[rs]+=sumtag[rs]*addv[o]; addv[o]=0; } } void build(int o,int l,int r) { if (l==r) { sumtag[o]=cnt[pos[l]]; return; } int mid=(l+r)>>1; build(ls,l,mid),build(rs,mid+1,r); sumtag[o]=sumtag[ls]+sumtag[rs]; } void modify(int o,int l,int r,int ql,int qr,int w) { if (ql<=l&&r<=qr) { addv[o]+=w,sumv[o]+=sumtag[o]*w; return; } int mid=(l+r)>>1; pushdown(o); if (ql<=mid) modify(ls,l,mid,ql,qr,w); if (qr>mid) modify(rs,mid+1,r,ql,qr,w); pushup(o); } ll query(int o,int l,int r,int ql,int qr) { if (ql<=l&&r<=qr) return sumv[o]; int mid=(l+r)>>1; ll res=0; pushdown(o); if (ql<=mid) res+=query(ls,l,mid,ql,qr); if (qr>mid) res+=query(rs,mid+1,r,ql,qr); pushup(o); return res; } #undef ls #undef rs } void modify(int u,int w) { while (top[u]!=rt) { T::modify(1,1,tot,dfn[top[u]],dfn[u],w); u=fa[top[u]]; } T::modify(1,1,tot,1,dfn[u],w); } ll query(int u) { ll res=0; while (top[u]!=rt) { res+=T::query(1,1,tot,dfn[top[u]],dfn[u]); u=fa[top[u]]; } return res+T::query(1,1,tot,1,dfn[u]); } int main() { Q=read(),lim=read(); for (int i=1;i<=Q;++i) { q[i].op=read(),q[i].u=read(); if (q[i].op==1) q[i].w=read(); int u=q[i].u; v.emplace_back(u); for (;u<=lim&&!get(u);u+=popcount(u)) bit[u>>5]|=1u<<(u&31); if (u<=lim) v.emplace_back(u); } sort(v.begin(),v.end()),v.erase(unique(v.begin(),v.end()),v.end()); memset(bit,0,sizeof(bit)); for (int i=v.size()-1;~i;--i) { int u=v[i]; if (!id[u]) id[u]=++tot; int f=u; for (;f<=lim&&!get(f);f+=popcount(f)) bit[f>>5]|=1u<<(f&31),++cnt[id[u]]; if (f>lim) f=lim+1; if (!id[f]) id[f]=++tot; E[id[f]].emplace_back(id[u]); } rt=id[lim+1]; dfs1(rt,0),dfs2(rt,rt); T::build(1,1,tot); for (int i=1;i<=Q;++i) { if (q[i].op==1) modify(id[q[i].u],q[i].w); else write(query(id[q[i].u])),putc('\n'); } return 0; }
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; } 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) { minv[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 minv[o]; int mid=(l+r)>>1,res=2e9; if (ql<=mid) res=min(res,query(ls,l,mid,ql,qr)); if (qr>mid) res=min(res,query(rs,mid+1,r,ql,qr)); return res; } #undef ls #undef rs void modify(int u,int v) { if (fa[u]) { S[fa[u]].erase(S[fa[u]].find(w[u])); S[fa[u]].insert(v); modify(1,1,tot,dfn[fa[u]],*S[fa[u]].begin()); } w[u]=v,modify(1,1,tot,dfn[u],v); } int query(int u,int v) { int res=2e9; while (top[u]!=top[v]) { if (dep[top[u]]<dep[top[v]]) swap(u,v); res=min(res,query(1,1,tot,dfn[top[u]],dfn[u])); u=fa[top[u]]; } if (dep[u]<dep[v]) swap(u,v); res=min(res,query(1,1,tot,dfn[v],dfn[u])); if (v>n) res=min(res,w[fa[v]]); return res; } int main() { n=read(),m=read(),Q=read(); for (int i=1;i<=n;++i) w[i]=read(); for (int i=1;i<=m;++i) { int u=read(),v=read(); E[u].emplace_back(v),E[v].emplace_back(u); } tot=n,Tarjan::tarjan(1); dfs1(1,0),dfs2(1,1); build(1,1,tot); while (Q--) { char s[2]; scanf("%s",s); if (s[0]=='C') { int u=read(),v=read(); modify(u,v); } else { int u=read(),v=read(); printf("%d\n",query(u,v)); } } return 0; }
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 (qr>mid) modify(rs,mid+1,r,ql,qr,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; pushdown(o); 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)); pushup(o); return res; } #undef ls #undef rs namespace LCT { #define ls(o) ch[o][0] #define rs(o) ch[o][1] int fa[N],ch[N][2]; int nroot(int x) { return ls(fa[x])==x||rs(fa[x])==x; } void rotate(int x) { int y=fa[x],z=fa[y],k=(x==rs(y)),w=ch[x][!k]; if (nroot(y)) ch[z][y==rs(z)]=x; ch[x][!k]=y,ch[y][k]=w; if (w) fa[w]=y; fa[y]=x,fa[x]=z; } void splay(int x) { while (nroot(x)) { int y=fa[x],z=fa[y]; if (nroot(y)) rotate((x==ls(y))^(y==ls(z))?x:y); rotate(x); } } int findroot(int x) {while (ls(x)) x=ls(x); return x; } void access(int x) { for (int y=0;x;x=fa[y=x]) { splay(x); if (rs(x)) { int t=findroot(rs(x)); modify(1,1,n,dfn[t],low[t],1); } rs(x)=y; if (rs(x)) { int t=findroot(rs(x)); modify(1,1,n,dfn[t],low[t],-1); } } } #undef ls #undef rs } // namespace LCT int main() { n=read(),m=read(); for (int i=1;i<n;++i) { int u=read(),v=read(); E[u].emplace_back(v),E[v].emplace_back(u); } dfs1(1,0),dfs2(1,1); build(1,1,n); for (int i=1;i<=n;++i) LCT::fa[i]=fa[i]; while (m--) { int op=read(); if (op==1) LCT::access(read()); if (op==2) { int u=read(),v=read(),t=getlca(u,v); printf("%d\n",query(1,1,n,dfn[u],dfn[u]) +query(1,1,n,dfn[v],dfn[v]) -(query(1,1,n,dfn[t],dfn[t])<<1)+1); } if (op==3) { int u=read(); printf("%d\n",query(1,1,n,dfn[u],low[u])); } } return 0; }
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> #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=100000+10; int n,Q,a[N]; #define ls (o<<1) #define rs (o<<1|1) int now_mx[N<<2],now_lz[N<<2],his_mx[N<<2],his_lz[N<<2]; inline void pushup(int o) { now_mx[o]=max(now_mx[ls],now_mx[rs]); his_mx[o]=max(his_mx[ls],his_mx[rs]); } inline void pushdown(int o) { his_mx[ls]=max(his_mx[ls],now_mx[ls]+his_lz[o]); his_lz[ls]=max(his_lz[ls],now_lz[ls]+his_lz[o]); now_mx[ls]+=now_lz[o],now_lz[ls]+=now_lz[o]; his_mx[rs]=max(his_mx[rs],now_mx[rs]+his_lz[o]); his_lz[rs]=max(his_lz[rs],now_lz[rs]+his_lz[o]); now_mx[rs]+=now_lz[o],now_lz[rs]+=now_lz[o]; his_lz[o]=now_lz[o]=0; } inline void modify(int o,int l,int r,int ql,int qr,int w) { if (ql<=l&&r<=qr) { now_mx[o]+=w,now_lz[o]+=w; his_mx[o]=max(his_mx[o],now_mx[o]); his_lz[o]=max(his_lz[o],now_lz[o]); return; } int mid=(l+r)>>1; pushdown(o); if (ql<=mid) modify(ls,l,mid,ql,qr,w); if (qr>mid) modify(rs,mid+1,r,ql,qr,w); pushup(o); } inline int query(int o,int l,int r,int ql,int qr) { if (ql<=l&&r<=qr) return his_mx[o]; int mid=(l+r)>>1,res=0; pushdown(o); 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)); pushup(o); return res; } #undef ls #undef rs int pre[N],pos[N<<1],ans[N]; struct Query { int id,l,r; } q[N]; bool operator <(Query a,Query b) { return a.r<b.r; } int main() { n=read(); for (re int i=1;i<=n;++i) a[i]=read(); for (re int i=1;i<=n;++i) pre[i]=pos[a[i]+N],pos[a[i]+N]=i; Q=read(); for (re int i=1;i<=Q;++i) q[i]=(Query){i,read(),read()}; sort(q+1,q+Q+1); for (re int i=1,j=1;i<=n;++i) { modify(1,1,n,pre[i]+1,i,a[i]); while (q[j].r==i) ans[q[j].id]=query(1,1,n,q[j].l,i),++j; } for (re int i=1;i<=Q;++i) printf("%d\n",ans[i]); return 0; } [/collapse] GSS3 就是 GSS1 加个修改操作，没什么好说的。 [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 void modify(int o,int l,int r,int p,int w) { if (l==r) { t[o].sum=t[o].lmax=t[o].rmax=t[o].ans=w; return; } int mid=(l+r)>>1; if (p<=mid) modify(ls,l,mid,p,w); else modify(rs,mid+1,r,p,w); 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 op=read(),l=read(),r=read(); if (!op) modify(1,1,n,l,r); else printf("%d\n",query(1,1,n,l,r).ans); } return 0; } [/collapse] 事实上这题可以动态 DP ，点我。（当然 GSS1 也是可以动态 DP 的。） GSS4 用线段树维护区间和。 注意到一个数开根号变成 $1$ 的次数不大，而变成 $1$ 后就不用修改了。 假设现在在修改一个区间：如果该区间内的所有数开根号都不会变了，那就不修改了；否则直接暴力修改到叶节点即可。 [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 #define int long long 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=100000+10; int n,Q; #define ls (o<<1) #define rs (o<<1|1) int sum[N<<2],f[N<<2]; inline void pushup(int o) { sum[o]=sum[ls]+sum[rs],f[o]=f[ls]&f[rs]; } inline void build(int o,int l,int r) { if (l==r) { sum[o]=read(),f[o]=sum[o]<=1; return; } int mid=(l+r)>>1; build(ls,l,mid),build(rs,mid+1,r); pushup(o); } inline void modify(int o,int l,int r,int ql,int qr) { if (f[o]) return; if (l==r) { sum[o]=floor(sqrt(sum[o])); if (sum[o]<=1) f[o]=1; return; } int mid=(l+r)>>1; if (ql<=mid) modify(ls,l,mid,ql,qr); if (qr>mid) modify(rs,mid+1,r,ql,qr); pushup(o); } inline int query(int o,int l,int r,int ql,int qr) { if (ql<=l&&r<=qr) return sum[o]; int mid=(l+r)>>1,res=0; if (ql<=mid) res+=query(ls,l,mid,ql,qr); if (qr>mid) res+=query(rs,mid+1,r,ql,qr); return res; } #undef ls #undef rs signed main() { int T=0; while (scanf("%lld",&n)==1) { build(1,1,n); Q=read(); printf("Case #%lld:\n",++T); while (Q--) { int op=read(),l=read(),r=read(); if (l>r) swap(l,r); if (op) printf("%lld\n",query(1,1,n,l,r)); else modify(1,1,n,l,r); } puts(""); } return 0; } [/collapse] GSS5 在 GSS1 的基础上大力讨论一下即可。 如果两区间没有交，答案就是 $[x_1,y_1]$ 的最大后缀和加 $(y_1,x_2)$ 的和加 $[x_2,y_2]$ 的最大前缀和。 如果两区间有交，答案为以下三者中的最大值： $[x_2,y_1]$ 的最大子段和。 $[x_1,x_2)$ 的最大后缀和加 $[x_2,y_2]$ 的最大前缀和。 $[x_1,y_1]$ 的最大后缀和加 $(y_1,y_2]$ 的最大后缀和。 [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=10000+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 inline int calc(int l1,int r1,int l2,int r2) { int res; if (r1<l2) { res=query(1,1,n,l1,r1).rmax; res+=query(1,1,n,l2,r2).lmax; if (r1+1<l2)res+=query(1,1,n,r1+1,l2-1).sum; } else { res=query(1,1,n,l2,r1).ans; res=max(res,query(1,1,n,l1,l2).rmax+query(1,1,n,l2,r2).lmax-a[l2]); res=max(res,query(1,1,n,l1,r1).rmax+query(1,1,n,r1,r2).lmax-a[r1]); } return res; } int main() { int T=read(); while (T--) { n=read(); for (re int i=1;i<=n;++i) a[i]=read(); build(1,1,n); Q=read(); while (Q--) { int l1=read(),r1=read(),l2=read(),r2=read(); printf("%d\n",calc(l1,r1,l2,r2)); } } return 0; } [/collapse] GSS6 在 GSS1 的基础上把线段树改成平衡树即可。 插入、删除、修改、查询就是基础的平衡树操作。 然后 pushup 和线段树有些不同，但本质是一样的。 [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=200000+10; int n,Q,a[N]; // fhq treap int root,tot=0; int ch[N][2],val[N],rnd[N],sz[N]; struct node { int sum,lmax,rmax,ans; } t[N]; inline int new_node(int w) { ++tot; sz[tot]=1,val[tot]=w,rnd[tot]=rand(); t[tot].lmax=t[tot].rmax=max(w,0); t[tot].sum=t[tot].ans=w; return tot; } inline void pushup(int x) { int ls=ch[x][0],rs=ch[x][1]; sz[x]=sz[ls]+sz[rs]+1; t[x].sum=t[ls].sum+val[x]+t[rs].sum; t[x].lmax=max(t[ls].lmax,t[ls].sum+val[x]+t[rs].lmax); t[x].rmax=max(t[rs].rmax,t[rs].sum+val[x]+t[ls].rmax); t[x].ans=max(max(t[ls].ans,t[rs].ans),t[ls].rmax+val[x]+t[rs].lmax); } inline void split(int o,int k,int& x,int& y) { if (!o) { x=y=0; return; } if (k<=sz[ch[o][0]]) y=o,split(ch[o][0],k,x,ch[o][0]); else x=o,split(ch[o][1],k-sz[ch[o][0]]-1,ch[o][1],y); pushup(o); } inline int merge(int A,int B) { if (!A||!B) return A+B; if (rnd[A]<rnd[B]) { ch[A][1]=merge(ch[A][1],B),pushup(A); return A; } else { ch[B][0]=merge(A,ch[B][0]),pushup(B); return B; } } int main() { srand(19260817); n=read(); t[0].ans=-2e9; for (re int i=1;i<=n;++i) a[i]=read(); for (re int i=1;i<=n;++i) root=merge(root,new_node(a[i])); Q=read(); while (Q--) { char op[2]; scanf("%s",op); int o,r,z; if (op[0]=='I') { int p=read(),x=read(); split(root,p-1,o,r); root=merge(o,merge(new_node(x),r)); } else if (op[0]=='D') { int p=read(); split(root,p-1,o,r),split(r,1,r,z); root=merge(o,z); } else if (op[0]=='R') { int p=read(),x=read(); split(root,p-1,o,r),split(r,1,r,z); val[r]=x,pushup(r); root=merge(o,merge(r,z)); } else { int L=read(),R=read(); split(root,R,r,z),split(r,L-1,o,r); printf("%d\n",t[r].ans); root=merge(o,merge(r,z)); } } return 0; } [/collapse] GSS7 在 GSS1 的基础上加个树链剖分即可。 首先解决区间修改的问题，每个节点维护一个区间赋值标记即可。 链修改比较简单，把所有重链都改一遍即可。 需要注意的是链查询。因为合并两个区间时左右顺序对结果是有影响的，所以不能直接合并过去。 一种方法是维护一个 $L$ 和一个 $R$ ，分别代表左右两条链合并的结果，最后再把 $L,R$ 并起来。 写代码的时候要考虑清楚左右顺序问题，我因为这个 WA 了几发。 [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=100000+10; int n,Q,a[N]; struct edge { int v,nxt; } e[N<<1]; int head[N]; inline void addEdge(int u,int v) { static int cnt=0; e[++cnt]=(edge){v,head[u]},head[u]=cnt; } int fa[N],dep[N],sz[N],hson[N],top[N]; int dfn[N],id[N],tim; inline 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; if (v==f) continue; dfs1(v,u),sz[u]+=sz[v]; if (sz[v]>sz[hson[u]]) hson[u]=v; } } inline void dfs2(int u,int anc) { top[u]=anc,dfn[u]=++tim,id[tim]=u; 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) struct node { int sum,lmax,rmax,ans,flag,setv; node() { sum=lmax=rmax=ans=flag=setv=0; } } t[N<<2]; 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); c.flag=c.setv=0; return c; } inline void update(int o,int l,int r,int w) { t[o].sum=(r-l+1)*w; t[o].lmax=t[o].rmax=t[o].ans=max(t[o].sum,0); t[o].flag=1,t[o].setv=w; } inline void pushup(int o) { t[o]=t[ls]+t[rs]; } inline void pushdown(int o,int l,int r) { if (t[o].flag) { int mid=(l+r)>>1; update(ls,l,mid,t[o].setv); update(rs,mid+1,r,t[o].setv); t[o].flag=t[o].setv=0; } } inline void build(int o,int l,int r) { if (l==r) { t[o].sum=a[id[l]]; t[o].lmax=t[o].rmax=t[o].ans=max(t[o].sum,0); t[o].flag=t[o].setv=0; return; } int mid=(l+r)>>1; build(ls,l,mid),build(rs,mid+1,r); pushup(o); } inline void modify(int o,int l,int r,int ql,int qr,int w) { if (ql<=l&&r<=qr) { update(o,l,r,w); return; } int mid=(l+r)>>1; pushdown(o,l,r); if (ql<=mid) modify(ls,l,mid,ql,qr,w); if (qr>mid) modify(rs,mid+1,r,ql,qr,w); pushup(o); } 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; node res; pushdown(o,l,r); if (ql<=mid) res=res+query(ls,l,mid,ql,qr); if (qr>mid) res=res+query(rs,mid+1,r,ql,qr); pushup(o); return res; } #undef ls #undef rs inline void chain_modify(int u,int v,int w) { int tu=top[u],tv=top[v]; while (tu!=tv) { if (dep[tu]<dep[tv]) swap(u,v),swap(tu,tv); modify(1,1,n,dfn[tu],dfn[u],w); u=fa[tu],tu=top[u]; } if (dep[u]<dep[v]) swap(u,v); modify(1,1,n,dfn[v],dfn[u],w); } inline int chain_query(int u,int v) { node L,R; int tu=top[u],tv=top[v]; while (tu!=tv) { if (dep[tu]<dep[tv]) { R=query(1,1,n,dfn[tv],dfn[v])+R; v=fa[tv],tv=top[v]; } else { L=query(1,1,n,dfn[tu],dfn[u])+L; u=fa[tu],tu=top[u]; } } if (dep[u]<dep[v]) R=query(1,1,n,dfn[u],dfn[v])+R; else L=query(1,1,n,dfn[v],dfn[u])+L; swap(L.lmax,L.rmax); return (L+R).ans; } int main() { n=read(); for (re int i=1;i<=n;++i) a[i]=read(); for (re int i=1;i<n;++i) { int u=read(),v=read(); addEdge(u,v),addEdge(v,u); } dfs1(1,0),dfs2(1,1),build(1,1,n); Q=read(); while (Q--) { int op=read(); if (op==1) { int u=read(),v=read(); printf("%d\n",chain_query(u,v)); } else { int u=read(),v=read(),w=read(); chain_modify(u,v,w); } } return 0; } [/collapse] GSS8 感觉还是有点难。 首先这个操作显然用平衡树维护。 注意到 $k$ 很小，考虑每个节点对于每个 $k$ 都维护一个 $ans$ 。 考虑怎么合并两个区间的信息： $$ \begin{aligned} \sum_{i=l}^ra_i(i-l+1)^k&=\left(\sum_{i=l}^{mid}a_i(i-l+1)^k\right)+\left(\sum_{i=mid+1}^ra_i(i-l+1)^k\right)\\ &=\left(\sum_{i=l}^{mid}a_i(i-l+1)^k\right)+\left(\sum_{i=mid+1}^ra_i\big((mid-l+1)-(i-mid)\big)^k\right)\\ &=\left(\sum_{i=l}^{mid}a_i(i-l+1)^k\right)+\left(\sum_{i=mid+1}^ra_i\sum_{j=0}^k{k\choose j}(mid-l+1)^{k-j}(i-mid)^{j}\right)\\ &=\left(\sum_{i=l}^{mid}a_i(i-l+1)^k\right)+\left(\sum_{j=0}^k{k\choose j}(mid-l+1)^{k-j}\sum_{i=mid+1}^ra_i(i-mid)^{j}\right)\\ &=lans_k+\left(\sum_{j=0}^k{k\choose j}(mid-l+1)^{k-j}rans_j\right) \end{aligned} $$ 这样子就很好合并了。 然后因为是平衡树，所以直接把当前节点丢到左区间（或右区间）去，然后就是两个区间合并了。 [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; #define int unsigned int 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=200000+10,K=10+10; int n,Q; int C[K][K]; inline void init() { srand(19260817); for (re int i=C[0][0]=1;i<=10;++i) for (re int j=C[i][0]=1;j<=i;++j) C[i][j]=C[i-1][j]+C[i-1][j-1]; } // fhq treap int root,tot=0; int ch[N][2],sz[N],val[N],rnd[N]; int ans[N][K],pw[K]; inline int newnode(int w) { ++tot; sz[tot]=1,val[tot]=w,rnd[tot]=rand(); for (re int i=0;i<=10;++i) ans[tot][i]=w; return tot; } inline void pushup(int x) { int ls=ch[x][0],rs=ch[x][1]; sz[x]=sz[ls]+sz[rs]+1; for (re int i=pw[0]=1;i<=10;++i) pw[i]=pw[i-1]*(sz[ls]+1); for (re int k=0;k<=10;++k) { ans[x][k]=ans[ls][k]+val[x]*pw[k]; for (re int i=0;i<=k;++i) ans[x][k]+=C[k][i]*pw[k-i]*ans[rs][i]; } } inline void split(int o,int k,int& x,int& y) { if (!o) { x=y=0; return; } if (k<=sz[ch[o][0]]) y=o,split(ch[o][0],k,x,ch[o][0]); else x=o,split(ch[o][1],k-sz[ch[o][0]]-1,ch[o][1],y); pushup(o); } inline int merge(int A,int B) { if (!A||!B) return A+B; if (rnd[A]<rnd[B]) { ch[A][1]=merge(ch[A][1],B),pushup(A); return A; } else { ch[B][0]=merge(A,ch[B][0]),pushup(B); return B; } } signed main() { init(); n=read(); for (re int i=1;i<=n;++i) root=merge(root,newnode(read())); Q=read(); while (Q--) { char op[2]; scanf("%s",op); int o,r,z; if (op[0]=='I') { int p=read()+1,w=read(); split(root,p-1,o,r); root=merge(merge(o,newnode(w)),r); } else if (op[0]=='D') { int p=read()+1; split(root,p-1,o,r),split(r,1,r,z); root=merge(o,z); } else if (op[0]=='R') { int p=read()+1,w=read(); split(root,p-1,o,r),split(r,1,r,z); val[r]=w,pushup(r); root=merge(merge(o,r),z); } else { int L=read()+1,R=read()+1,k=read(); split(root,L-1,o,r),split(r,R-L+1,r,z); printf("%u\n",ans[r][k]); root=merge(merge(o,r),z); } } return 0; } [/collapse]
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],tv=top[v],res=0; while (tu!=tv) { if (dep[tu]<dep[tv]) { swap(tu,tv); swap(u,v); } res=max(res,query(1,1,n,dfn[tu],dfn[u])); u=fa[tu],tu=top[u]; } if (dep[u]<dep[v]) swap(u,v); res=max(res,query(1,1,n,dfn[v]+1,dfn[u])); return res; } void init() { n=e_cnt=tim=0; memset(head,0,sizeof(head)); memset(hson,0,sizeof(hson)); memset(top,0,sizeof(top)); memset(maxv,0,sizeof(maxv)); } int main() { int T=read(); while (T--) { init(); n=read(); for (re int i=1;i<n;++i) { int u=read(),v=read(),w=read(); x[i]=u,y[i]=v; addEdge(u,v,w),addEdge(v,u,w); } dfs1(1,0),dfs2(1,1); build(1,1,n); while (233) { char op[10]; scanf("%s",op); if (op[0]=='D') break; if (op[0]=='C') { int i=read(),w=read(),u=dep[x[i dep[y[i]]?x[i]:y[i]; modify(1,1,n,dfn[u],w); } else { int u=read(),v=read(); if (u==v) puts("0"); else printf("%d\n",Query(u,v)); } } } return 0; } [/collapse] QTREE2 DIST 操作只需要维护树上前缀和即可求出答案。 KTH 操作大力讨论一下答案应该在 $u-lca$ 的链上还是 $v-lca$ 的链上，然后倍增上去即可求出。 所以只需要写一个倍增 LCA 和一个倍增找 $k$ 次祖先就好了。 [collapse status="false" title="SPOJ AC代码"] // =================================== // 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=10000+10; int n; struct edge { int v,w,nxt; } e[N<<1]; int head[N],e_cnt=0; inline void addEdge(int u,int v,int w) { e[++e_cnt]=(edge){v,w,head[u]},head[u]=e_cnt; } int dep[N],dis[N],f[14][N]; inline void dfs(int u,int fa) { for (re int i=1;i<=13;++i) f[i][u]=f[i-1][f[i-1][u]]; for (re int i=head[u];i;i=e[i].nxt) { int v=e[i].v,w=e[i].w; if (v==fa) continue; dep[v]=dep[u]+1,dis[v]=dis[u]+w,f[0][v]=u; dfs(v,u); } } inline int getLCA(int u,int v) { if (dep[u]<dep[v]) swap(u,v); for (re int i=13;~i;--i) if (dep[f[i][u dep[v]) u=f[i][u]; if (dep[u]!=dep[v]) u=f[0][u]; for (re int i=13;~i;--i) if (f[i][u]!=f[i][v]) u=f[i][u],v=f[i][v]; if (u!=v) u=f[0][u]; return u; } inline int find(int u,int k) { for (re int i=13;~i;--i) if (k&(1<<i)) u=f[i][u]; return u; } inline void init() { memset(head,0,sizeof(head)),e_cnt=0; } int main() { int T=read(); while (T--) { init(); n=read(); for (re int i=1;i<n;++i) { int u=read(),v=read(),w=read(); addEdge(u,v,w),addEdge(v,u,w); } dfs(1,0); while (233) { char op[10]; scanf("%s",op); if (op[1]=='O') break; if (op[0]=='D') { int u=read(),v=read(),t=getLCA(u,v); printf("%d\n",dis[u]+dis[v]-(dis[t]<<1)); } else { int u=read(),v=read(),t=getLCA(u,v),k=read(); int L=dep[u]-dep[t]+1,R=dep[v]-dep[t]+1; if (L>=k) printf("%d\n",find(u,k-1)); else printf("%d\n",find(v,R-(k-L+1))); } } } return 0; } [/collapse] QTREE3 树链剖分，每条重链开一个 set 维护所有黑点。 修改直接 insert / erase ，查询就跳重链跳到根并更新答案即可。 [collapse status="false" title="SPOJ AC代码"] // =================================== // author: M_sea // website: http://m-sea-blog.com/ // =================================== #include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <cmath> #include <set> #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=100000+10; int n,Q,c[N]; struct edge { int v,nxt; } e[N<<1]; int head[N]; inline void addEdge(int u,int v) { static int cnt=0; e[++cnt]=(edge){v,head[u]},head[u]=cnt; } int fa[N],dep[N],sz[N],hson[N],top[N]; int dfn[N],id[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; 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) { dfn[u]=++tim,id[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); } set<int> S[N]; int main() { n=read(),Q=read(); for (re int i=1;i<n;++i) { int u=read(),v=read(); addEdge(u,v),addEdge(v,u); } dfs1(1,0),dfs2(1,1); while (Q--) { int op=read(),u=read(); if (!op) { c[u]^=1; if (c[u]) S[top[u]].insert(dfn[u]); else S[top[u]].erase(dfn[u]); } else { int res=-1; while (u) { if (S[top[u]].size()) { int v=id[*S[top[u]].begin()]; if (dep[v]<=dep[u]) res=v; } u=fa[top[u]]; } printf("%d\n",res); } } return 0; } [/collapse] QTREE4 其实和捉迷藏那题是一样的... 首先建出点分树，然后每个点开两个堆，一个维护点分子树中所有白点到 $u$ 在点分树上父亲的距离，一个维护所有儿子的前一个堆的堆顶。 然后再开一个堆记一下所有点的最长链与次长链之和。那么就很好算答案了。 然后修改的话就在点分树上暴跳父亲并修改一些东西。 [collapse status="false" title="SPOJ AC代码"] // =================================== // author: M_sea // website: http://m-sea-blog.com/ // =================================== #pragma GCC optimize("Ofast") #include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <cmath> #include <queue> #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=100000+10; int n; struct edge { int v,w,nxt; } e[N<<1]; int head[N]; inline void addEdge(int u,int v,int w) { static int cnt=0; e[++cnt]=(edge){v,w,head[u]},head[u]=cnt; } struct Heap { priority_queue<int> Q,O; inline void push(int x) { Q.push(x); } inline void del(int x) { O.push(x); } inline void remove() { while (!O.empty()&&Q.top()==O.top()) Q.pop(),O.pop(); } inline int size() { return Q.size()-O.size(); } inline void pop() { remove(); Q.pop(); } inline int top() { remove(); return Q.empty()?0:Q.top(); } inline int top2() { if (size()<2) return 0; int tmp=top(); pop(); int res=top(); push(tmp); return res; } } ans,A[N],B[N]; inline void push(Heap& x) { if (x.size()>1) ans.push(x.top()+x.top2()); } inline void del(Heap& x) { if (x.size()>1) ans.del(x.top()+x.top2()); } namespace OT { int lg[N<<2],pos[N<<1],st[19][N<<2],dep[N],dis[N],tot=0; inline void dfs(int u,int fa) { st[0][++tot]=u,pos[u]=tot; for (re int i=head[u];i;i=e[i].nxt) { int v=e[i].v,w=e[i].w; if (v==fa) continue; dep[v]=dep[u]+1,dis[v]=dis[u]+w; dfs(v,u),st[0][++tot]=u; } } inline int cmp(int a,int b) { return dep[a]<dep[b]?a:b; } inline void init_rmq() { for (re int i=2;i<=tot;++i) lg[i]=lg[i>>1]+1; for (re int i=1;i<=18;++i) for (re int j=1;j+(1<<i)-1<=tot;++j) st[i][j]=cmp(st[i-1][j],st[i-1][j+(1<<(i-1))]); } inline int getdis(int u,int v) { if (pos[u]>pos[v]) swap(u,v); int t=lg[pos[v]-pos[u]+1]; int lca=cmp(st[t][pos[u]],st[t][pos[v]-(1<<t)+1]); return dis[u]+dis[v]-(dis[lca]<<1); } inline void init() { dfs(1,0); init_rmq(); } } namespace T { int sz[N],vis[N],fa[N]; int sumsz,minsz,root; inline void getroot(int u,int pa) { sz[u]=1; int now=0; for (re int i=head[u];i;i=e[i].nxt) { int v=e[i].v; if (v==pa||vis[v]) continue; getroot(v,u),sz[u]+=sz[v]; now=max(now,sz[v]); } now=max(now,sumsz-sz[u]); if (now<minsz) root=u,minsz=now; } inline void dfs(int u,int pa,int anc) { A[anc].push(OT::getdis(u,fa[anc])); for (re int i=head[u];i;i=e[i].nxt) if (e[i].v!=pa&&!vis[e[i].v]) dfs(e[i].v,u,anc); } inline void solve(int u,int pa) { vis[u]=1,fa[u]=pa; dfs(u,0,u),B[u].push(0),B[pa].push(A[u].top()); for (re int i=head[u];i;i=e[i].nxt) { int v=e[i].v; if (v==pa||vis[v]) continue; minsz=n,sumsz=sz[v]; getroot(v,u); solve(root,u); } push(B[u]); } inline void build() { root=0,minsz=sumsz=n; getroot(1,0); solve(root,0); } int col[N]; inline void whiten(int u) { del(B[u]),B[u].push(0),push(B[u]); for (re int i=u;fa[i];i=fa[i]) { del(B[fa[i]]); if (A[i].size()) B[fa[i]].del(A[i].top()); A[i].push(OT::getdis(u,fa[i])); B[fa[i]].push(A[i].top()); push(B[fa[i]]); } } inline void blacken(int u) { del(B[u]),B[u].del(0),push(B[u]); for (re int i=u;fa[i];i=fa[i]) { del(B[fa[i]]); if (A[i].size()) B[fa[i]].del(A[i].top()); A[i].del(OT::getdis(u,fa[i])); if (A[i].size()) B[fa[i]].push(A[i].top()); push(B[fa[i]]); } } inline void query() { int Q=read(),num=n; while (Q--) { char op[2]; scanf("%s",op); if (op[0]=='A') { if (!num) puts("They have disappeared."); else if (num==1) puts("0"); else printf("%d\n",max(0,ans.top())); } else { int u=read(); if (col[u]) whiten(u),col[u]=0,++num; else blacken(u),col[u]=1,--num; } } } } int main() { n=read(); for (re int i=1;i<n;++i) { int u=read(),v=read(),w=read(); addEdge(u,v,w),addEdge(v,u,w); } OT::init(); T::build(); T::query(); return 0; } [/collapse] QTREE5 显然可以动态点分治，但是这东西我再也不想写了... 考虑一个 LCT 做法。 每个节点维护一个 $lm$ 和 $rm$ ，分别表示该节点所在的 Splay 中最浅的/最深的节点能到的子树中最近的白点的距离。 考虑这个东西怎么维护。因为 $lm$ 和 $rm$ 类似，这里只考虑 $lm$ 。 显然 $lm_u$ 是以下两部分的最小值： 左子树的答案。 左子树的 $size$ + 右子树的答案 +1。 如果 $u$ 是白点的话，还要加上一部分：左子树的 $size$ 。 考虑怎么算右子树的答案。对每个节点维护一个 multiset ，维护所有虚子树的答案即可。 这个东西在 access 的时候顺便维护一下就好了。 查询就直接 makeroot ，然后查 $lm$ 就好了。 注意 makeroot 时需要 reverse ，而 reverse 时要把 $lm$ 和 $rm$ 也交换！ [collapse status="false" title="SPOJ AC代码"] // =================================== // author: M_sea // website: http://m-sea-blog.com/ // =================================== #include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <cmath> #include <set> #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=100000+10; int n,Q,col[N]; struct edge { int v,nxt; } e[N<<1]; int head[N]; inline void addEdge(int u,int v) { static int cnt=0; e[++cnt]=(edge){v,head[u]},head[u]=cnt; } struct Link_Cut_Tree { int fa[N],ch[N][2],sz[N],rev[N]; int lm[N],rm[N]; multiset<int> S[N]; int sta[N]; inline int fir(int x) { return S[x].empty()?1e9:*(S[x].begin()); } inline int nroot(int x) { return ch[fa[x]][0]==x||ch[fa[x]][1]==x; } inline void reverse(int x) { swap(ch[x][0],ch[x][1]),swap(lm[x],rm[x]),rev[x]^=1; } inline void pushup(int x) { sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1; lm[x]=min(lm[ch[x][0]],sz[ch[x][0]]+min(fir(x),lm[ch[x][1]]+1)); if (col[x]) lm[x]=min(lm[x],sz[ch[x][0]]); rm[x]=min(rm[ch[x][1]],sz[ch[x][1]]+min(fir(x),rm[ch[x][0]]+1)); if (col[x]) rm[x]=min(rm[x],sz[ch[x][1]]); } inline void pushdown(int x) { if (rev[x]) { if (ch[x][0]) reverse(ch[x][0]); if (ch[x][1]) reverse(ch[x][1]); rev[x]=0; } } inline void rotate(int x) { int y=fa[x],z=fa[y],k=(x==ch[y][1]),w=ch[x][!k]; if (nroot(y)) ch[z][ch[z][1]==y]=x; ch[x][!k]=y,ch[y][k]=w; if (w) fa[w]=y; fa[y]=x,fa[x]=z; pushup(y); } inline void splay(int x) { int y=x,z=0; sta[++z]=y; while (nroot(y)) sta[++z]=y=fa[y]; while (z) pushdown(sta[z--]); while (nroot(x)) { y=fa[x],z=fa[y]; if (nroot(y)) rotate((ch[y][0]==x)^(ch[z][0]==y)?x:y); rotate(x); } pushup(x); } inline void access(int x) { for (re int y=0;x;x=fa[y=x]) { splay(x); S[x].insert(lm[ch[x][1]]+1); ch[x][1]=y; auto it=S[x].lower_bound(lm[ch[x][1]]+1); if (it!=S[x].end()&&*it==lm[ch[x][1]]+1) S[x].erase(it); pushup(x); } } inline void makeroot(int x) { access(x),splay(x),reverse(x); } } T; inline void dfs(int u,int f) { T.fa[u]=f; for (re int i=head[u];i;i=e[i].nxt) { int v=e[i].v; if (v==f) continue; T.S[u].insert(1e9),T.pushup(u); dfs(v,u); } } int main() { T.lm[0]=T.rm[0]=1e9; n=read(); for (re int i=1;i<n;++i) { int u=read(),v=read(); addEdge(u,v),addEdge(v,u); } dfs(1,0); Q=read(); while (Q--) { int op=read(),u=read(); if (!op) { T.makeroot(u); col[u]^=1,T.pushup(u); } else { T.makeroot(u); printf("%d\n",T.lm[u]>n?-1:T.lm[u]); } } return 0; } [/collapse] QTREE6 维护两个 LCT ，一棵维护白点，一棵维护黑点。每次修改暴力 cut 再 link 即可。 然而这样子会被菊花图卡爆。 考虑一种我不会的套路：把 $u$ 的颜色作为 $(u,fa_u)$ 边的颜色。 同样维护两个 LCT ，一棵维护白边，一棵维护黑边。 可以发现每次修改只需要在一棵树中 cut 掉父边，再在另一棵树中 link 父边即可。 查询就直接 findroot ，然后输出重儿子的大小即可。子树大小按照维护子树信息那一套维护。 一个要注意的地方：这棵树被我们强制成了有根树，所以不能 makeroot 。 另一个要注意的地方：根节点要建一个虚点当它的父节点，这样子根节点才会有父边。 [collapse status="false" title="SPOJ AC代码"] // =================================== // 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=100000+10; int n,Q,c[N]; struct edge { int v,nxt; } e[N<<1]; int head[N]; inline void addEdge(int u,int v) { static int cnt=0; e[++cnt]=(edge){v,head[u]},head[u]=cnt; } struct Link_Cut_Tree { int fa[N],ch[N][2],s[N],si[N]; inline void init() { for (re int i=1;i<=n+1;++i) s[i]=1; } inline int nroot(int x) { return ch[fa[x]][0]==x||ch[fa[x]][1]==x; } inline void pushup(int x) { s[x]=s[ch[x][0]]+s[ch[x][1]]+si[x]+1; } inline void rotate(int x) { int y=fa[x],z=fa[y],k=(x==ch[y][1]),w=ch[x][!k]; if (nroot(y)) ch[z][ch[z][1]==y]=x; ch[x][!k]=y,ch[y][k]=w; if (w) fa[w]=y; fa[y]=x,fa[x]=z; pushup(y); } inline void splay(int x) { while (nroot(x)) { int y=fa[x],z=fa[y]; if (nroot(y)) rotate((ch[y][0]==x)^(ch[z][0]==y)?x:y); rotate(x); } pushup(x); } inline void access(int x) { for (re int y=0;x;x=fa[y=x]) splay(x),si[x]+=s[ch[x][1]],si[x]-=s[ch[x][1]=y]; } inline int findroot(int x) { access(x),splay(x); while (ch[x][0]) x=ch[x][0]; splay(x); return x; } inline void link(int x,int y) { splay(x),access(y),splay(y); fa[x]=y,si[y]+=s[x],s[y]+=s[x]; } inline void cut(int x,int y) { access(x),splay(x); ch[x][0]=fa[ch[x][0]]=0; pushup(x); } } T[2]; int fa[N]; inline void dfs(int u,int f) { fa[u]=f,T[0].link(u,f); for (re int i=head[u];i;i=e[i].nxt) if (e[i].v!=f) dfs(e[i].v,u); } int main() { n=read(); T[0].init(),T[1].init(); for (re int i=1;i<n;++i) { int u=read(),v=read(); addEdge(u,v),addEdge(v,u); } dfs(1,n+1); Q=read(); while (Q--) { int op=read(),u=read(); if (op) T[c[u]].cut(u,fa[u]),c[u]^=1,T[c[u]].link(u,fa[u]); else { int rt=T[c[u]].findroot(u); printf("%d\n",T[c[u]].s[T[c[u]].ch[rt][1]]); } } return 0; } [/collapse] QTREE7 和 QTREE6 差不多，每个节点开一个 multiset 维护虚儿子的最大值即可。 然后 link 的时候连虚边有点麻烦，可以直接连实边。 [collapse status="false" title="SPOJ AC代码"] // =================================== // author: M_sea // website: http://m-sea-blog.com/ // =================================== #include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <cmath> #include <set> #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=100000+10; int n,Q; int c[N],w[N]; struct edge { int v,nxt; } e[N<<1]; int head[N]; inline void addEdge(int u,int v) { static int cnt=0; e[++cnt]=(edge){v,head[u]},head[u]=cnt; } struct Link_Cut_Tree { int fa[N],ch[N][2],mx[N]; multiset<int> S[N]; inline int nroot(int x) { return ch[fa[x]][0]==x||ch[fa[x]][1]==x; } inline void pushup(int x) { mx[x]=max(w[x],max(mx[ch[x][0]],mx[ch[x][1]])); if (S[x].size()) mx[x]=max(mx[x],*S[x].rbegin()); } inline void rotate(int x) { int y=fa[x],z=fa[y],k=(x==ch[y][1]),w=ch[x][!k]; if (nroot(y)) ch[z][ch[z][1]==y]=x; ch[x][!k]=y,ch[y][k]=w; if (w) fa[w]=y; fa[y]=x,fa[x]=z; pushup(y); } inline void splay(int x) { while (nroot(x)) { int y=fa[x],z=fa[y]; if (nroot(y)) rotate((ch[y][0]==x)^(ch[z][0]==y)?x:y); rotate(x); } pushup(x); } inline void access(int x) { for (re int y=0;x;x=fa[y=x]) { splay(x); if (ch[x][1]) S[x].insert(mx[ch[x][1]]); ch[x][1]=y; if (ch[x][1]) S[x].erase(mx[ch[x][1]]); pushup(x); } } inline int findroot(int x) { access(x),splay(x); while (ch[x][0]) x=ch[x][0]; splay(x); return x; } inline void link(int x,int y) { splay(x),access(y),splay(y); fa[x]=y,ch[y][1]=x,pushup(y); } inline void cut(int x,int y) { access(x),splay(x); ch[x][0]=fa[ch[x][0]]=0; pushup(x); } } T[2]; int fa[N]; inline void dfs(int u,int f) { fa[u]=f,T[c[u]].link(u,f); for (re int i=head[u];i;i=e[i].nxt) if (e[i].v!=f) dfs(e[i].v,u); } int main() { n=read(); for (re int i=1;i<n;++i) { int u=read(),v=read(); addEdge(u,v),addEdge(v,u); } for (re int i=1;i<=n;++i) c[i]=read(); for (re int i=1;i<=n;++i) w[i]=read(); T[0].mx[0]=T[1].mx[0]=-2e9; dfs(1,n+1); Q=read(); while (Q--) { int op=read(),u=read(); if (op==0) { int rt=T[c[u]].findroot(u); printf("%d\n",T[c[u]].mx[T[c[u]].ch[rt][1]]); } else if (op==1) { T[c[u]].cut(u,fa[u]),c[u]^=1,T[c[u]].link(u,fa[u]); } else { T[c[u]].access(u),T[c[u]].splay(u); w[u]=read(); T[c[u]].pushup(u); } } return 0; } [/collapse]