HDU 5861 Road （线段树）

Road

题目链接：

http://acm.split.hdu.edu.cn/showproblem.php?pid=5861

Description

There are n villages along a high way, and divided the high way into n-1 segments. Each segment would charge a certain amount of money for being open for one day, and you can open or close an arbitrary segment in an arbitrary day, but you can open or close the segment for just one time, because the workers would be angry if you told them to work multiple period. We know the transport plan in the next m days, each day there is one cargo need to transport from village ai to village bi, and you need to guarantee that the segments between ai and bi are open in the i-th day. Your boss wants to minimize the total cost of the next m days, and you need to tell him the charge for each day. (At the beginning, all the segments are closed.)

Input

Multiple test case. For each test case, begins with two integers n, m(1<=n,m<=200000), next line contains n-1 integers. The i-th integer wi(1<=wi<=1000) indicates the charge for the segment between village i and village i+1 being open for one day. Next m lines, each line contains two integers ai,bi(1≤ai,bi<=n,ai!=bi).

Output

For each test case, output m lines, each line contains the charge for the i-th day.

Sample Input

4 3 1 2 3 1 3 3 4 2 4

Sample Output

3 5 5

Source

2016 Multi-University Training Contest 10
##题意：水平线上n个村子间有 n-1 条路. 每条路开放一天的价格为 Cost_i. 有 m 天的操作，每天需要用到村子 Ai~Bi 间的道路. 每条路只能开放或关闭一次. (不能重复开关) 求每天的最小花费.
##题解：用了两次线段树维护，写得很丑，还不如写两次线段树. 第一次线段树：维护每条路第一次和最后一次被用到的天数. 以下代码维护了 mi:第一天，ma:最后一天，has:是否已经被用过. mi和ma分别是子节点的最小值和最大值，关键是 has 的维护. (一开始没有写has, WA了) has表示当前区间的结点是否都已经被用过.(即有mi值). 如果has=1那么就可以直接用lazy维护区间中所有结点的最大值. 若has=0意味着某个子节点还没有被用过, 若当前区间被lazy维护而没有更新到点，那么这个子节点的最小值就可能被改变. 这个地方关于维护的对象和lazy的处理做的不是很好，不过幸好过了. 晚点再改一下代码. 第二次线段树：维护每天用了多少钱. 根据以上结果维护，对于每条路(被用到过的)区间更新第一次到最后一次这些天用的钱.
##代码： ``` cpp #include #include #include #include #include #include #include #include #include #include #include #define LL long long #define eps 1e-8 #define maxn 201000 #define mod 100000007 #define inf 0x3f3f3f3f #define mid(a,b) ((a+b)>>1) #define IN freopen("in.txt","r",stdin); using namespace std;

int n,m;
LL cost[maxn];
struct Tree
{
int left,right;
LL lazy,mi,ma,sum;
bool has;
}tree[maxn<<2];

bool flag;

void pushup(int i) {
tree[i].mi = min(tree[i<<1].mi, tree[i<<1|1].mi);
tree[i].ma = max(tree[i<<1].ma, tree[i<<1|1].ma);
tree[i].has = tree[i<<1].has && tree[i<<1|1].has;
if(flag) tree[i].sum = (tree[i<<1].sum + tree[i<<1|1].sum);
}

/递归建树/
void build(int i,int left,int right)
{
tree[i].left=left;
tree[i].right=right;
tree[i].lazy=0;

if(left==right){
    tree[i].mi=inf;
    tree[i].ma=-inf;
    tree[i].has = 0;
    tree[i].sum = 0;
    return ;
}

int mid=mid(left,right);

build(i<<1,left,mid);
build(i<<1|1,mid+1,right);

pushup(i);

}

/区间修改，标记下传：每当访问到当前结点的子节点时，下传标记/
void pushdown(int i)
{
if(tree[i].lazy){
if(flag) {
tree[i<<1].lazy+=tree[i].lazy;
tree[i<<1|1].lazy+=tree[i].lazy;
tree[i<<1].sum+=(tree[i<<1].right-tree[i<<1].left+1)tree[i].lazy;
tree[i<<1|1].sum+=(tree[i<<1|1].right-tree[i<<1|1].left+1)tree[i].lazy;
tree[i].lazy=0; /下传后清零/
} else {
tree[i<<1].lazy=tree[i].lazy;
tree[i<<1|1].lazy=tree[i].lazy;
//tree[i<<1].mi = min(tree[i].lazy, tree[i<<1].mi);
//tree[i<<1|1].mi = min(tree[i].lazy, tree[i<<1|1].mi);
tree[i<<1].ma = max(tree[i].lazy, tree[i<<1].ma);
tree[i<<1|1].ma = max(tree[i].lazy, tree[i<<1|1].ma);
tree[i].lazy=0; /下传后清零/
}
}
}

/区间修改，d为改变量/
void update(int i,int left,int right,LL d)
{
if(tree[i].leftleft&&tree[i].rightright)
{
tree[i].mi = min(d, tree[i].mi);
tree[i].ma = max(d, tree[i].ma);
if(flag) {
tree[i].sum += (right-left+1) * d;
tree[i].lazy += d;
return;
} else {
if(tree[i].has) {
tree[i].lazy = d;
return;
}
if(tree[i].left==tree[i].right) {
if(!tree[i].has) tree[i].mi = tree[i].ma = d;
tree[i].has = 1;
return ;
}
}
}

pushdown(i);

int mid=mid(tree[i].left,tree[i].right);

if(right<=mid) update(i<<1,left,right,d);
else if(left>mid) update(i<<1|1,left,right,d);
else
{
    update(i<<1,left,mid,d);
    update(i<<1|1,mid+1,right,d);
}

pushup(i);

}

/区间结果查询/
typedef pair<LL,LL> pii;
pii query(int i,int left,int right)
{
if(tree[i].leftleft&&tree[i].rightright)
return make_pair(tree[i].mi,tree[i].ma);

pushdown(i);

int mid=mid(tree[i].left,tree[i].right);

if(right<=mid) return query(i<<1,left,right);
else if(left>mid) return query(i<<1|1,left,right);
//else return 0;

}

LL query_sum(int i,int left,int right)
{
if(tree[i].leftleft&&tree[i].rightright)
return tree[i].sum;

pushdown(i);

int mid=mid(tree[i].left,tree[i].right);

if(right<=mid) return query_sum(i<<1,left,right);
else if(left>mid) return query_sum(i<<1|1,left,right);
else return query_sum(i<<1,left,mid)+query_sum(i<<1|1,mid+1,right);

}

int starts[maxn], endss[maxn];

int main(int argc, char const *argv[])
{
//IN;

//int t; cin >> t;
while(scanf("%d %d", &n, &m) != EOF)
{
    flag = 0;
    for(int i=1; i<=n-1; i++)
        scanf("%lld", &cost[i]);
    build(1, 1, n-1);
    for(int i=1; i<=m; i++) {
        int x,y; scanf("%d %d", &x,&y);
        if(x > y) swap(x, y);
        update(1, x, y-1, i);
    }

    for(int i=1; i<=n-1; i++) {
        pii tmp = query(1, i, i);
        starts[i] = tmp.first;
        endss[i] = tmp.second;
    }

    flag = 1;
    build(1, 1, m);
    for(int i=1; i<=n-1; i++) {
        if(starts[i] == inf) continue;
        update(1, starts[i], endss[i], cost[i]);
    }

    for(int i=1; i<=m; i++) {
        printf("%lld
", query_sum(1,i,i));
    }
}

return 0;

}