CF-R765-B题解

Codeforces Round #765被橄榄了。但B与C两题都刚好处在有思路而没解出来的难度，是很好的学习机会。

题目描述

Elementary Particles

Martians(火星人) are actively engaged(吸引，卷入) in interplanetary trade. Olymp City, the Martian city known for its spaceport, has become a place where goods from all the corners of our Galaxy come. To deliver even more freight(货物；运费) from faraway planets, Martians need fast spaceships.

A group of scientists conducts experiments to build a fast engine for the new spaceship. In the current experiment, there are elementary(基本的；元素的) particles, the -th of them has type .

Denote subsegment of the particle sequence as a sequence for some left bound and right bound . For instance, the sequence (1 4 2 8 5 7) for and has the sequence (4 2 8) as a subsegment. Two subsegments are considered different if at least one bound of those subsegments differs.

Note that the subsegments can be equal as sequences but still considered different. For example, consider the sequence (1 1 1 1 1) and two of its subsegments: one with and and another with and . Both subsegments are equal to (1 1 1), but still considered different, as their left and right bounds differ.

The scientists want to conduct(指导；引导；指挥) a reaction(反应) to get two different subsegments of the same length. Denote this length . The resulting pair of subsegments must be harmonious, i. e. for some it must be true that the types of particles on the -th position are the same for these two subsegments. For example, the pair (1 7 3) and (4 7 8) is harmonious, as both subsegments have 7 on the second position. The pair (1 2 3) and (3 1 2) is not harmonious.

The longer are harmonious subsegments, the more chances for the scientists to design a fast engine. So, they asked you to calculate the maximal possible length of harmonious pair made of different subsegments.

Input

The first line contains an integer — the number of test cases. The following are descriptions of the test cases.

The first line contains an integer — the amount of elementary particles in the sequence.

The second line contains integers — types of elementary particles.

It is guaranteed that the sum of over all test cases does not exceed .

Output

For each test, print a single integer, maximal possible length of harmonious pair made of different subsegments. If such pair does not exist, print instead.

Example

input:

4
7
3 1 5 2 1 3 4
6
1 1 1 1 1 1
6
1 4 2 8 5 7
2
15 15

output:

4
5
-1
1

解释

给定一个序列，找出两个连续子序列，满足：

1. 两个子序列的在原序列中的位置不同，可以重叠但不能相等。
2. 两个子序列至少有一个相同位置的元素相同。相同位置可以理解为数组下标，即要求至少存在一个i，使得a[i]=b[i]成立。
3. 两个子序列长度相等，且为所有符合要求的子序列组中最长的。

若存在这个的子序列组，输出它的长度。否则输出。

思路

暴力

遍历所有子序列，并比对它们是否符合条件。由于长度是相等的，对于每种可能的长度只要确定起点就确定了终点。因此遍历时间复杂度为：

此外还得对每种遍历结果进行比对，时间复杂度。总时间复杂度为。不用考虑了，没戏。

贪心

稍作思考，可以发现本题中只有序列起点会影响是否符合条件。因此可以使用下面的方式，逐步位移来比对序列，一但出现相同位置相同元素，则两序列重叠部分即为最长的序列组。

此时时间复杂度就降低至：位移 ， 匹配 ，总时间复杂度。仍然不可接受，

这里发现实际上我们的要求就是通过最短的位移将一对相同的元素对上。那只要找到原序列中最短相同元素对就可以了。位移后的长度损失为两元素间距，侧最长序列组长度为。

找最短相同元素对需要为元素进行一次复杂度的遍历，则时间复杂度仍然是。此时可以使用一个map记录下每个元素的最小元素对，然后只要一次搜索即可。时间复杂度为。可以接受了。

本题由于空间够大，可以将map换成数组，将时间复杂度降低到。

代码实现

#include <iostream>

using namespace std;

constexpr unsigned int MAX = 150005;

// 存储上个元素的位置
int l[MAX];
// 存储当前元素的位置
int r[MAX];
// 存储元素最小间距
int d[MAX]

void init() {
    for (int i = 0; i < MAX; ++i) {
        l[i] = 0; 
        r[i] = 0; 
        d[i] = MAX;
    }
}

void input() {
    int n;
    cin >> n;
    
    for (int i = 1; i <= n; ++i) {
        int tmp;
        cin >> tmp;

        // 如果是第一个元素，则加入l。
        // 如果第二个则加入r并计算间距。
        // 否则更新位置并计算间距。
        if (l[tmp] == 0) {
            l[tmp] = i;
        } else if (r[tmp] == 0) {
            r[tmp] = i;
            d[tmp] = min(d[tmp], r[tmp] - l[tmp]);
        } else {
            l[tmp] = r[tmp];
            r[tmp] = i;
            d[tmp] = min(d[tmp], r[tmp] - l[tmp]);
        }
    }
}

void output() {
    // 因为没有结果时，输出将是n - m，且要求为-1，故置m为n+1。
    int m = n + 1;
    // 使用最小的间距值来代替m。
    for (int i = 0; i < MAX; ++i ) {
        m = min(d[i], m);
    }
    cout << n - m << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        init();
        input();
        output(); 
    }
    return 0;
}