UVA1618-Weak Key（RMQ）

Problem UVA1618-Weak Key

Accept: 103  Submit: 588
Time Limit: 3000 mSec

Problem Description

Cheolsoo is a cryptographer in ICPC(International Cryptographic Program Company). Recently, Cheolsoo developed a cryptographic algorithm called ACM(Advanced Cryptographic Method). ACM uses a key to encrypt a message. The encrypted message is called a cipher text. In ACM, to decrypt a cipher text, the same key used in the encryption should be applied. That is, the encryption key and the decryption key are the same. So, the sender and receiver should agree on a key before they communicate securely using ACM. Soon after Cheolsoo finished the design of ACM, he asked its analysis on security to Younghee who is a cryptanalyst in ICPC.
Younghee has an interest in breaking cryptosystems. Actually, she developed many attacking methods for well-known cryptographic algorithms. Some cryptographic algorithms have weak keys. When a message is encrypted with a weak key, the message can be recovered easily without the key from the cipher text. So, weak key should not be used when encrypting a message. After many trials, she found the characteristic of weak keys in ACM. ACM uses a sequence of mutually distinct positive integers (N1,N2,...,Nk) as a key. Younghee found that weak keys in ACM have the following two special patterns: There are four integers Np,Nq,Nr,Ns(1 ≤ p < q < r < s ≤ k) in the key such that (1) Nq > Ns > Np > Nr or Nq < Ns < Np < Nr
For example, the key (10, 30, 60, 40, 20, 50) has the pattern in (1); ( , 30, 60, , 20, 50). So, the key is a weak key in ACM. But, the key (30, 40, 10, 20, 80, 50, 60, 70) is not weak because it does not have any pattern in the above.
Now, Younghee wants to find an efficient method to determine, for a given key, whether it is a weak key or not. Write a program that can help Younghee.

Input

The input consists of T test cases. The number of test cases T is given in the first line of the input file. Each test case starts with a line containing an integer k, the length of a sequence repressenting a key, 4 ≤ k ≤ 5,000. In the next line, k mutually distinct positive integers are given. There is a single space between the integers, and the integers are between 1 and 100,000, both inclusive.

 Output

Print exactly one line for each test case. Print ‘YES’ if the sequence is a weak key. Otherwise, print ‘NO’.

 

 Sample Input

3
6
10 30 60 40 20 50
8
30 40 10 20 80 50 60 70
4
1 2 20 9

 

Sample Output

YES
NO
NO

题解：一开始没有太好的思路，但是很快想到那个4个数和为0的题目，那个题就是再枚举的基础上不断优化，有了枚举优化的思路这个题就好想了。这个题很明显只用思考一种关系，另一种关系取相反数，调用同一个函数就好。四个数，画个折线图，大致是增减增的形式，看看数据范围，应该是O(n^2)的算法，那就枚举两个数，枚举p，q，此时num[s]应该在num[p]+1到num[q]-1之间，并且s越大越好，定好了s，r就是序列从q+1到s-1这个范围内的最小值，如果这个最小值符合题目要求的大小关系，那么就找到了答案。考虑到时间复杂度，这s和r的查找都必须是O(1)的，静态查询区间最值,RMQ是很自然的想法，r是很好办的，不就是查询原序列的区间最小值么，关键是s怎么找，其实也很简单，看看刚才关于s的描述，就是序列在按照元素值大小排序后，将各个元素对应的原始位置列出来形成的新的序列进行区间最值的查询，这样就实现了r和s的常数时间内的查询。具体实现时有一些技巧和细节和题解不完全相同，详见代码。

#include <bits/stdc++.h>

using namespace std;

const int maxn = 5000 + 10;

int Max[maxn][20], Min[maxn][20];
int num[maxn], pos[maxn], n;
int lg2[maxn];

void Max_ST(int *num) {
    lg2[0] = -1;
    for (int i = 1; i <= n; i++) {
        lg2[i] = lg2[i - 1] + (i&(i - 1) ? 0 : 1);
    }

    for (int i = 1; i <= n; i++) {
        Max[i][0] = num[i];
    }

    for (int j = 1; j <= lg2[n]; j++) {
        for (int i = 0; lg2[n - i] >= j; i++) {
            Max[i][j] = max(Max[i][j - 1], Max[i + (1 << (j - 1))][j - 1]);
        }
    }
}

void Min_ST(int *num) {
    lg2[0] = -1;
    for (int i = 1; i <= n; i++) {
        lg2[i] = lg2[i - 1] + (i&(i - 1) ? 0 : 1);
    }

    for (int i = 1; i <= n; i++) {
        Min[i][0] = num[i];
    }

    for (int j = 1; j <= lg2[n]; j++) {
        for (int i = 0; lg2[n - i] >= j; i++) {
            Min[i][j] = min(Min[i][j - 1], Min[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int RMQ_Max(int l, int r) {
    int k = lg2[r - l + 1];
    return max(Max[l][k], Max[r - (1 << k) + 1][k]);
}

int RMQ_Min(int l, int r) {
    int k = lg2[r - l + 1];
    return min(Min[l][k], Min[r - (1 << k) + 1][k]);
}

vector<int> Rank;

bool solve() {
    Max_ST(pos), Min_ST(num);
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (num[i] < num[j]) {
                int l = num[i] + 1, r = num[j] - 1;
                if (l > r) continue;
                r = RMQ_Max(l, r) - 1;
                l = j + 1;
                if (l > r) continue;
                int tt = RMQ_Min(l, r);
                if (tt < num[i]) {
                    return true;
                }
            }
        }
    }
    return false;
}

int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int iCase;
    scanf("%d", &iCase);
    while (iCase--) {
        scanf("%d", &n);
        Rank.clear();
        for (int i = 1; i <= n; i++) {
            scanf("%d", &num[i]);
            Rank.push_back(num[i]);
        }

        sort(Rank.begin(), Rank.end());
        Rank.erase(unique(Rank.begin(), Rank.end()), Rank.end());
        for (int i = 1; i <= n; i++) {
            num[i] = lower_bound(Rank.begin(), Rank.end(), num[i]) - Rank.begin() + 1;
            pos[num[i]] = i;
        }

        bool ok = solve();
        if (ok) {
            printf("YES
");
            continue;
        }

        for (int i = 1; i <= n; i++) {
            num[i] = n + 1 - num[i];
            pos[num[i]] = i;
        }

        ok = solve();
        if (ok) printf("YES
");
        else printf("NO
");
    }
    return 0;
}