给出一个跑得快一点的做法，洛谷最优解 (时间是第二名的 (frac{1}{2})), CF 第一页
D1
首先找到整个序列的众数 (G), 很容易证明答案序列中的两个众数中其中一个是 (G) 。
知道了这个结论以后，我们可以枚举在序列中出现的数 (K), 让 (G) 的权值为 (1), (K) 的权值为 (-1), 然后就找一下最长的权值为 (0) 的串即可。这个开个桶统计即可。
这个和大家一样，就不多说了。
Code(片段) :
const int N = 2e5 + 7;
int n, a[N], cnt[N], zs, ans, fir[N << 1];
void work(int x) {
int now = N;
memset(fir, -1, sizeof(fir));
fir[now] = 0;
L(i, 1, n) {
if(a[i] == zs) now ++;
else if(a[i] == x) now --;
if(fir[now] == -1) fir[now] = i;
else ans = max(ans, i - fir[now]);
}
}
int main() {
scanf("%d", &n);
L(i, 1, n) scanf("%d", &a[i]), cnt[a[i]] ++;
L(i, 1, n) if(cnt[i] > cnt[zs]) zs = i;
L(i, 1, min(n, 100)) if(i != zs) work(i);
printf("%d
", ans);
return 0;
}
D2
同样令众数为 (G)。
根号分治。
对于出现次数 (> B) 的数，可以像 (D1) 一样处理。
对于出现次数 (le B) 的数 (设为 (K))（重点）：
设出现次数为 (cnt)。
首先可以枚举选中的序列的第一个出现 (K) 的位置是 (K) 的第几次出现的位置。
然后发现这个序列中包含的 (G) 的个数一定 (le cnt)。
于是我们可以只考虑枚举的这个位置前面的 (cnt) 个 (G) (不能包含上一个数字 (K)) 和后面 (cnt) 个 (G) (可以包含后面的数字 (K)) ，然后按照 (D1) 的方法做即可。
有一些细节，具体见代码。
Code :
#include<bits/stdc++.h>
#define L(i, j, k) for(int i = j, i##E = k; i <= i##E; i++)
#define R(i, j, k) for(int i = j, i##E = k; i >= i##E; i--)
#define ll long long
#define ull unsigned long long
#define db double
#define pii pair<int, int>
#define mkp make_pair
using namespace std;
char buf[256],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,256,stdin),p1==p2)?EOF:*p1++)
inline int read() {
int x = 0, f = 1; char ch = getchar();
while(!isdigit(ch)) { if(ch=='-') f = -1; ch = getchar(); }
while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
return x * f;
}
const int N = 2e5 + 7;
const int B = 233;
int n, a[N], cnt[N], zs, ans;
int fir[N << 1];
int max(int x, int y) { return x > y ? x : y; }
void worka(int x) {
int now = N;
memset(fir, -1, sizeof(fir));
fir[now] = 0;
L(i, 1, n) {
if(a[i] == zs) now ++;
else if(a[i] == x) now --;
if(!~fir[now]) fir[now] = i;
else ans = max(ans, i - fir[now]);
}
}
int lef[N], rig[N], f[N], fg[N];
vector<int> ve[N];
void workb(int x) {
L(i, 1, cnt[x]) {
fill(fir + N - cnt[x] - 2, fir + N + cnt[x] * 2 + 3, -1);
int tot = 0, las = (i == 1 ? 0 : ve[x][i - 2]), now = ve[x][i - 1], len = 0;
while(lef[now - 1] > las && len <= cnt[x]) now = lef[now - 1], ++len, f[++tot] = now;
int dd = i, KK = N;
if(!lef[now - 1] && i == 1) fir[N] = 0;
reverse(f + 1, f + tot + 1);
f[++tot] = ve[x][i - 1], fg[tot] = 1;
now = ve[x][i - 1], len = 0;
while(rig[now + 1] && len <= cnt[x]) {
now = rig[now + 1];
while(dd < cnt[x] && ve[x][dd] < now) f[++tot] = ve[x][dd], fg[tot] = 1, ++ dd;
++len, f[++tot] = now;
}
if(len <= cnt[x]) while(dd < cnt[x]) f[++tot] = ve[x][dd], fg[tot] = 1, ++ dd;
f[tot + 1] = n + 1;
if(rig[now + 1]) f[tot + 1] = rig[now + 1];
L(j, 1, tot) {
if(fg[j] == 1) -- KK, fg[j] = 0; else ++ KK;
if(!~fir[KK]) fir[KK] = f[j];
else ans = max(ans, f[j + 1] - 1 - fir[KK]);
}
}
}
int main() {
n = read();
L(i, 1, n) a[i] = read(), cnt[a[i]] ++;
L(i, 1, n) if(cnt[i] > cnt[zs]) zs = i;
L(i, 1, n) if(a[i] == zs) lef[i] = rig[i] = i;
L(i, 1, n) if(!lef[i]) lef[i] = lef[i - 1];
R(i, n, 1) if(!rig[i]) rig[i] = rig[i + 1];
L(i, 1, n) if(cnt[a[i]] <= B) ve[a[i]].push_back(i);
L(i, 1, n) if(i != zs) {
if(cnt[i] > B) worka(i);
else workb(i);
}
printf("%d
", ans);
return 0;
}