题目链接
题解
CDQ分治神题。。。
难想难写。。
比较朴素的思想是对于每个询问都求一遍(BST)，这样做显然会爆
考虑一下时间都浪费在了什么地方
我们每次求(BST)实际上就只有一条边不同，我们实际浪费了很多时间在处理相同的边上
那就考虑分治
对于一个待修改的边集，我们将其权值全部设为(-infty)，跑一遍(BST)，此时其它边如果被选中，说明这些边在单独询问时也一定会被选，将这些边连的点缩点
同样，对于一个待修改的边集，我们将其权值全部设为(infty)，跑一遍(BST)，此时其它边没被选中，说明这些边在单独询问时也一定不会被选，将这些边删掉
这样就可以(A)了
复杂度我也不知道是什么
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<map>
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define mp(a,b) make_pair<int,int>(a,b)
#define cls(s) memset(s,0,sizeof(s))
#define cp pair<int,int>
#define LL long long int
using namespace std;
const int maxn = 50005,maxm = 50005,INF = 0x3fffffff;
inline int read(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}
return out * flag;
}
struct EDGE{int i,a,b,w;}e[50][maxm],d[maxm],b[maxm];
struct Que{int u,v;}q[maxm];
inline bool operator <(const EDGE& a,const EDGE& b){
return a.w < b.w;
}
LL ans[maxm];
int n,m,Q,sum[50],w[maxm],id[maxm],a[maxm];
int pre[maxm];
int find(int u){return u == pre[u] ? u : pre[u] = find(pre[u]);}
void clear(int t){
for (int i = 1; i <= t; i++){
pre[d[i].a] = d[i].a;
pre[d[i].b] = d[i].b;
}
}
void comb(int& t,LL& Ans){
clear(t); int tmp = 0,fa,fb;
sort(d + 1,d + 1 + t);
REP(i,t){
fa = find(d[i].a); fb = find(d[i].b);
if (fa != fb){
pre[fb] = fa;
b[++tmp] = d[i];
}
}
REP(i,tmp) {
pre[b[i].a] = b[i].a;
pre[b[i].b] = b[i].b;
}
REP(i,tmp) if (b[i].w != -INF){
fa = find(b[i].a); fb = find(b[i].b);
if (fa != fb){
pre[fb] = fa;
Ans += b[i].w;
}
}
tmp = 0;
REP(i,t){
fa = find(d[i].a); fb = find(d[i].b);
if (fa != fb){
b[++tmp] = d[i];
id[d[i].i] = tmp;
b[tmp].a = find(b[tmp].a);
b[tmp].b = find(b[tmp].b);
}
}
REP(i,tmp) d[i] = b[i];
t = tmp;
}
void rd(int& t){
clear(t); int tmp = 0,fa,fb;
sort(d + 1,d + 1 + t);
REP(i,t){
fa = find(d[i].a); fb = find(d[i].b);
if (fa != fb){
pre[fb] = fa;
b[++tmp] = d[i];
}
else if (d[i].w == INF){
b[++tmp] = d[i];
}
}
for (int i = 1; i <= tmp; i++) d[i] = b[i];
t = tmp;
}
void solve(int l,int r,int now,LL Ans){
int t = sum[now];
if (l == r) a[q[l].u] = q[l].v; //原标号边权值
for (int i = 1; i <= t; i++)
e[now][i].w = a[e[now][i].i]; //边赋值
for (int i = 1; i <= t; i++)
d[i] = e[now][i],id[d[i].i] = i; //新边对应旧边位置
if (l == r){
ans[l] = Ans; clear(t);
sort(d + 1,d + 1 + t);
int fa,fb;
for (int i = 1; i <= t; i++){
fa = find(d[i].a); fb = find(d[i].b);
if (fa != fb){
pre[fb] = fa; ans[l] += d[i].w;
}
}
return;
}
for (int i = l; i <= r; i++) d[id[q[i].u]].w = -INF;
comb(t,Ans);
for (int i = l; i <= r; i++) d[id[q[i].u]].w = INF;
rd(t);
REP(i,t) e[now + 1][i] = d[i];
sum[now + 1] = t;
int mid = l + r >> 1;
solve(l,mid,now + 1,Ans);
solve(mid + 1,r,now + 1,Ans);
}
int main(){
n = read(); m = read(); Q = read();
for (int i = 1; i <= m; i++){
e[0][i].i = i;
e[0][i].a = read();
e[0][i].b = read();
a[i] = e[0][i].w = read();
}
for (int i = 1; i <= Q; i++){
q[i].u = read();
q[i].v = read();
}
sum[0] = m;
solve(1,Q,0,0);
for (int i = 1; i <= Q; i++)
printf("%lld
",ans[i]);
return 0;
}