题面
在Byteland一共有n 个城市，编号依次为1 到n，它们之间计划修建m条双向道路，其中修建第i 条道路的费用为ci。
Byteasar作为Byteland 公路建设项目的总工程师，他决定选定一个区间[l, r]，仅使用编号在该区间内的道路。他希望选择一些道路去修建，使得连通块的个数尽量少，同时，他不喜欢修建多余的道路，因此每个连通块都可以看成一棵树的结构。
为了选出最佳的区间，Byteasar 会不断选择q 个区间，请写一个程序，帮助Byteasar 计算每个区间内修建公路的最小总费用。
30~60
30分暴力；
60分，考虑到由于边的权值随编号递增，所以对于一个询问区间([l,r])，显然能往前取，尽量往前取。
所以，我们把边从大到小加入，对树的结构每次加边后暴力重构，方便加边时LCA。
然后对于一个区间([l,r])，就要把([l,m])的边，然后我用数据结构找生成树中编号小于(r)的权值和。
100
开棵线段树，树上每个结点表示，使用区间内的边生成的mst，最多存储(O(n))条边，空间就有(O(n*m*log_m))
然后我对于每个询问就只需(O(log_m*n))的时间。
总的时间复杂度为(O(log_m*n*q))。
为什么可以用线段树
前提条件：离线；
关键条件：区间合并只需(O(n))。
Code
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#define ll long long
#define fo(i,x,y) for(int i=x;i<=y;i++)
#define fd(i,x,y) for(int i=x;i>=y;i--)
using namespace std;
const char* fin="highway.in";
const char* fout="highway.out";
const int maxn=107,maxm=100007,maxt=maxm*4;
int n,m,q,t[maxn*2];
struct line{
int x,y,z;
}a[maxm];
struct node{
node(){r[0]=0;}
int r[maxn];
}c[maxt],ans,tmp;
struct bitch{
int data[maxm],az[maxm],id;
bitch(){memset(az,0,sizeof az);id=0;}
void init(){id++;}
int& operator [](const int &v){
if (az[v]<id) az[v]=id,data[v]=0;
return data[v];
}
}dad;
int getdad(int v){return dad[v]==0?v:dad[v]=getdad(dad[v]);}
void merge(node &v,const node &b,const node &c){
t[0]=0;
int i=1,j=1;
while (i<=b.r[0] && j<=c.r[0])
if (a[b.r[i]].z<a[c.r[j]].z) t[++t[0]]=b.r[i++];
else t[++t[0]]=c.r[j++];
while (i<=b.r[0]) t[++t[0]]=b.r[i++];
while (j<=c.r[0]) t[++t[0]]=c.r[j++];
v.r[0]=0;
dad.init();
fo(i,1,t[0]){
int j=getdad(a[t[i]].x),k=getdad(a[t[i]].y);
if (j!=k){
dad[j]=k;
v.r[++v.r[0]]=t[i];
}
}
}
void plant(int l,int r,int t){
int mid=(l+r)/2;
if (l==r){
c[t].r[0]=1;
c[t].r[1]=l;
return;
}
plant(l,mid,t*2);
plant(mid+1,r,t*2+1);
merge(c[t],c[t*2],c[t*2+1]);
}
node query(int l,int r,int t,int v1,int v2){
int mid=(l+r)/2;
if (l>v2 || r<v1) return node();
if (l>=v1 && r<=v2) return c[t];
merge(tmp,query(l,mid,t*2,v1,v2),query(mid+1,r,t*2+1,v1,v2));
return tmp;
}
int main(){
freopen(fin,"r",stdin);
freopen(fout,"w",stdout);
scanf("%d%d%d",&n,&m,&q);
fo(i,1,m){
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
}
plant(1,m,1);
fo(i,1,q){
int l,r;
scanf("%d%d",&l,&r);
ans=query(1,m,1,l,r);
int Ans=0;
fo(j,1,ans.r[0]) Ans+=a[ans.r[j]].z;
printf("%d
",Ans);
}
return 0;
}