codeforces 1082E Increasing Frequency

coding ability going down sigh~
description：
Given array a[1…N], and number C
you are asked to add K to a continuous section of the array
and make the C most in a[]

solution:
At first, I assume this is an easy calculation problem
but later, I find that, the keypoint of this problem is the number C
when we operate an interval, the C in this part is changed while the others are the same
which means, we must find an interval and a number k so that the number of K in this interval minus the number of C in this interval is the biggest

then it is obvious that, we first separate array into different part according to the number
and for each number, find the optimized interval

the total complexity is O(N)

(I just realize an O(NlogN) version since the sort is easy to realize)

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 520000;

int N, C;
int sum[MAXN];
int a[MAXN], b[MAXN], c[MAXN];


int cmp(const int p, const int q) {
	if (a[p] != a[q])
		return a[p] < a[q];
	return b[p] < b[q];
}

int max(int a, int b) {
	return a > b ? a : b;
}

int main() {

	scanf("%d %d", &N, &C);

	for (int i = 1; i <= N; ++i) {
		scanf("%d", &a[i]);
		b[i] = i;
		c[i] = i;
		if (a[i] == C)
			sum[i] = 1;
		sum[i] += sum[i - 1];
	}

	sort(c + 1, c + N + 1, cmp);

	int Ans = sum[N];

	for (int i = 1; i <= N; ++i) {
		int now = c[i];
		if (a[now] == C)
			continue;
		for (int j = i; ; ++j)
			if (a[c[j]] != a[now]) {
				int cnt = 0, ls = 0;
				for (int k = i; k < j; ++k) {
					int l = b[c[k]];
					cnt = max(0, cnt - (sum[l]-sum[ls]))+1;
					Ans = max(Ans, sum[N] + cnt);
					ls = l;
				}
				i = j-1;
				break;
			}

	}

	printf("%d", Ans);
	return 0;
}