题面

在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
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #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]
          
           v2 || r
           
            =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\n",Ans); } return 0;}