CF102428J Jumping Grasshoper 题解

发表于 分类于 本文字数： 1063 阅读时长 ≈ 3 分钟

true
Jumping Grasshoper
2019-2020 ACM-ICPC Latin American Regional Programming Contest
none
none
  • CF Gym 102428 J

题目大意是，我们需要维护一个数列，支持对其进行修改和查询。
修改就是正常的单点修改，查询的话就有点不一样。
每一次查询的时候，我们会指定一个开始的位置和开始的方向。每一轮，我们向指定的方向找到第一个比当前位置高的地方，跳到那里，并将方向变为当前方向相反的那一个方向。
如果当前方向没有找到能够跳到的地方，那就停下。我们需要找到最后会停在哪里，并输出之。
题目保证每一时刻都没有两个高度是相同的。

我们设当前的这个位置为 $p$。

首先我们可以猜测，这个停下的位置一定会是起点左右的某一个最大值。
因为我们每一次查询的过程一定是在反复在起点的两侧跳跃。

为了分析方便，我们把这两个值的下标都取出来，分别称作 $maxl$ 和 $maxr$。

然后我们开始分类讨论：

首先要考虑到的一种情况就是当前的位置已经是哪里都不能去了，即 $a_{maxl} < a_p$ 且 $a_{maxr} < a_p$。
那就直接输出 $p$ 就好了。

然后是两种次级情况。

一是左边没有比当前高的，但是右边有；二是右边没有比当前高的，但是左边有。

这两种情况的决策与开始时的方向有关，这里只拿第一种情况做例子。

如果开始时的方向是向左，那我们跳一次之后方向就会变成向右。
我们设这个位置是 $minl$。
因为有 $a_p > a_{maxr}$，所以有 $a_{minl} > a_{maxr}$，这就意味着我们需要在 $minl$ 停下。

如果开始时的方向是向右，因为右边已经没有比当前高的地方了，直接停下就可以了。

另一种情况类似。

然后就是最后一种情况了，两者都比当前要高。

因为我们一直跳的话迟早会落在 $maxl$ 或 $maxr$ 两者之一上面，只需要判断两者大小关系即可。
因为我们已经确定了这两个位置是跳了一段时间之后再到达的，那么落在 $maxl$ 位置上的时候肯定是向右，因为其肯定是从右面向左跳过去的；落在 $maxr$ 的位置同理。

那么如果 $a_{maxl} < a_{maxr}$，那么我们最终会从 $maxl$ 出发向右跳到 $p$ 右面第一个大于 $a_{maxl}$ 的位置，另一种情况同理。

回头看一眼我们的讨论，可以发现已经覆盖了所有的情况了。

那么我们需要找到一种算法，可以支持单点修改、区间查询最大值和区间查询大于（等于）某一个数的最靠左（或右）的位置。

我们可以选择线段树和线段树上二分来解决。

代码如下：

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 200010;
int n, m;
int a[N];
struct SegTree
{
    int l, r;
    int maxn;
};
SegTree tr[N << 3];
void pushup(int p)
{
    tr[p].maxn = max(tr[p << 1].maxn, tr[p << 1 | 1].maxn);
}
void build(int p, int l, int r)
{
    tr[p].l = l, tr[p].r = r;
    tr[p].maxn = 0;
    if(l == r)
    {
        tr[p].maxn = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    pushup(p);
}
void segchg(int p, int pos, int k)
{
    if(tr[p].l == tr[p].r)
    {
        tr[p].maxn = k;
        return;
    }
    int mid = (tr[p].l + tr[p].r) >> 1;
    if(pos <= mid)segchg(p << 1, pos, k);
    else if(pos > mid)segchg(p << 1 | 1, pos, k);
    pushup(p);
}
int segmax(int p, int l, int r)
{
    if(tr[p].l >= l && tr[p].r <= r)return tr[p].maxn;
    int mid = (tr[p].l + tr[p].r) >> 1;
    int res = 0;
    if(l <= mid)res = max(res, segmax(p << 1, l, r));
    if(r > mid)res = max(res, segmax(p << 1 | 1, l, r));
    return res;
}
int getposl(int p, int l, int r, int k)
{
    if(tr[p].maxn <= k)return n + 1;
    if(tr[p].l == tr[p].r)return tr[p].l;
    if(tr[p].l >= l && tr[p].r <= r)
    {
        if(tr[p << 1].maxn <= k)return getposl(p << 1 | 1, l, r, k);
        else return getposl(p << 1, l, r, k);
    }
    int mid = (tr[p].l + tr[p].r) >> 1;
    int res = n + 1;
    if(l <= mid)res = min(res, getposl(p << 1, l, r, k));
    if(r > mid)res = min(res, getposl(p << 1 | 1, l, r, k));
    return res;
}
int getposr(int p, int l, int r, int k)
{
    if(tr[p].maxn <= k)return 0;
    if(tr[p].l == tr[p].r)return tr[p].l;
    if(tr[p].l >= l && tr[p].r <= r)
    {
        if(tr[p << 1 | 1].maxn <= k)return getposr(p << 1, l, r, k);
        else return getposr(p << 1 | 1, l, r, k);
    }
    int mid = (tr[p].l + tr[p].r) >> 1;
    int res = 0;
    if(r > mid)res = max(res, getposr(p << 1 | 1, l, r, k));
    if(l <= mid)res = max(res, getposr(p << 1, l, r, k));
    return res;
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    build(1, 1, n);
    for(int i = 1; i <= m; i++)
    {
        string s;
        int p, k;
        cin >> s;
        if(s == "U")
        {
            scanf("%d%d", &p, &k);
            segchg(1, p, k);
            a[p] = k;
        }
        else
        {
            bool flag = (s == "R");
            scanf("%d", &p);
            int maxr = segmax(1, p + 1, n);
            int maxl = segmax(1, 1, p - 1);
            if(maxl < a[p] && maxr < a[p])
            {
                printf("%d\n", p);
            }
            else if(maxl > a[p] && maxr < a[p])
            {
                if(flag)printf("%d\n", p);
                else printf("%d\n", getposr(1, 1, p - 1, a[p]));
            }
            else if(maxr > a[p] && maxl < a[p])
            {
                if(!flag)printf("%d\n", p);
                else printf("%d\n", getposl(1, p + 1, n, a[p]));
            }
            else
            {
                if(maxl < maxr)printf("%d\n", getposl(1, p + 1, n, maxl));
                else printf("%d\n", getposr(1, 1, p - 1, maxr));
            }
        }
    }
    return 0;
}