codeforces+E. Increasing Frequency+技巧

题目链接：http://codeforces.com/contest/1082/problem/E
题目大意：给你一个长度为序列，和一个c,你可以对一个区间[l,r] (l<=r)内的所有元素，进行加或者减一个k，只能操作一次。问你这样得到的序列中c元素最多为多少？(1≤n≤5⋅10^5 )

思路：如果枚举每个区间。那么复杂度为O(n ^2)。超时。
因为翻转的区间里内的相同数字的个数大于c的个数。这样才能使得c的个数增多。但是我们可以从0开始，如果0-x区间内。c的个数>=相同数字的最大个数那么这个区间就肯定不会翻转。这个时候可以把所有的个数清0，重新统计。但是可以使得次时的个数a[i]=c的个数cut，那么就可以用a[i]-cut统计翻转此区间能额外的个数。
所以只要把序列扫一遍输出cut+max(a[i]-cut)就行了。

#include<bits/stdc++.h>
using namespace std;
const int MAX= 500005;

int a[MAX];
int main()
{
    fill(a, a+MAX, 0);
    int n, k, cut=0, m=0, x;
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        scanf("%d",&x);
        if(x==k)/*统计k的个数*/
            cut++;
        else
        {
            if(a[x]<cut)/*翻转此区间不能得到额外的k的个数*/
                a[x]=cut;/* 置'0' */

            a[x]++;

            m=max(m, a[x]-cut);/*统计能额外得到的k的最大个数/
        }
    }
    cout<<m+cut<<endl;

    return 0;
}