题解：P13342 [EGOI 2025] Wind Turbines / 风力涡轮机
Fenki_lo
·
·
题解
P13342 [EGOI 2025] Wind Turbines / 风力涡轮机
很好的风力，使我脑子旋转。
题意
给定一个 n 个点 m 条边的无向连通图，每条边有边权，现在给定 q 次询问，每次询问给定 l,r，表示当编号在 [l,r] 内的点都成为“有根点”，求让所有点都直接或间接和至少一个“有根点”连通的选择边的边权。
## 思路
当 $l_i=r_i$ 时，显然答案为最小生成树。
接下来往下考虑 $r_i=l_i+1$ 的情况，那么就是最小生成树的总边权减去 $l_i$ 到 $r_i$ 在最小生成树路径上的最大边，这个显然可以用 kruskal 最小重构树做，相当于查询 $l_i$ 与 $r_i$ 在 重构树上的 lca 点权。
扩展到普遍情况，那么相当于查询区间 $[l_i,r_i]$ 内的点在重构树上两两的 lca 的并集的点权和。由于重构树上的每一个点都代表一次合并，那么区间内 $k=r_i-l_i+1$ 就恰好有 $k-1$ 个不同的 lca，于是问题转换为求这 $k-1$ 个 lca 的点权和。
考虑一个重构树上的节点什么时候会贡献。因为重构树每个非叶子节点都有两个儿子，因此若存在 $x,y(x<y)$ 分别存在于它的两个儿子的子树中，则这个点可以贡献给包含 $[x,y]$ 区间的 $[l,r]$ 贡献。同时由于每个这样的节点只能贡献一次，因此在固定了一边的 $x$ 时，对于这个节点我们选取最小的 $y$ 总是最优的。
于是我们考虑预处理出所有可能贡献的点对 $(x,y,w_u)$。我们可以维护左右儿子子树内叶子内编号的集合，对于一个集合内的点 $x$，在另一个集合内找其第一个比它大的点与最大的比它小的点构造贡献点对（前驱后继），然后每次计算完贡献点对后启发式合并。
具体地，我们可以用 set 去维护，计算贡献、合并时比较两个 set 的大小即可。
转变为在二维平面上的点，$l$ 为横轴，$r$ 为纵轴，每个询问、贡献点对都转变为一个点，那么 $(x,y)$ 可以贡献给在它左上角的所有询问点。这显然可以使用扫描线与树状数组处理，但要将 $l$ 从 $n$ 往 $1$ 扫，同时要先加贡献点再查询询问点。具体看代码。
同时我们要注意，由于一个点不可以重复贡献给一个询问，因此对于每个 $w_u$ 需要记录一个最小的 $r$，即在二维平面上最低的纵轴坐标。具体原因如下：
如图，现在我们有两个相同贡献了 $w_u$ 的点。
他们分别可以贡献给蓝色矩形与红色矩形，但实际上我们只能取并，因此它的实际贡献为绿色边围起来的部分。
因为我们是将横轴从大往小扫，于是我们要转换成这两个橙色的矩形去贡献。
所以要记录每个相同 $w_u$ 的最小 $r$。
复杂度 $\Omicron(n\log^2n)$，视 $n,m,q$ 同阶。瓶颈还是在于启发式合并。
## 代码
```cpp
#include<bits/stdc++.h>
#define ll long long
#define rt ((n<<1)-1)
#define s(a) son[u][a]
#define si set<ll>::iterator
using namespace std;
template<typename T> inline void read(T &x){
x=0;
T w=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-') w=-1;
c=getchar();
}
while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
x*=w;
}
template<typename T> inline void write(T x){
if(x<0) putchar('-'),x=(~x)+1;
if(x>9) write(x/10);
putchar(x%10^48);
}
const ll N=4e5+10;
ll n,m,q;
struct ed{
ll u,v,w;
}p[N];
bool cmp(ed a,ed b){
return a.w<b.w;
}
ll pt[N],f[N],son[N][2];
ll head[N],id,sum,siz[N];
ll fin(ll x){
return f[x]==x ? x : f[x]=fin(f[x]);
}
void rebuild(){
sort(p+1,p+m+1,cmp);
ll cnt=n;
for(int i=1;i<=(n<<1);i++) f[i]=i;
for(int i=1;i<=m;i++){
ll xx=fin(p[i].u),yy=fin(p[i].v);
if(xx!=yy){
cnt++;
son[cnt][0]=xx,son[cnt][1]=yy;
f[xx]=f[yy]=cnt;
pt[cnt]=p[i].w;
sum+=p[i].w;
}
}
}
set<ll>s[N];
ll t[N];
struct ran{
ll y,w_id;
};
vector<ran>v[N];
struct query{
ll r,id;
};
vector<query>que[N];
void dfs(ll u){
siz[u]=1;
if(u<=n) s[u].insert(u),t[u]=u;
else{
for(int i=0;i<=1;i++) dfs(s(i)),siz[u]+=siz[s(i)];
ll tag=0;
if(siz[s(0)]>siz[s(1)]) tag=1,t[u]=t[s(0)];
else tag=0,t[u]=t[s(1)];
for(si it=s[t[s(tag)]].begin();it!=s[t[s(tag)]].end();it++){
si it1=s[t[s(tag^1)]].upper_bound(*it);
if(it1!=s[t[s(tag^1)]].end()) v[*it].push_back({*it1,u});
if(it1!=s[t[s(tag^1)]].begin()){
it1--;
v[*it1].push_back({*it,u});
}
}
for(si it=s[t[s(tag)]].begin();it!=s[t[s(tag)]].end();it++) s[t[s(tag^1)]].insert(*it);
}
}
ll tr[N],mi[N],ans[N];
void add(ll i,ll z){
for(;i<=n;i+=i&-i) tr[i]+=z;
}
ll num(ll i){
ll res=0;
for(;i;i-=i&-i) res+=tr[i];
return res;
}
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
read(n),read(m),read(q);
for(int i=1;i<=m;i++){
read(p[i].u),read(p[i].v),read(p[i].w);
p[i].u++,p[i].v++;
}
rebuild();
dfs(rt);
for(int i=1;i<=q;i++){
ll l,r;
read(l),read(r);
l++,r++;
que[l].push_back({r,i});
}
for(int i=1;i<=(n<<1);i++) mi[i]=n+1;
for(int i=n;i>=1;i--){
for(auto p : v[i]){
if(p.y>=mi[p.w_id]) continue;
add(p.y,pt[p.w_id]);
add(mi[p.w_id],-pt[p.w_id]);
mi[p.w_id]=min(mi[p.w_id],p.y);
}
for(auto p : que[i]) ans[p.id]=sum-num(p.r);
}
for(int i=1;i<=q;i++) write(ans[i]),putchar('\n');
return 0;
}
```