「题解」洛谷 P4062 [Code+#1]Yazid 的新生舞会 线性做法

· · 题解

还是考虑那个众数的套路，考虑一个数 c 的贡献，将 c 置为 1，不是 c 的置为 -1，那么一个区间和 >0 的绝对众数是 c．

从左往右和从右往左各跑一边，每次让一个 +1 匹配左边第一个没匹配的 -1 （没有的话就匹配到虚空），如果一个位置从前往后或者从后往前都没匹配到，意味着它不可能和其他位置组成逆序对，这个位置就会寄掉，用并查集即可完成匹配。

跑出了这些绝对众数可能为 c 的连续段，这些连续段的总长度至多是 c 出现次数的两倍，所以所有 c 的若干连续段的总长是 \mathcal{O}(n) 的。

那么作前缀和，在每个连续段内对答案的贡献就是一个二维数点的形式。

注意到相邻数只会有 \pm 1 的改变，那么扫描线的时候，考虑计算这一个位置统计的答案和上一个位置的差值是多少即可，只需要开个桶记录一下每个值的出现次数。

如果使用线性序列并查集算法，复杂度是 \mathcal{O}(n) 的，不过写这篇题解的时候用纯路径压缩跑到了洛谷上第一。

找出极长连续段的实现上需要精细一点，可能要双指针什么的（

#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<ctime>
#include<random>
#define pb emplace_back
#define mp std::make_pair
#define fi first
#define se second
#define dbg(x) cerr<<"In Line "<< __LINE__<<" the "<<#x<<" = "<<x<<'\n';
#define dpi(x,y) cerr<<"In Line "<<__LINE__<<" the "<<#x<<" = "<<x<<" ; "<<"the "<<#y<<" = "<<y<<'\n';
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>pii;
typedef pair<ll,int>pli;
typedef pair<ll,ll>pll;
typedef vector<int>vi;
typedef vector<ll>vll;
typedef vector<pii>vpii;
inline void cmax(int &x, int y){x=x>y?x:y;}
inline void cmin(int &x, int y){x=x<y?x:y;}
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
inline void read(int &r){
    r=0;bool w=0;char ch=getchar();
    while(ch<'0'||ch>'9')w=ch=='-'?1:0,ch=getchar();
    while(ch>='0'&&ch<='9')r=r*10+(ch^48),ch=getchar();
    r=w?-r:r;
}
const int N=500100;
int n,type;
int a[N],L[N],R[N],visbuf[N<<1],*vis=visbuf+N;
vi vec[N];
ll ans;
int f[N],p[N];
int st[N],top;
int getfa1(int x){
    return f[x]==x?x:f[x]=getfa1(f[x]);
}
void merge1(int x,int y){
    int fx=getfa1(x),fy=getfa1(y);
    f[fy]=fx;
}
int getfa2(int x){
    return p[x]==x?x:p[x]=getfa2(p[x]);
}
void merge2(int x,int y){
    int fx=getfa2(x),fy=getfa2(y);
    p[fy]=fx;
}
signed main(){
    read(n);read(type);
    for(int i=1;i<=n;i++)read(a[i]),p[i]=f[i]=i,vec[a[i]].pb(i);
    p[n+1]=f[n+1]=n+1;
    for(int o=0;o<n;o++){
        int mn=n+1;top=0;
        for(auto i:vec[o]){
            int fa=getfa1(i-1);
            merge1(fa,i);
            if(fa)merge1(fa-1,fa);
            L[i]=fa;
            while(top&&st[top]>fa)--top;
            st[++top]=fa;
        }
        reverse(vec[o].begin(),vec[o].end());
        for(auto i:vec[o]){
            int fa=getfa2(i+1);
            merge2(fa,i);
            if(fa<=n)merge2(fa+1,fa);
            cmax(R[L[i]],fa);
        }
        reverse(vec[o].begin(),vec[o].end());
        for(int k=1;k<=top;k++){
            int l=st[k],r=R[l];
            while(l<=r){
                ++l;cmax(r,R[l]);
            }
            l=st[k];cmin(r,n);
            int cnt=0,s=0;
            for(int i=l;i<=r;i++){
                L[i]=R[i]=0;f[i]=p[i]=i;
                if(i){
                    if(a[i]==o)cnt+=vis[s++];
                    if(a[i]!=o)cnt-=vis[--s];
                }
                ++vis[s];
                ans+=cnt;
            }
            s=0;
            for(int i=l;i<=r;i++){
                if(i){
                    if(a[i]==o)++s;
                    if(a[i]!=o)--s;
                }
                vis[s]=0;
            }
            while(k<=top&&st[k]<=r)
                ++k;
            --k;
        }
        #undef now
    }
    cout << ans << '\n';
    return 0;
}