BZOJ【Cerc2012】Non-boring sequences

发表于 | 阅读数

是否存在某个区间不存在存在唯一数。

先预处理某个数出现一次的区间，考虑分治$[l,r]$，首先找到$[l,r]$出现一次的数某个数$p$，$[l,p-1],[p+1,r]$继续寻找，显然如果某个数在最左边或最右边，就会产生$n^2$的假算法。考虑从$l,r$两端搜索$p$，最差情况在中间，那么复杂度就是$O(n\log n)$

代码 
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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0', c = getchar();
    return x * f;
}
int a[N], L[N], R[N];
bool solve(int l, int r)
{
    if (l >= r)
        return 1;
    int x = l, y = r;
    while (x <= y)
    {
        if (L[x] < l && R[x] > r)
            return (solve(l, x - 1) && solve(x + 1, r));
        else if (L[y] < l && R[y] > r)
            return (solve(l, y - 1) && solve(y + 1, r));

        x++, y--;
    }
    return 0;
}
map<int, int> mp;
int main()
{
    int T = read();
    while (T--)
    {
        int n = read();
        mp.clear();
        for (int i = 1; i <= n; i++)
            R[i] = n + 1;
        for (int i = 1; i <= n; i++)
        {
            a[i] = read();
            if (mp.find(a[i]) == mp.end())
                L[i] = 0;
            else
                L[i] = mp[a[i]], R[mp[a[i]]] = i;
            mp[a[i]] = i;
        }
        if (solve(1, n))
            printf("non-boring\n");
        else
            printf("boring\n");
    }
}