UVA1618 弱键 Weak Key 题解

巨佬们都用ST表写，而我只想到暴力……

题目要求确定四个数的大小关系，但数据范围最多支持确定两个数的大小关系，所以只能两两确认，先确认 $q,s$ ，再确认 $s,p$ ，最后确认 $p,r$ ，找到符合要求的四个数。

但是上面最初的想法用代码不好实现，而题目要求的 $Nq>Ns>Np>Nr$ 或 $Nq<Ns<Np<Nr$ 中，$q<s,s>p,p<r$ ，所以枚举 $s,p$ ，再算出一组 $q,r$ ，最后判断是否合法。

这样就需要一个预处理。以 $Nq>Ns>Np>Nr$ 为例，如果按照最初的思路去想，会发现需要一个二维数组 $a[i][j]$ 保存所有小于 $N[i]$ 且符合下标关系的 $N[j]$ 。这里也类似，记 $a[i]$ 保存所有的满足 $i<j,N[i]>N[j]$ 的 $j$ ，$b[i]$ 保存所有的满足 $i>j,N[i]<N[j]$ 的$j$ ，则可以这么处理 $a,b$ ：

std::vector<int> a[MAXK + 3], b[MAXK + 3];
for (int p = 1; p < k; p++)
        for (int r = p + 1; r <= k; r++)
            if (N[p] > N[r])
                a[p].push_back(r);
for (int s = k; s >= 2; s--)
        for (int q = 1; q < s; q++)//这么枚举q更方便下面的查找
            if (N[q] > N[s])
                b[s].push_back(q);

然后枚举 $s,p$ ，这时 $q$ 的范围就在 $b[s]$ 中，$r$ 的范围就在 $a[p]$ 中。因为 $q$ 是次小的，所以我们就要在 $b[s]$ 中，找到 $>p$ 且最小的 $q$ （这样更可能存在解），用二分查找就可以了，前提是 $b[s]$ 必须是有序的，这很容易做到。然后再根据 $q$ 查找出 $r$ ，验证是否符合要求就行。注意：如果查找不到，就要设为一个特殊值与其他下标区分

求 $Nq<Ns<Np<Nr$ 也是这样，只不过反转一下 $N$ 数组再做就行了。

代码：

#include <cstdio>
#include <algorithm>
#include <vector>
#define MAXK 5000
std::vector<int> a[MAXK + 3], b[MAXK + 3];
int k, N[MAXK + 3], T;
bool judge(bool reverse) {//reverse表示是否要反转
    if (reverse)
        std::reverse(N + 1, N + 1 + k);
    for (int i = 1; i <= k; i++)
        a[i].clear(), b[i].clear();//因为做两遍，所以一定要清空
    //预处理a
    for (int p = 1; p < k; p++)
        for (int r = p + 1; r <= k; r++)
            if (N[p] > N[r])
                a[p].push_back(r);
    //预处理b
    for (int s = k; s >= 2; s--)
        for (int q = 1; q < s; q++)
            if (N[q] > N[s])
                b[s].push_back(q);
    //枚举s,p
    for (int s = k; s >= 2; s--)
        for (int p = s - 1; p >= 1; p--)
            if (N[s] > N[p]) {
                int pos = std::upper_bound(b[s].begin(), b[s].end(), p) - b[s].begin();
                int q = (pos == b[s].size() ? 0 : b[s][pos]);//这里设0为特殊值
                pos = std::upper_bound(a[p].begin(), a[p].end(), q) - a[p].begin();
                int r = (pos == a[p].size() ? 0 : a[p][pos]);
                if (N[q] > N[s] && N[s] > N[p] && N[p] > N[r] && p < q && q < r && r < s)//其实这里的判断可以没有这么多，但是写成这样易于理解
                    return 1;
            }
    return 0;
}
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &k);
        for (int i = 1; i <= k; i++)
            scanf("%d", &N[i]);
        if (judge(0) || judge(1))
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}
/*
3
6
10 30 60 40 20 50
8
30 40 10 20 80 50 60 70
4
1 2 20 9
*/