CF515E Drazil and Park【思维+线段树】

题意

有一只猴子，他生活在一个环形的公园里。有 $n$ 棵树围绕着公园。第$i$棵树和第$i+1$棵树之间的距离是 $d_i$ ，而第$n$棵树和第一棵树之间的距离是 $d_n$ 。第$i$棵树的高度是 $h_i$ 。

这只猴子每天要进行晨跑。晨跑的步骤如下：

· 他先选择两棵树；

· 然后爬上第一棵树；

· 再从第一棵树上下来，接着围绕着公园跑（有两个可能的方向）到第二棵树，然后爬上第二棵树；

· 最后从第二棵树上下来。

但是有一些小孩会在连续的一些树上玩耍。所以猴子不能经过这些树。

比如现在猴子选择的第$x$棵和第$y$棵树，那么该早晨他消耗的能量是 $2(hx+hy)+dist(x,y)$ 。由于某一条路径是被小孩子占据的，所以他只能跑另外一条，因此 $dist(x,y)$ 是确定的。

现在给出第i天，孩子们会在第 $a_i$ 棵树和 $b_i$ 棵树之间玩耍。具体的，如果 $ai\le bi$ ，那么孩子玩耍的区间就是 $[ai,bi]$ ，否则孩子玩耍的区间就是 $[ai,n]\bigcup [1,bi]$ 。

请帮助这只猴子找出两棵树，让他晨跑的时候他能够消耗最大的能量。

时间限制

2.00s

内存限制

500.00MB

思路

看到环形结构，第一个想法就是断环成链。
之后我们令，$su{m}_i$表示从起点到$i$的距离，也就是$d$数组的前缀和，那么$2(hx+hy)+dist(x,y)=2hx+2hy+su{m}_y-su{m}_x=su{m}_y+2hy-(su{m}_x-2hx)$，那么如果我们可以求出$su{m}_i+2hi$的最大值和$su{m}_i-2hi$的最小值，就可以得到每次询问的答案。
可以使用线段树或者ST表维护这两个最值对应的下标，对于询问$(l,r)$，如果两个最值的下标相同，为$p$，那么由于要求两颗不同的树，于是需要在$(l,p-1)$与$(p+1,r)$中再查询一下，具体看代码啦，很简单滴。

代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 100005;

int d[N * 2], h[N * 2];
LL s1[N * 2], s2[N * 2];

struct Tree
{
    int l, r;
    int mxp, mip;
}t[N << 4];

int calcMx(int i, int j)
{
    return s1[i] > s1[j] ? i : j;
}

int calcMi(int i, int j)
{
    return s2[i] < s2[j] ? i : j;
}

void push_up(int i)
{
    t[i].mip = calcMi(t[i << 1].mip, t[i << 1 | 1].mip);
    t[i].mxp = calcMx(t[i << 1].mxp, t[i << 1 | 1].mxp);
}

void build(int i, int l, int r)
{
    t[i].l = l, t[i].r = r;
    if (l == r)
    {
        t[i].mxp = t[i].mip = l;
        return;
    }
    int mid = (l + r) >> 1;
    build(i << 1, l, mid);
    build(i << 1 | 1, mid + 1, r);
    push_up(i);
}

int queryMi(int i, int l, int r)
{
    if (l <= t[i].l && t[i].r <= r) return t[i].mip;
    int mid = (t[i].l + t[i].r) >> 1;

    if (l > mid) return queryMi(i << 1 | 1, l, r);
    else if(r <= mid) return queryMi(i << 1, l, r);
    else return calcMi(queryMi(i << 1, l, r), queryMi(i << 1 | 1, l, r));
}

int queryMx(int i, int l, int r)
{
    if (l <= t[i].l && t[i].r <= r) return t[i].mxp;
    int mid = (t[i].l + t[i].r) >> 1;

    if (l > mid) return queryMx(i << 1 | 1, l, r);
    else if(r <= mid) return queryMx(i << 1, l, r);
    else return calcMx(queryMx(i << 1, l, r), queryMx(i << 1 | 1, l, r));
}

int getMx(int l, int r)
{
    if (l > r) return 0;
    return queryMx(1, l, r);
}

int getMi(int l, int r)
{
    if (l > r) return 0;
    return queryMi(1, l, r);
}

LL solve(int l, int r)
{
    int mxp = getMx(l, r), mip = getMi(l, r);
    if (mip != mxp) return s1[mxp] - s2[mip];
    int mxpp = calcMx(getMx(l, mxp - 1), getMx(mxp + 1, r));
    int mipp = calcMi(getMi(l, mxp - 1), getMi(mxp + 1, r));
    return max(s1[mxp] - s2[mipp], s1[mxpp] - s2[mip]);
}

int main()
{
    #ifdef ZYCMH
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &d[i % n + 1]), d[i % n + 1 + n] = d[i % n + 1];
    for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]), h[i + n] = h[i];

    LL sum = 0;
    s1[0] = -1e18;
    s2[0] = 1e18;
    for (int i = 1; i <= n * 2; i ++ )
    {
        sum += d[i];
        s1[i] = sum + 2 * h[i];
        s2[i] = sum - 2 * h[i];
    }

    build(1, 1, 2 * n);

    for (int i = 1; i <= m; i ++ )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        if (l <= r) printf("%lld\n", solve(r + 1, l - 1 + n));
        else printf("%lld\n", solve(r + 1, l - 1));
    }

    return 0;
}

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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131