本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-15 17:27:02

显然的，对于一个 $a_i$，我们把等于 $a_i$ 的设为 $1$，其他设为 $-1$，那么就转化成了求最大字段和。

考虑顺着枚举 $a_i$，对于当前 $i$ 暴力往后扫求以 $i$ 开始的极长区间 $[i,j]$，使得对于所有区间 $[i,k]$ 其中 $(i \le k \le j)$ 满足这个区间的和 $\ge 0$。

那么对于这个区间 $[i,j]$ 中所有的 $=a_i$ 的 $k$ 打上标记，下一次若遇到标记就不用再扫一遍了。

时间复杂度约为 $O(n \sqrt n)$，因为对于个数 $\le \sqrt n$ 的数字，每个的贡献是 $O(\sqrt n)$。而对于个数 $> \sqrt n$ 的数字，最多也就 $O(\sqrt n)$，所以这部分也就 $O(n \sqrt n)$，所以总时间复杂度为 $O(n \sqrt n)$。

#include <bits\/stdc++.h>

using namespace std;

int T;
int n;
int a[200010];

int main() {
    scanf("%d", &T);
    for (int Tc = 1; Tc <= T; ++Tc) {
        unordered_map<int, int> st;

        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);

        int ans = 0, v, l, r;
        for (int i = 1; i <= n; ++i) {
            if (st.count(i)) continue;

            int s = 0;
            for (int j = i; j <= n; ++j) {
                if (a[j] == a[i]) ++s, st[j] = 1;
                else --s;

                if (s > ans) {
                    ans = s;
                    v = a[i];
                    l = i, r = j;
                }
                if (s < 0) break;
            }
        }

        printf("%d %d %d\n", v, l, r);
    }
    return 0;
}