题解 P4062 【[Code+#1]Yazid 的新生舞会】

· · 题解

蒟蒻提供一种 n \sqrt n 的算法。

先考虑部分分怎么做。

对于 type=1 ，先计算众数为 1 的有多少区间，如果做一个前缀和，就是在问有多少对 (L,R) 满足： L<=R 且 sum_R-sum_{L-1}> \frac {R-L+1}{2}。

变一下柿子为：2*sum_R-R>2*sum_{L-1}-(L-1)。

枚举 R ，用树状数组这些数据结构维护就好，时间复杂度 O(n \log n) 。

不过为了后面的根号算法能过，还得优化一下这个计算过程，想办法丢掉一个 \log 。

考虑到 R-1 往后移一位，sum_R 要么等于 sum_{R-1}+1 ，要么等于sum_{R-1} ，那么 2*sum_R-R 的值相对于 2*sum_{R-1}-(R-1) 就会 +1 或者 -1，就可以根据已经计算好的 R-1 的贡献来修改进而得到 R 的贡献。

怎么修改？

这样一来查询的区间只会往左或往右移一位，那么就得知道多出来的一位或少了的一位贡献是多少，得到对应的变化量，开个桶记录一下所有的 2*sum_x-x 的相同的有多少个（x<R）就能进行修改了。（看文字没明白的画个图就懂啦）

这样就能做到 O(n) 求解。

对于 type=3 ，最多只有 8 个数字，同样枚举众数，把枚举的数所在的位置改成 1 ，其余为 0 ，解法同 type=1 的情况。

对于 type=2 ，意味着满足条件的区间长度最长不超过 30 ，可以暴力扫这些区间算答案，时间复杂度 O(30n)。

接下来就是根号算法啦！

上面的两种做法区别在于一个是针对数字种类，一个是针对数字出现次数。

不妨对每个数字出现的出现次数分个类。

对于所有 cnt_x \le \sqrt n 的数字 x，我们就暴力扫长度为 2 \sqrt n 的区间，所有这些数字的贡献都会被算到。（注意不要算了出现次数大于 \sqrt n 的数字的贡献 ），时间复杂度 O(n \sqrt n) 。

对于 cnt_x \geq \sqrt n 的，用 type=1 的做法做，这些不同的数字最多不会超过 \sqrt n 个，时间也是 O(n \sqrt n) 。

如果你不想用 type=1 的优化而是直接用树状数组，似乎也能过 ... ...

code: 
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;
int read() {
    char ch=getchar();int x=0,pd=0;
    while(ch<'0'||ch>'9') pd|=ch=='-',ch=getchar();
    while('0'<=ch&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return pd?-x:x;
}
const int maxn=505005;
int _max(int a,int b) { return a<b?b:a; }
int _min(int a,int b) { return a<b?a:b; }
int n,type;
int a[maxn];
int cnt[maxn],vis[maxn],cnt2[maxn];
int s1[maxn];
LL ans;
int main() {
    n=read(),type=read();
    for(int i=1;i<=n;i++) ++vis[a[i]=read()];
    int size=sqrt(n),limit=size*2;
    for(int i=1;i<=n;i++) {
        int maxx=0;
        for(int j=i;j<i+limit&&j<=n;j++) {
            if(vis[a[j]]<=size) maxx=_max(maxx,++cnt[a[j]]);
            if(maxx>(j-i+1)/2) ++ans;
        }
        for(int j=i;j<i+limit&&j<=n;j++)
            if(vis[a[j]]<=size) --cnt[a[j]];
    }
    for(int num=0;num<n;num++)
        if(vis[num]>size) {
            for(int i=0;i<=n+15;i++) cnt2[i]=0;
            int minn=0x3f3f3f3f;
            for(int i=1;i<=n;i++) {
                s1[i]=s1[i-1]+(a[i]==num);
                minn=_min(minn,2*s1[i]-i);
            }
            int p=1-minn+1,sum=0;
            cnt2[p]=1; // 有负数，加个偏移量 
            for(int i=1;i<=n;i++) {
                if(s1[i]==s1[i-1]) sum-=cnt2[ 2*s1[i-1]-(i-1)-1+p ];
                else sum+=cnt2[ 2*s1[i-1]-(i-1)+p ];
                ++cnt2[2*s1[i]-i+p];
                ans+=sum;
            }
        }
    printf("%lld\n",ans);
    return 0;
}