HDU5861 Road

2016多校, HDU, 扫描线, 树状数组, 线段树

　　2016 Multi-University Training Contest 10

　　题意：一条大道被n个村庄分成n－1条路，每条道路开放一天的花费为c[i]，道路初始为关闭状态，可以任意选择开放或关闭某条道路，道路被关闭后不能再次开放。现在有m天的运输任务，每天从村庄l[i]运输货物到村庄r[i]，要求运输路程中的所有道路均为开放状态。求满足运输任务前提下的最小花费。 - 原题链接

　　正反做两次线段树区间覆盖，得到第i条道路最早和最晚的占用时间，树状数组维护每天的总花费。
　　小trick，输入数据不保证l[i]>r[i]。赛时一次AC，happy✌️ 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define kl (k<<1)
#define kr ((k<<1)+1)
#define mid ((l+r)>>1)
#define lowbit(x) ((x)&-(x))
using namespace std;
const int maxn=2*1e5 + 10, INF=0x7f7f7f7f;
typedef long long lint;
int n, m, a[maxn], ql[maxn], qr[maxn];
lint s[maxn];
vector<int> vct[maxn];
struct node
{
    int x[2];
    node(int l=0, int r=0, int c=0){ x[0]=l, x[1]=r; }
}tr[maxn<<2];
void Build(int k=1, int l=1, int r=n)
{
    tr[k].x[0]=tr[k].x[1]=-INF;
    if(l==r)    return ;
    Build(kl, l, mid);
    Build(kr, mid+1, r);
    return ;
}
void Push_down(int k, int f)
{
    tr[kl].x[f]=max(tr[kl].x[f], tr[k].x[f]);
    tr[kr].x[f]=max(tr[kr].x[f], tr[k].x[f]);
    return ;
}
void Insert(int ll, int rr, int f, int val, int k=1, int l=1, int r=n)
{
    if(rr <l||r< ll)    return ;
    if(ll<=l&&r<=rr)
    {
        tr[k].x[f]=val;
        return ;
    }
    Push_down(k, f);
    Insert(ll, rr, f, val, kl, l, mid);
    Insert(ll, rr, f, val, kr, mid+1, r);
    return ;
}
void Add(int x, int val)
{
    for(int i=x; i<=m; i+=lowbit(i))    s[i]+=val;
    return ;
}
lint Get(int x, lint sum=0)
{
    for(int i=x; i; i-=lowbit(i))    sum+=s[i];
    return sum;
}
void Query(int x, int &ll, int &rr, int k=1, int l=1, int r=n)
{
    if(l==r)
    {
        ll=tr[k].x[0], rr=tr[k].x[1];
        return ;
    }
    Push_down(k, 0);
    Push_down(k, 1);
    if(x<=mid)    Query(x, ll, rr, kl, l, mid);
    else Query(x, ll, rr, kr, mid+1, r);
    return ;
}
int main()
{
    while(scanf("%d%d", &n, &m)!=EOF)
    {
        for(int i=1; i<n; i++)    scanf("%d", &a[i]);
        for(int i=1; i<=m; i++)
        {
            scanf("%d%d", &ql[i], &qr[i]);
            if(ql[i]>qr[i])    swap(ql[i], qr[i]);
            --qr[i];
        }
        Build();
        for(int i=1; i<=m; i++)    Insert(ql[i], qr[i], 0, i);
        for(int i=m; i>=1; i--)    Insert(ql[i], qr[i], 1, m-i+1);
        for(int i=1, ll, rr; i<n; i++)
        {
            Query(i, rr, ll);
            if(rr==-INF)    continue;
            Add(m-ll+1, a[i]);
            Add(rr+1, -a[i]);
        }
        for(int i=1; i<=m; i++)    printf("%lld\n", Get(i));
        memset(s, 0, sizeof s);
    }
    return 0;
}