题解 P7882

· · 题解

考虑转化为求 \sum\limits_{x}x\sum\limits_{[l,r]\subset[L,R]}[\text{Mode}(l,r)=x]。

首先我们将 [\text{Mode}(l,r)=x] 转化一手。

f_{i,x}=\begin{cases}1&(a_i=x)\\-1&(a_i\neq x)\\\end{cases} \left[\text{Mode}(l,r)=x\right]=[\sum\limits_{i=l}^rf_{i,x}>0]

考虑将序列从左向右扫一遍，可以扫出若干满足 \sum\limits_{i=l}^rf_{i,x}>0 的极长区间。

不难发现对于所有 x 的所有极长区间，它们的长度和不会超过 2n。

注意到如果一个区间比较小，我们直接枚举出合法的区间进行二维数点即可，时间复杂度 O(nB+m\sqrt n)。

考虑区间较大的情况，问题可以直接转化为区间逆序对，时间复杂度 O((\sum n)\sqrt m+m\sqrt n)。

直接阈值分治就行了，总时间复杂度 O(n\sqrt m+m\sqrt n)，注意二次离线莫队的时间复杂度一定要写成 O(n\sqrt m+m\sqrt n)，写出 O(m\sqrt m) 就寄了。

因为心情好就给个代码吧。

// Problem: P7882 [Ynoi2006] rsrams
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P7882
// Memory Limit: 512 MB
// Time Limit: 8000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//gzjrr,ddjcc
#include<bits/stdc++.h>
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
using namespace std;
#define ll long long
char buf[1<<21],*p1=buf,*p2=buf,obuf[1<<25],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
void print(ll x) {
    if(x>9) print(x/10);
    *O++=x%10+'0';
}
inline int read()
{
    int s=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') s*=10,s+=ch^48,ch=getchar();
    return s;
}
const int B=3000;
int A[1000003];
vector<int> v[1000003];
struct node{int l,r;}Q[1000003];
vector<node> z[1000003];
ll pre0[1000003],pre1[1003];
struct node3{int l,r,x;};
vector<node3> R;
struct node4{int l,r,id,op;};
vector<node4> f[1000003];
ll ans[1000003];
int n=read(),m=read();
inline void ins(int x,int k)
{
    pre0[x]+=k,pre1[x>>10]+=k;
    return ;
}
inline ll query(int x)
{
    ll res=0;
    for(int i=(x>>10)<<10; i<=x; ++i) res+=pre0[i];
    for(int i=0; i<(x>>10); ++i) res+=pre1[i];
    return res;
}
struct Mo
{
    int N,M,B,L;
    struct mq
    {
        int l,r,bl,id;
        bool operator<(const mq&t)const
        {
            return bl<t.bl||(bl==t.bl&&((bl&1)?r<t.r:r>t.r));
        }
    }q[1000003],tmp[1000003];
    struct oq{int l,r,id,op;};
    vector<oq> vp[1000003],vs[1000003];
    ll tans[1000003],pre[1000003],suf[1000003];
    int a[1000003],tree[1000003],pre0[1100003],pre1[1003];
    inline void add(int x)
    {
        while(x<=N) ++tree[x],x+=x&(-x);
        return ;
    }
    inline int find(int x)
    {
        int res=0;
        while(x) res+=tree[x],x-=x&(-x);
        return res;
    }
    inline void ins(int x)
    {
        for(int i=x,r=((x>>L)+1)<<L; i<r; ++i) ++pre0[i];
        for(int i=(x>>L)+1; (i<<L)<=N; ++i) ++pre1[i];
    }
    inline int query(int x)
    {
        return pre1[x>>L]+pre0[x];
    }
    int lsh[1000003];
    void main(int tl,int tr,int mul)
    {
        N=0,M=m,L=0;
        for(int i=tl,s=0; i<=tr; ++i) 
            ++N,lsh[N]=a[N]=((s+=(A[i]==mul?1:-1)));
        while((1<<(L<<1))<=N) ++L;
        for(int i=1,o=0; o<m; ++i)
            q[i].l=max(Q[++o].l-1,tl)-tl+1,
            q[i].r=min(Q[o].r,tr)-tl+1,q[i].id=o,tans[i]=0,
            (q[i].l>=q[i].r)&&(--i,--M);
        if(!M) return ;
        B=N/sqrt(M*2/3+1)+1,sort(lsh+1,lsh+N+1);
        int L=unique(lsh+1,lsh+N+1)-lsh-1;
        for(int i=0; i<=N+1; ++i)
            vector<oq>().swap(vp[i]),
            vector<oq>().swap(vs[i]);
        for(int i=1; i<=N; ++i) 
            a[i]=lower_bound(lsh+1,lsh+L+1,a[i])-lsh;   
        memset(lsh,0,(N+1)<<2);
        for(int i=1; i<=M; ++i) 
            q[i].bl=q[i].l/B,++lsh[q[i].r];
        for(int i=1; i<=N; ++i) lsh[i]+=lsh[i-1];
        for(int i=1; i<=M; ++i) tmp[lsh[q[i].r]--]=q[i];
        memset(lsh,0,(N+1)<<2);
        for(int i=1; i<=M; ++i) ++lsh[q[i].bl];
        for(int i=1; i<=N; ++i) lsh[i]+=lsh[i-1];
        for(int i=1; i<=N; ++i,++i) lsh[i]=lsh[i-1];
        for(int i=1; i<=M; ++i) 
            if(tmp[i].bl&1) q[++lsh[tmp[i].bl]]=tmp[i];
            else q[lsh[tmp[i].bl]--]=tmp[i];
        memset(tree,0,(N+1)<<2);
        for(int i=1; i<=N; ++i)
            pre[i]=pre[i-1]+find(a[i]-1),add(a[i]);
        memset(tree,0,(N+1)<<2),suf[N+1]=0;
        for(int i=N; i>=1; --i)
            suf[i]=suf[i+1]+N-i-find(a[i]),add(a[i]);
        for(int i=1,l=1,r=0; i<=M; ++i)
        {
            if(r<q[i].r) 
                tans[i]+=pre[q[i].r]-pre[r],
                vp[l-1].push_back((oq){r+1,q[i].r,i,-1}),r=q[i].r;
            if(l>q[i].l)
                tans[i]+=suf[q[i].l]-suf[l],
                vs[r+1].push_back((oq){q[i].l,l-1,i,-1}),l=q[i].l;
            if(r>q[i].r) 
                tans[i]-=pre[r]-pre[q[i].r],
                vp[l-1].push_back((oq){q[i].r+1,r,i,1}),r=q[i].r;
            if(l<q[i].l)
                tans[i]-=suf[l]-suf[q[i].l],
                vs[r+1].push_back((oq){l,q[i].l-1,i,1}),l=q[i].l;
        }
        memset(pre0,0,((N>>10)+1)<<12),memset(pre1,0,sizeof(pre1));
        for(int i=1; i<=N; ++i)
        {
            ins(a[i]);
            for(oq j:vp[i])
                for(int k=j.l; k<=j.r; ++k)
                    tans[j.id]+=query(a[k]-1)*j.op;
        }
        memset(pre0,0,((N>>10)+1)<<12),memset(pre1,0,sizeof(pre1));
        for(int i=N; i>=1; --i)
        {
            ins(a[i]);
            for(oq j:vs[i])
                for(int k=j.l; k<=j.r; ++k)
                    tans[j.id]+=(N-i+1-query(a[k]))*j.op;
        }
        for(int i=1; i<=M; ++i) tans[i]+=tans[i-1];
        for(int i=1; i<=M; ++i) ans[q[i].id]+=tans[i]*mul;
        return ;
    }
}T;
int tmp[1000003],smx[1000003];
signed main()
{
    for(int i=1; i<=n; ++i) 
        A[i]=read(),v[A[i]].push_back(i);
    for(int i=1,l,r; i<=m; ++i) 
        Q[i].l=l=read(),Q[i].r=r=read(),
        f[l-1].push_back((node4){l,r,i,-1}),
        f[r].push_back((node4){l,r,i,1});
    for(int i=1,sz=v[1].size(); i<=n; ++i,sz=v[i].size()) if(sz)
    {
        for(int j=0; j<sz; ++j) tmp[j]=(j<<1)-v[i][j];
        smx[sz]=0xc0c0c0c0;
        for(int j=sz-1; j>=0; --j) smx[j]=max(smx[j+1],tmp[j]);
        for(int j=0,k,l,r,mn=tmp[j],mx=tmp[j]; 
        j<sz; j=k+1,mn=tmp[j],mx=tmp[j])
        {
            for(k=j; mn<=smx[k+1]; 
                ++k,mn=min(mn,tmp[k]),mx=max(mx,tmp[k]));
            l=max(v[i][j]-mx+tmp[j],1),
            r=min(v[i][k]+tmp[k]-mn,n);
            if(r-l<B)
                for(int k=l; k<=r; ++k) 
                    z[k].push_back((node){l,i});
            else R.push_back((node3){l-1,r,i});
        }
    }
    for(node3 i:R)
        T.main(i.l,i.r,i.x);
    for(int i=1; i<=n; ++i)
    {
        for(node j:z[i])
            for(int k=i,s=0; k>=j.l; --k)
                ((s+=(A[k]==j.r?1:-1))>0)&&(ins(k,j.r),0);
        for(node4 j:f[i])
            ans[j.id]+=(query(j.r)-query(j.l-1))*j.op;
    }
    for(int i=1; i<=m; ++i) print(ans[i]),*O++='\n';
    fwrite(obuf,O-obuf,1,stdout);
    return 0;
}