CF1416A-k-Amazing Numbers

2020-09-30 约 645 字预计阅读 2 分钟次阅读

CF1416A-k-Amazing Numbers

题目:

题目描述:

You are given an array $ a $ consisting of $ n $ integers numbered from $ 1 $ to $ n $ .

Let’s define the $ k $ -amazing number of the array as the minimum number that occurs in all of the subsegments of the array having length $ k $ (recall that a subsegment of $ a $ of length $ k $ is a contiguous part of $ a $ containing exactly $ k $ elements). If there is no integer occuring in all subsegments of length $ k $ for some value of $ k $ , then the $ k $ -amazing number is $ -1 $ .

For each $ k $ from $ 1 $ to $ n $ calculate the $ k $ -amazing number of the array $ a $ .

输入格式:

The first line contains one integer $ t $ ( $ 1 \le t \le 1000 $ ) — the number of test cases. Then $ t $ test cases follow.

The first line of each test case contains one integer $ n $ ( $ 1 \le n \le 3 \cdot 10^5 $ ) — the number of elements in the array. The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le n $ ) — the elements of the array.

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 3 \cdot 10^5 $ .

输出格式:

For each test case print $ n $ integers, where the $ i $ -th integer is equal to the $ i $ -amazing number of the array.

样例:

样例输入 1:

1
2
3
4
5
6
7
3
5
1 2 3 4 5
5
4 4 4 4 2
6
1 3 1 5 3 1

样例输出 1:

1
2
3
-1 -1 3 2 1
-1 4 4 4 2
-1 -1 1 1 1 1

思路:

实现:

 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
#include "ybwhead/ios.h"
int n;
const int maxn = 3e5 + 10;
int ma[maxn], las[maxn];
int cmp(int a, int b)
{
    return ma[a] < ma[b] || ma[a] == ma[b] && a < b;
}
int main()
{
    int TTT;
    yin >> TTT;
    while (TTT--)
    {
        yin >> n;
        for (int i = 1; i <= n; i++)
            las[i] = 0, ma[i] = 0;
        for (int i = 1; i <= n; i++)
        {
            int x;
            yin >> x;
            // if (las[x])
            ma[x] = max(ma[x], i - las[x]);
            las[x] = i;
        }
        for (int i = 1; i <= n; i++)
            ma[i] = max(ma[i], n + 1 - las[i]);
        for (int i = 1; i <= n; i++)
            las[i] = i;
        sort(las + 1, las + n + 1, cmp);
        int kk = 1, ans = -1;
        for (int i = 1; i <= n; i++)
        {
            if (ma[las[i]] > kk)
            {
                for (int j = kk; j < ma[las[i]]; j++)
                    yout << ans << " ";
                kk = ma[las[i]];
            }
            if (ans >= 0)
                ans = min(ans, las[i]);
            else
                ans = las[i];
        }
        if (kk == 1)
            for (int i = 1; i <= n; i++)
                yout << las[1] << " ";
        else
            for (int j = kk; j <= n; j++)
                yout << ans << " ";
        yout << endl;
    }
}

目录

CF1416A-k-Amazing Numbers

CF1416A-k-Amazing Numbers

题目:

题目描述:

输入格式:

输出格式:

样例:

样例输入 1:

样例输出 1:

思路:

实现: