P14558 解题报告

· · 题解

前言

神秘爷爷辈 ROI，13 年题被 17 年出，21 年出，有点厉害的。

思路分析

根号啥的太无脑了吧，事实上 \log^2 也不太需要动脑。

存在一种 \log 的分治做法，不过猫猫不是很喜欢，我们直接来一个发掘性质的 O(n) 做法。

众数，也太难了。

我们知道有一种算绝对众数的方法叫摩尔投票法。

但这个东西也太垃圾了，每次一个区间的都要扫一遍才能算，如果不存在还不一定算的对要 shuffle 区间再多算几遍来检验存在性。

做不了怎么办？手动添加限制条件。

我们不妨考虑拆贡献，计算数字 x 为区间绝对众数的贡献。

那我们考虑类似摩尔投票的想法，令 a_i=2[a_i=x]-1，也就是相同赋 1，不同赋 -1。

那么一个区间以 x 为绝对众数就当且仅当区间和为正的时候。

然后我们经典操作一下，前缀和之后区间 [l,r] 的和即为 s_r-s_{l-1}。

然后这就是一个二维偏序嘛，s_{l-1}<s_r,l<r。

但直接转成二维偏序掉性质，导致带 \log 也太丑了。

你考虑每次最多 \pm1，画一下折线图。

然后你就知道，当你位于 (r,s_r) 的时候，你统计的事 l<r,s_{l-1}<s_r，但是每次 \pm1 保证了你不会有 s_{l-1}<s_r 的点突然被插入。

也就是我们只需要再累一个和记录下当前小于的数量和就可以了。

比较抽象所以先给个代码看看：

for(int i=1,s=n,ss=0;i<=k;i++)
{
  if(c[i]==x) ss+=cnt[s++],cnt[s]++;
  else ss-=cnt[--s],cnt[s]++;ans+=ss;
}

其中 c 是未累积前缀和的待统计数组，初值赋值为 n 旨在防止负数下标。

然后这样我们就得到了 O(nV) 做法，显然无法通过。

然后我们注意到什么？

你注意到如果有 w 个数 x，那么你所能取到的最大区间长度为 2w，这是一个极强的限制条件。

也就是说有很多很多的区间，他其实都是不可能取到的。

那我们怎样去掉大部分不合法的区间呢？

考虑从当前数字开始往右跑，一直累加和。

显然的是变成 -1 的时候就可以停下来了，到这里就没贡献了。

但现在有个问题就是形如这样的：

x,x,0,0,0,x,x,x

我们注意到右边那段可以把左边那段整个合并进去，所以光往右跑是有问题的。

那怎么办呢？

我们注意到假设向右跑出来的区间为 [l,r]，那么最远有贡献区间不会超过 [l-(r-l+1)+1,r]。

因为假设这个区间全是 x 左边也只能移动到这里。

那不带脑一点，直接给这个整个区间整个扔进去就好了（记得合并一下重复了的部分）。

然后我们算一下复杂度。

有 w 个 x，得到的所有区间总长度为 2w。

而我们刚刚又用了一次对称，所以卡满就是 4w 的。

因为有 \sum w=n，所以总区间长度复杂度还是 O(n) 的。

这里处理出了可用的区间，搭配上前面那个 O(len) 计算贡献的方式就可以得到严格线性的做法了。

代码

比较好写。

#include<bits/stdc++.h>
namespace Hoks
{
    #define ls (p<<1)
    #define rs (ls|1)
    #define mid ((l+r)>>1)
    using namespace std;
    const int N=5e5+10,B=2010,M=50,V=1e6,mod=95542721,INF=3e18;
    int n,v,m,k,a[N],c[N],cnt[N<<1];long long ans;
    vector<int>e[N];pair<int,int>b[N];
    namespace Fast_IO
    {
        static char buf[1000000],*paa=buf,*pd=buf,out[10000000];int length=0;
        #define getchar() paa==pd&&(pd=(paa=buf)+fread(buf,1,1000000,stdin),paa==pd)?EOF:*paa++
        inline int read()
        {
            int x(0),t(1);char fc(getchar());
            while(!isdigit(fc)){if(fc=='-') t=-1;fc=getchar();}
            while(isdigit(fc)) x=(x<<1)+(x<<3)+(fc^48),fc=getchar();
            return x*t;
        }
        inline void flush(){fwrite(out,1,length,stdout);length=0;}
        inline void put(char c){if(length==9999999) flush();out[length++]=c;}
        inline void put(string s){for(char c:s) put(c);}
        inline void print(long long x)
        {
            if(x<0) put('-'),x=-x;
            if(x>9) print(x/10);
            put(x%10+'0');
        }
        inline bool chk(char c) { return !(c=='.'||c=='#'||c=='('||c==')'||c==':'||c>='a'&&c<='z'||c>='A'&&c<='Z'||c>='0'&&c<='9'); }
        inline bool ck(char c) { return c!='\n'&&c!='\r'&&c!=-1&&c!=' '; }
        inline void rd(char s[],int&n)
        {
            s[++n]=getchar();
            while(chk(s[n])) s[n]=getchar();
            while(ck(s[n])) s[++n]=getchar();
            n--;
        }
    }
    using namespace Fast_IO;
    inline void solve()
    {
        n=read();v=read();for(int i=1;i<=n;i++) e[a[i]=read()].emplace_back(i);
        for(int x=1;x<=v;x++)
        {
            m=0;int lst=0;
            for(auto i:e[x])
            {
                if(lst>=i) continue;int t=i,s=0;
                while(t<=n&&s>=0) s+=2*(a[t]==x)-1,t++;
                b[++m]={i,min(t+1,n)};lst=t-1;
            }if(!m) continue;reverse(b+1,b+1+m);
            int r=b[1].second,l=b[1].first*2-r-1;k=0;
            for(int i=2;i<=m;i++)
                if(l<=b[i].second) l=min(l,b[i].first-(r-b[i].first)-1);
                else
                {
                    for(int j=r;j>=l&&j>=1;j--) c[++k]=a[j];
                    r=b[i].second,l=b[i].first*2-r-1;
                }
            for(int j=r;j>=l&&j>=1;j--) c[++k]=a[j];cnt[n]=1;
            for(int i=1,s=n,ss=0;i<=k;i++)
            {
                if(c[i]==x) ss+=cnt[s++],cnt[s]++;
                else ss-=cnt[--s],cnt[s]++;ans+=ss;
            }
            for(int i=1,s=n;i<=k;i++)
                if(c[i]==x) cnt[++s]=0;
                else cnt[--s]=0;
        }print(ans);put('\n');
    }
    inline void main()
    {
        int T=1;
        // T=read();
        while(T--) solve();
        genshin:;flush();
    }
}
signed main()
{
    Hoks::main();return 0;
}