\(\color{#0066ff}{ 题目描述 }\)
给你一个长度为 \(n\) 的数列 \(a\) ,你可以任意选择一个区间 \([l,r]\), 并给区间每个数加上一个整数 \(k\), 求这样一次操作后数列中最多有多少个数等于 \(c\)
\(\color{#0066ff}{输入格式}\)
第一行两个整数 \(n\), \(c\) . 第二行 \(n\) 个整数 \(a_1,a_2,...,a_n\).
\(\color{#0066ff}{输出格式}\)
输出一个整数表示答案。
\(\color{#0066ff}{输入样例}\)
6 9
9 9 9 9 9 9
3 2
6 2 6\(\color{#0066ff}{输出样例}\)
6
2\(\color{#0066ff}{数据范围与提示}\)
\(1\le n,c,a_i \le 5\cdot 10^5\).
\(\color{#0066ff}{ 题解 }\)
考虑暴力，枚举区间左右端点
当前的答案为区间内出现最多的数的个数+区间外c的个数
对于区间外c的个数，可以用前缀后缀和来维护
现在考虑区间维护
可以发现，离散化后的数最多n个
既然不知道区间出现最多的数的次数
就考虑枚举值域，强制让其为次数最多的数，开vector记录出现的位置
上面的强制是不会影响答案的（因为一定会找到最优情况）
对于枚举的每个位置，考虑\(ans = x + y + r - l + 1\)
x是l前面c的个数（前缀和维护），y是r后面c的个数（后缀和维护）
(r - l + 1)是出现次数，因为我们用vector存了它出现的位置，所以直接vector下标作差就是出现次数
则\(ans = (x -l) + (r+y+1)\)
要使ans最大， 则两边都最大，而且左边只与l有关，右边只与r有关
我们枚举l的时候，左边的值是固定的，然后对于右边的值，开个变量维护一下max就行
因为总共就n个位置，所以复杂度\(O(n)\)
#include<bits/stdc++.h>
#define LL long long
LL in() {
char ch; LL x = 0, f = 1;
while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);
for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48));
return x * f;
}
const int maxn = 5e5 + 100;
int n, c, a[maxn], b[maxn];
int l[maxn], r[maxn], dp[maxn];
std::vector<int> v[maxn];
int main() {
n = in(), c = in();
for(int i = 1; i <= n; i++) a[i] = b[i] = in();
b[n + 1] = c;
std::sort(b + 1, b + n + 2);
int len = 1;
for(int i = 2; i <= n + 1; i++) if(b[i] != b[i - 1]) b[++len] = b[i];
for(int i = 1; i <= n; i++) a[i] = std::lower_bound(b + 1, b + len + 1, a[i]) - b;
c = std::lower_bound(b + 1, b + len + 1, c) - b;
for(int i = 1; i <= n; i++) l[i] = l[i - 1] + (a[i] == c);
for(int i = n; i >= 1; i--) r[i] = r[i + 1] + (a[i] == c);
for(int i = 1; i <= n; i++) v[a[i]].push_back(i);
for(int i = 1; i <= len; i++) {
int max = -maxn;
for(int j = (int)v[i].size() - 1; j >= 0; j--) {
max = std::max(max, r[v[i][j] + 1] + 1 + j);
dp[i] = std::max(dp[i], max + l[v[i][j] - 1] - j);
}
}
int ans = 0;
for(int i = 1; i <= len; i++) ans = std::max(ans, dp[i]);
printf("%d\n", ans);
return 0;
}
/*x + y + j - i + 1 = (x - i) + (y + j + 1) */