ToB企服应用市场:ToB评测及商务社交产业平台

标题: P9058 [Ynoi2004] rpmtdq 与 P9678 [ICPC2022 Jinan R] Tree Distance [打印本页]

作者: 曂沅仴駦 时间: 2024-7-29 20:05
标题: P9058 [Ynoi2004] rpmtdq 与 P9678 [ICPC2022 Jinan R] Tree Distance
思路：

留意到点对数量有 \(N^2\) 个，思量丢掉一些无用的点对。
对于点对 \((x_1,y_1),(x_2,y_2)\)，满意 \(x_1 \le x_2 < y_2 \le y_1\)，即区间 \([x_2,y_2]\) 被 \([x_1,y_1]\) 包含，此时满意若询问到了 \([x_1,y_1]\)，则一定会询问到 \([x_2,y_2]\)。
若满意 \(\operatorname{dis}(x_1,y_1) \ge \operatorname{dis}(x_2,y_2)\)，那么此时可以将 \((x_1,y_1)\) 舍弃，因为若要用 \((x_1,y_1\)) 的贡献，不如直接去看 \((x_2,y_2)\) 的贡献，究竟 \((x_1,y_1)\) 的贡献一定不会比 \((x_2,y_2)\) 更优。
那么我们可以定义若两个点对 \((x_1,y_1),(x_2,y_2)\) 满意以下条件，则称 \((x_1,y_1)\) 被 \((x_2,y_2)\) 支配：

\(x_1 \le x_2 < y_2 \le y_1\)。
\(\operatorname{dis}(x_1,y_1) \ge \operatorname{dis}(x_2,y_2)\)。

此时定义一个支配点对满意没有被任何一个点对支配，即我们需要找出全部的支配点对来计算贡献。
留意到是一个树上点对间隔问题，思量点分治办理。
令当前分治重心为 \(rt\)，对于点 \(v\)，令 \(S_v\) 表示当前联通块中全部满意 \(\operatorname{dis}(i,rt) \le \operatorname{dis}(v,rt)\) 的 \(i\) 组成的一个聚集。
那么可以与 \(v\) 组成支配点对的点一定是 \(S_v\) 中 \(v\) 的前驱和后继，即 \(S_v\) 中 \(v\) 中最小的数。
简单证一下，设 \(S_v\) 中 \(v\) 的前驱为 \(u\)：

有 \(\operatorname{dis}(i,u) \le \operatorname{dis}(i,rt) + \operatorname{dis}(u,rt) \le \operatorname{dis}(i,rt) + \operatorname{dis}(v,rt) = \operatorname{dis}(i,v)\)，即 \(\operatorname{dis}(i,u) \le \operatorname{dis}(i,v)\)。
留意到此时 \(i < u < v\) 或 \(u < v < i\)，即 \((i,v)\) 被 \((i,u)\) 支配或 \((u,i)\) 被 \((v,i)\) 支配。
那么只有当 \(i=u\) 时，\((u,u)\) 点对不存在，\((u,v)\) 不会被别的 \(S_v\) 中的点对支配。

后继情况类似，就不多说了。
然后思量如何快速找到支配点对，直接按照上面的方法找 \(S_v\)，复杂度肯定是 \(O(N^2)\) 起步，思量优化。
首先对于整个联通块的全部点，按照点的编号排序升序，然后维护一个 \(\operatorname{dis}(i,rt)\) 不降的单调栈。
那么有一个性子是，对于被点 \(i\) 弹出去的点 \(u\)，肯定满意 \(i\) 是 \(u\) 后面第一个小于等于 \(\operatorname{dis}(u,rt)\) 的点且编号最小，即 \(i\) 是 \(S_u\) 中 \(u\) 的前驱；然后再倒着降序做一遍单调栈找后继即可。
此时我们来估算一下支配点对的数量，每个点最多被 \(\log N\) 个分治重心包含，每次包含最多增加 \(2\) 对支配点对，即总支配点对的数量为 \(N \log N\) 左右。
现在求出了全部的支配点对，即有贡献的点对，现在思量如何求被一个区间包含的全部支配点对的最小贡献值，可以在线使用树套树，但是没须要。
思量离线使用扫描线算法，因为树状数组不好维护后缀最值，思量倒着扫左端点，然后对于每个点对，在左端点处将右端点贡献加入进去；那么对于一个在左端点的询问，就是一个前缀最小值。
时间复杂度为 \(O(N \log^2 N + Q \log N)\)。
完整代码：

[code]#include#define Add(x,y) (x+y>=mod)?(x+y-mod)

x+y)#define lowbit(x) x&(-x)#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x#define Full(a) memset(a,0,sizeof(a))#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);using namespace std;typedef double db;typedef unsigned long long ull;typedef long long ll;const ll N=2e5+10,M=1e6+10,INF=1e18; bool Begin;inline ll read(){ ll x=0,f=1; char c=getchar(); while(c'9'){ if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)