例题一：区间最小生成树
#include<bits/stdc++.h> using namespace std; #define re register int #define LL long long static char buf[1<<20], *p1=buf, *p2=buf; #define getchar() p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<20, stdin), p1==p2)?EOF:*p1++ inline int read() { int x=0;char c=getchar(); while(c<‘0‘||c>‘9‘)c=getchar(); while(‘0‘<=c&&c<=‘9‘)x=x*10+c-48,c=getchar(); return x; } const int N=30005; int n, m, q; int fa[N];int getf(int x){return x==fa[x]?x:fa[x]=getf(fa[x]);} struct node{int x, y, z;}rdin[N]; vector<node> G[N<<3]; vector<node> update(vector<node>A, vector<node>B) { vector<node>ret; ret.clear(); int i=0, j=0, cnt=0; int p=A.size(), q=B.size(); for(re o=1;o<=n;++o)fa[o]=o; while(i<p&&j<q&&cnt<n-1) { if(A[i].z<=B[j].z) { int f1=getf(A[i].x), f2=getf(A[i].y); if(f1!=f2) { cnt++; fa[f1]=f2; ret.push_back(A[i]); } i++; } else { int f1=getf(B[j].x), f2=getf(B[j].y); if(f1!=f2) { cnt++; fa[f1]=f2; ret.push_back(B[j]); } j++; } } while(i<p&&cnt<n-1) { int f1=getf(A[i].x), f2=getf(A[i].y); if(f1!=f2) { cnt++; fa[f1]=f2; ret.push_back(A[i]); } i++; } while(j<q&&cnt<n-1) { int f1=getf(B[j].x), f2=getf(B[j].y); if(f1!=f2) { cnt++; fa[f1]=f2; ret.push_back(B[j]); } j++; } return ret; } void modi(int p, int l, int r, int id, node w) { if(l == id && id == r) { G[p].clear(); G[p].push_back(w); return; } int mid=(l+r)>>1, ls=(p<<1), rs=(p<<1|1); if(id <= mid) modi(ls, l, mid, id, w); else modi(rs, mid+1, r, id, w); G[p] = update(G[ls], G[rs]); } void build(int p, int l, int r) { if(l == r) { G[p].push_back(rdin[l]); return; } int mid=(l+r)>>1, ls=(p<<1), rs=(p<<1|1); build(ls, l, mid); build(rs, mid+1, r); G[p]=update(G[ls], G[rs]); } vector<node> query(int p, int l, int r, int x, int y) { if(x <= l && r <= y) return G[p]; int mid=(l+r)>>1, ls=(p<<1), rs=(p<<1|1); if(x<=mid && y<=mid)return query(ls, l, mid, x, y); if(x>mid && y>mid)return query(rs, mid+1, r, x, y); vector<node>A, B; A=query(ls, l, mid, x, y); B=query(rs, mid+1, r, x, y); return update(A, B); } int work(vector<node>A) { for(re i=1;i<=n;++i)fa[i]=i; int k=0, sz = A.size(), ret=0, cnt=0; while(k<sz && cnt<n-1) { int f1=getf(A[k].x), f2=getf(A[k].y), v=A[k].z; if(f1!=f2) { fa[f1]=f2; ret+=v; cnt++; } k++; } return cnt==n-1?ret:-1; } int main() { n=read();m=read();q=read(); for(re i=1;i<=m;++i) { int x=read(), y=read(), z=read(); rdin[i]=(node){x, y, z}; } build(1, 1, m); while(q--) { int t, k, x, y, z; t=read(); if(t==1) { k=read();x=read();y=read();z=read(); modi(1, 1, m, k, (node){x, y, z}); } else { x=read();y=read(); int Ans = work(query(1, 1, m, x, y)); if(Ans == -1) puts("Impossible"); else printf("%d\n", Ans); } } return 0; }
例题二：城市建设
#include<bits/stdc++.h> using namespace std; #define re register int #define LL long long #define py pair<int,int> #define fi first #define se second static char buf[1<<20], *p1=buf, *p2=buf; #define getchar() p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<20, stdin), p1==p2)?EOF:*p1++ inline int read() { int x=0; char c=getchar(); while(c<‘0‘||c>‘9‘)c=getchar(); while(‘0‘<=c&&c<=‘9‘)x=(x<<3)+(x<<1)+c-48,c=getchar(); return x; } const int N=5e4+5, INF=1e9; struct node{ int x, y, v, id; bool operator<(const node&p)const{ return v < p.v; } }; node E[30][N], t[N], nw[N]; int rak[N], A[N]; LL Ans[N]; py ask[N]; int fa[N];int getf(int x){return x==fa[x]?x:fa[x]=getf(fa[x]);} LL suodian(int &tot) {// 合并一定需要的边 for(re i=1;i<=tot;++i) fa[t[i].x]=t[i].x, fa[t[i].y]=t[i].y; int cnt=0; LL val=0; sort(t+1, t+1+tot); for(re i=1;i<=tot;++i) { int x=t[i].x, y=t[i].y; if(getf(x)!=getf(y)) { fa[getf(x)]=getf(y); nw[++cnt]=t[i]; } } for(re i=1;i<=cnt;++i) fa[nw[i].x]=nw[i].x, fa[nw[i].y]=nw[i].y; for(re i=1;i<=cnt;++i) { int x=nw[i].x, y=nw[i].y, v=nw[i].v; if(v!=-INF) { fa[getf(x)]=getf(y); val += v; } } cnt=0; for(re i=1;i<=tot;++i) { int x=t[i].x, y=t[i].y; if(getf(x)!=getf(y)) { nw[++cnt]=t[i]; nw[cnt].x=getf(x); nw[cnt].y=getf(y); rak[t[i].id]=cnt; } } tot=cnt; for(re i=1;i<=tot;++i)t[i]=nw[i]; return val; } void qubian(int &tot) { // 去除一定不需要的边 for(re i=1;i<=tot;++i) fa[t[i].x]=t[i].x, fa[t[i].y]=t[i].y; int cnt=0; sort(t+1, t+1+tot); for(re i=1;i<=tot;++i) { int x=t[i].x, y=t[i].y, v=t[i].v; if(getf(x)==getf(y)) { if(v==INF) nw[++cnt]=t[i]; } else { fa[getf(x)]=getf(y); nw[++cnt]=t[i]; } } tot=cnt; for(re i=1;i<=tot;++i)t[i]=nw[i]; } void CDQ(int l, int r, int d, int tot, LL val) {// 左，右，深度，边的总数，合并成点的贡献 if(l == r) A[ask[l].fi] = ask[l].se; // 更新边权 for(re i=1;i<=tot;++i) { t[i] = E[d][i]; // 继承 t[i].v = A[t[i].id]; // 边权更新 rak[t[i].id] = i; // 原边在新数组中的编号 } if(l == r) { for(re i=1;i<=tot;++i) fa[t[i].x] = t[i].x, fa[t[i].y] = t[i].y; sort(t+1, t+1+tot);//kruskal Ans[l] = val; for(re i=1;i<=tot;++i) { int x=t[i].x, y=t[i].y, v=t[i].v; if(getf(x) != getf(y)) { fa[getf(x)] = getf(y); Ans[l] += v; } } return; } for(re i=l;i<=r;++i) t[rak[ask[i].fi]].v = -INF; val += suodian(tot); for(re i=l;i<=r;++i) t[rak[ask[i].fi]].v = INF; qubian(tot); for(re i=1;i<=tot;++i) E[d+1][i] = t[i]; int mid = (l+r)>>1; CDQ(l, mid, d+1, tot, val); CDQ(mid+1, r, d+1, tot, val); } int main() { int n=read(), m=read(), q=read(); for(re i=1;i<=n;++i)fa[i]=i; for(re i=1;i<=m;++i) { int x=read(), y=read(), z=read(); A[i]=z; // 原边权记录一下 E[0][i]=(node){x, y, z, i}; // 左右端点，边权，在原数组的编号 } for(re i=1;i<=q;++i) { int x=read(), y=read(); ask[i]=py(x, y); } CDQ(1, q, 0, m, 0); // 分治 for(re i=1;i<=q;++i)printf("%lld\n", Ans[i]); return 0; }