[jzoj 5060] [GDOI 2017 2 차 시 뮬 레이 션 day 1] [도로 건설] [데이터 구조]

제목 의 대의
Byteland 에는 모두 n 개의 도시 가 있 는데 번 호 는 1 에서 n 이다. 그들 사이 에 m 개의 양 방향 도 로 를 건설 할 계획 이다. 그 중에서 i 조 도 로 를 건설 하 는 비용 은 ci 이다.
Byteasar 는 Byteland 도로 건설 프로젝트 의 총 엔지니어 로 서 그 는 구간 [l, r] 을 선정 하여 이 구간 안의 도로 번호 만 사용 하기 로 결정 했다.그 는 일부 도 로 를 선택 하여 건설 하 기 를 희망 하여 연결 블록 의 개 수 를 최대한 적 게 하 는 동시에 그 는 불필요 한 도 로 를 건설 하 는 것 을 좋아 하지 않 기 때문에 모든 연결 블록 은 나무의 구조 로 볼 수 있다.
가장 좋 은 구간 을 선택 하기 위해 서 Byteasar 는 q 개 구간 을 계속 선택 할 것 입 니 다. 프로그램 을 써 서 Byteasar 가 각 구간 내 에 도 로 를 건설 하 는 최소 총 비용 을 계산 하 는 데 도움 을 주 십시오.
문제 풀이 의 사고 방향.
선분 트 리 로 각 구간 변 의 mst 를 유지 하고 병합 하여 동 리 를 조회 합 니 다.
code

#include
#include
#include
#include
#include
#define LD double
#define LL long long
#define ULL unsigned long long
#define min(a,b) ((a
#define max(a,b) ((a>b)?a:b)
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fd(i,j,k) for(int i=j;i>=k;i--)
#define fr(i,j) for(int i=begin[j];i;i=next[i])
using namespace std;
int const mn=100+9,mm=1e5+9,inf=1e9;
int n,m,q,cnt,fa[mn];
struct rec{
    int u,v,c;
};
rec a[mm];
struct rec2{
    int size,ans;
    rec a[101];
};
rec2 b[mm*4],d[3];
int get(int x){
    if(!fa[x])return x;
    return fa[x]=get(fa[x]);
}
void merge(rec2 &x,rec2 &y,rec2 &z){
    int i=1,j=1,k=0;d[0].ans=0;
    while((i<=x.size)||(j<=y.size)){
        if((j>y.size)||((i<=x.size)&&(x.a[i].cint fu=get(x.a[i].u),fv=get(x.a[i].v);
            if(fu!=fv){
                fa[fu]=fv;d[0].ans+=x.a[i].c;
                d[0].a[++k]=x.a[i];
            }
            i++;
        }else{
            int fu=get(y.a[j].u),fv=get(y.a[j].v);
            if(fu!=fv){
                fa[fu]=fv;d[0].ans+=y.a[j].c;
                d[0].a[++k]=y.a[j];
            }
            j++;
        }
    }
    d[0].size=k;
    z.ans=d[0].ans;z.size=d[0].size;
    fo(i,1,k)fa[d[0].a[i].u]=fa[d[0].a[i].v]=0,z.a[i]=d[0].a[i];
}
void build(int now,int l,int r){
    if(l==r){
        b[now].a[1]=a[l];
        b[now].size=1;
        b[now].ans=a[l].c;
        return;
    }
    int mid=(l+r)>>1,lson=now*2,rson=now*2+1;
    build(lson,l,mid);
    build(rson,mid+1,r);
    merge(b[lson],b[rson],b[now]);
}
void qury(int now,int l,int r,int u,int v){
    int mid=(l+r)>>1;
    if((l==u)&&(r==v)){
        d[++cnt].size=b[now].size;d[cnt].ans=b[now].ans;
        fo(i,1,d[cnt].size)d[cnt].a[i]=b[now].a[i];
        if(cnt==2){
            merge(d[1],d[2],d[1]);
            cnt=1;
        }
        return;
    }
    if(v<=mid)qury(now*2,l,mid,u,v);
    else if(mid2+1,mid+1,r,u,v);
    else{
        qury(now*2,l,mid,u,mid);
        qury(now*2+1,mid+1,r,mid+1,v);
    }
}
int main(){
    //freopen("highway.in","r",stdin);
    //freopen("highway.out","w",stdout);
    freopen("d.in","r",stdin);
    freopen("d.out","w",stdout);
    scanf("%d%d%d",&n,&m,&q);
    fo(i,1,m)scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].c);
    build(1,1,m);int l,r;
    fo(cas,1,q){
        scanf("%d%d",&l,&r);
        if(cas==469){
            int bb;
            bb++;
        }
        qury(1,1,m,l,r);
        printf("%d
",d[1].ans);cnt=0;
    }
    return 0;
}