Increasing Frequency

Created by LXC on Wed May 31 19:16:05 2023

https://codeforces.com/problemset/problem/1082/E

ranting: 2000

tag: binary search, dp, greedy

problem

给出n个数的数组$a_1, a_2, \cdots, a_n$，每个数范围在1到5e5内

给出正数c。

现在可以选取一段区间使其区间的每个数都增加k。k可以是任意整数。

现在问求最多有多少个数可以变成c。

solution

定义$f_{l,r,d}$为区间[l,r]内的数都增加c-d后，这个区间内的c个数。

我们要求的答案是$\max \limits_{1< l\le r < n, d \in a} f_{1,l-1, c} + f_{l,r,d}+f_{r+1, n, c}$。

等价于$\max \limits_{1< l\le r < n, d \in a} f_{1,n, c} + f_{l,r,d}-f_{l, r, c}$。

将问题转化，对于每个d，我们生成一个新的数组s，遍历数组a，当遇到d则将1加入到新数组s中，将a数组中以d作为分割点所有子段中的c的个数cnt统计下来，并将-cnt加入到s中。

举例

c = 2 d = 3
a = [1, 2, 3, 4, 2, 3, 1, 2, 2, 3, 4, 2]
s = [-1, 1, -1, 1, -2, 1]

我们只需求s的最大子段和便可以得到d的贡献。求出所有的
的贡献时间复杂度是$O(n)$

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

int a[N];
int p[N];
int pre[N];
vector<int> g[N];

int max_seg(vector<int>& s) {
    int mx = 0, cur = 0;
    for (int i = 0; i < s.size(); i++) {
        cur = max(cur + s[i], 0);
        mx = max(mx, cur);
    }
    return mx;
}

void sol() {
    int n, c;
    cin >> n >> c;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        p[i] = p[i - 1] + (a[i] == c);
    }
    for (int i = 1; i <= n; i++) {
        g[a[i]].push_back(-(p[i] - p[pre[a[i]]]));
        g[a[i]].push_back(1);
        pre[a[i]] = i;
    }
    int ans = 0;
    for (int i = 1, sz = *max_element(a + 1, a + n + 1); i <= sz; i++) {
        if (i == c)
            continue;
        // for (int j : g[i]) {
        //     cout << j << " ";
        // }
        // cout << "\n";
        ans = max(ans, max_seg(g[i]));
    }
    cout << p[n] + ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}