HDOJ 5861 Road

这个题的题意理解真是废了劲了

题意：有n个城市，编号1~n，有n-1条边，连成了一条从1到n的顺序的链

每条边都有花费cost【i】

每条边只能开关一次！！！

门在打开时每天都有一个花费。这时候需要运输一些东西，告诉你开始和终止的城市，你需要保证有路径可以到达。最后输出每天的花费即可。

要理解题意，就要从样例看起

4 3
1 2 3
1 3
3 4
2 4

那是因为，下面还有一组2到4

因为每条边只能开关一次，所以2到3这条边在3到4查询的时候是不能关闭的

怎么处理呢？要求所需要的钱最少

那么就是：每条边都开得尽量晚（就是求每条边最晚的开放时间）

每条边都关得尽量早

所以，我们用线段树来维护每个节点的最晚开放时间和最早关闭时间（lazy标记处理）

这样的话，离线处理好每个查询，update插入的是起始和终止时间

然后说说代码的细节

Update(1,n,1,a,b-1,i);

        ans[early[rt]]+=cost[l];
        ans[late[rt]+1]-=cost[l];

根据统计好的最晚开放时间和最早关闭时间来搞的

#include<bits/stdc++.h>
using namespace std;

#define maxn 200050
#define INF 0x3f3f3f3f
#define LL __int64
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

LL num[maxn],ans[maxn];
int cost[maxn];
int early[maxn<<2],late[maxn<<2],mark[maxn<<2];

void build(int l,int r,int rt){
    early[rt]=INF;
    late[rt]=mark[rt]=0;
    if (l==r) return;
    int m=(l+r)>>1;
    build(lson);
    build(rson);
    return;
}

void PushDown(int rt){
    if (mark[rt]){
        early[rt<<1]=min(early[rt<<1],early[rt]);
        early[rt<<1|1]=min(early[rt<<1|1],early[rt]);
        late[rt<<1]=max(late[rt<<1],late[rt]);
        late[rt<<1|1]=max(late[rt<<1|1],late[rt]);
        mark[rt<<1]=mark[rt<<1|1]=1;
        mark[rt]=0;
    }
    return;
}

void Update(int l,int r,int rt,int L,int R,int x){
    if (L<=l&&R>=r){
        mark[rt]=1;
        early[rt]=min(early[rt],x);
        late[rt]=max(late[rt],x);
        return;
    }
    PushDown(rt);
    int m=(l+r)>>1;
    if (L<=m) Update(lson,L,R,x);
    if (R>m) Update(rson,L,R,x);
    return;
}

void query(int l,int r,int rt){
    if (l==r){
        if (early[rt]==INF||late[rt]==0) return;
        ans[early[rt]]+=cost[l];
        ans[late[rt]+1]-=cost[l];
        return;
    }
    PushDown(rt);
    int m=(l+r)>>1;
    query(lson);
    query(rson);
}

int main(){
    //freopen("input.txt","r",stdin);
    int n,m,a,b;
    while(scanf("%d%d",&n,&m)!=EOF){
        for(int i=1;i<n;i++) scanf("%d",&cost[i]);
        build(1,n,1);
        memset(ans,0,sizeof(ans));
        for(int i=1;i<=m;i++){
            scanf("%d%d",&a,&b);
            if (a>b) swap(a,b);
            Update(1,n,1,a,b-1,i);
        }
        LL sum=0;
        query(1,n,1);
        for(int i=1;i<=m;i++){
            sum+=ans[i];
            printf("%I64d\n",sum);
        }
    }
    return 0;
}