[LOJ 6253] Yazid 的新生舞会

$solution:$

不知道为什么别人的代码能写的非常短，难道就是写差分的好处?

这种题肯定是算每个众数的贡献，考虑通过暴力众数求出个数。

现在考虑众数 $x$ ，则在序列 $a$ 中将等于 $x$ 的置为 $1$ ，否则置为 $-1$，令为序列 $A$ 。设 $S_i=\sum_{k=1}^i A_k$。

若 $[l,r]$ 是满足题意的区间，则 $S_r>S_{l-1}$ ，所以对于每个众数 $x$ ，求出满足 $i>j,S_i>S_j$ 的方案数，直接求二维偏序即可，时间复杂度 $O(n^2\log n)$ ，并不能通过本题。

但是，我们能发现一个性质,在每个 $A$ 中只会有很少的 $1$ ，与很多的 $-1$ 出现，因为 $1$ 只能在 $A$ 中出现 $n$ 次。对于连续 $-1$ 段来说不可能 $l,r$ 均在其中，并且它们的 $S$ 值是每次减一，所以考虑将它们合为一个，其 $S$ 的范围为 $[L,R]$ ，可以简单发现连续段个数与 $n$ 同阶。

考虑将 $-1$ 连续段中作为右端点对答案的贡献，设 $l,r$ 为连续段的左右端点，$L,R$ 为 $S$ 的范围，$C_i$ 为满足 $S_k=i,k\in [0,i)$ 的个数。

则容易推出$$Ans=\sum_{i=-n}^{L-1} C_i\times (R-L+1)+\sum_{i=L}^R C_i\times (R-i)\\=\sum_{i=-n}^{L-1} C_i\times (R-L+1)+\sum_{i=L}^R C_i-\sum_{i=L}^R C_i\times i$$

发现 $\sum_{i=-n}^{L-1} C_i\times (R-L+1)$ 这两个式子直接线段树区间加法维护即可，而 $\sum_{i=L}^R C_i\times i$ 直接线段树上维护等差数列即可。

现在考虑完右端点在 $-1$ 的情况，而右端点在 $1$ 时直接线段树查询 $[-n,S_{i}-1]$ 即可。

因为区间段与 $n$ 同阶，所以时间复杂度为 $O(n\log n)$ 。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#define int long long

using namespace std;

inline int read(){

    int f=,ans=;char c=getchar();

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}

    return f*ans;

}

const int MAXN=;

int n,a[MAXN];

vector<int> ve[MAXN];

struct Segment1{

    int Ans[MAXN<<],Beg[MAXN<<],D[MAXN<<],qx[MAXN],qy[MAXN],qbe[MAXN],qd[MAXN],tot;

    inline void clear(){

        for(int i=;i<=tot;i++) Modify(,,*n,qx[i],qy[i],-qbe[i],-qd[i]);

        tot=;

    }

    inline void pushdown(int k,int l,int r){

        int mid=l+r>>;

        if(!Beg[k]&&!D[k]) return;

        Ans[k<<]+=Beg[k]*(mid-l+)+((((mid-l+)*(mid-l))/)*D[k]);

        Ans[k<<|]+=Beg[k]*(r-mid)+((((r+mid-*l+)*(r-mid))/)*D[k]);

        Beg[k<<]+=Beg[k],Beg[k<<|]+=Beg[k]+(mid+-l)*D[k];

        D[k<<]+=D[k],D[k<<|]+=D[k];

        Beg[k]=D[k]=;

        return;

    }

    inline void Modify(int k,int l,int r,int x,int y,int be,int d){

        if(x<=l&&r<=y){

            Ans[k]+=((r-l+)*be)+(((((l+r)*(r-l+))/)-(x*(r-l+)))*d);

            Beg[k]+=(be+(l-x)*d);

            D[k]+=d;

            return;

        }

        pushdown(k,l,r);

        int mid=l+r>>;

        if(x<=mid) Modify(k<<,l,mid,x,y,be,d);

        if(mid<y) Modify(k<<|,mid+,r,x,y,be,d);

        Ans[k]=Ans[k<<]+Ans[k<<|];

        return;

    }

    inline int Query(int k,int l,int r,int x,int y){

        if(x<=l&&r<=y) return Ans[k];

        pushdown(k,l,r);

        int mid=l+r>>,res=;

        if(x<=mid) res+=Query(k<<,l,mid,x,y);

        if(mid<y) res+=Query(k<<|,mid+,r,x,y);

        Ans[k]=Ans[k<<]+Ans[k<<|];return res;

    }

    inline void add(int x,int y,int be,int d){

        qx[++tot]=x+n;qy[tot]=y+n;qbe[tot]=be,qd[tot]=d;

        Modify(,,*n,x+n,y+n,be,d);return;

    }

    inline int Q(int x,int y){

        return Query(,,*n,x+n,y+n);

    }

}segment1;

struct Segment2{

    int Ans[MAXN<<],tag[MAXN<<];

    int qx[MAXN],qy[MAXN],qw[MAXN],tot;

    inline void clear(){

        for(int i=;i<=tot;i++) Modify(,,*n,qx[i],qy[i],-qw[i]);

        tot=;

    }

    inline void pushdown(int k,int l,int r){

        if(!tag[k]) return;

        int mid=l+r>>;

        Ans[k<<]+=tag[k]*(mid-l+);Ans[k<<|]+=tag[k]*(r-mid);

        tag[k<<]+=tag[k],tag[k<<|]+=tag[k];

        tag[k]=;return;

    }

    inline void Modify(int k,int l,int r,int x,int y,int w){

        if(x<=l&&r<=y){

            tag[k]+=w;

            Ans[k]+=(r-l+)*w;return;

        }

        pushdown(k,l,r);

        int mid=l+r>>;

        if(x<=mid) Modify(k<<,l,mid,x,y,w);

        if(mid<y) Modify(k<<|,mid+,r,x,y,w);

        Ans[k]=Ans[k<<]+Ans[k<<|];return;

    }

    inline int Query(int k,int l,int r,int x,int y){

        if(x<=l&&r<=y) return Ans[k];

        pushdown(k,l,r);

        int mid=l+r>>,res=;

        if(x<=mid) res+=Query(k<<,l,mid,x,y);

        if(mid<y) res+=Query(k<<|,mid+,r,x,y);

        Ans[k]=Ans[k<<]+Ans[k<<|];return res;

    }

    inline void add(int x,int y,int w){

        qx[++tot]=x+n,qy[tot]=y+n,qw[tot]=w;

        Modify(,,*n,x+n,y+n,w);return;

    }

    inline int Q(int x,int y){

        return Query(,,*n,x+n,y+n);

    }

}segment2;

int Ans;

signed main(){

//    freopen("1.in","r",stdin);

    n=read();read();

    for(int i=;i<=n;i++) a[i]=read(),ve[a[i]].push_back(i);

    for(int i=;i<n;i++){

        int siz=ve[i].size();

        if(!siz) continue;

        int l=,r=-;

        segment1.clear();

        segment2.clear();

        segment1.add(,,,);

        segment2.add(,,);

        for(int j=;j<siz;j++){

            int u=ve[i][j];

            r=u-;

            if(j!=) l=ve[i][j-]+;

            else l=;

            if(l<=r){

                int L=-l+j*,R=-r+j*;

                if(L>R) swap(L,R);

                Ans+=segment2.Q(-n,L-)*(R-L+);

                Ans+=R*segment2.Q(L,R);

                Ans-=segment1.Q(L,R);

                segment1.add(L,R,L,);

                segment2.add(L,R,);

            }

            int Psum=-u+*(j+);

            Ans+=segment2.Q(-n,Psum-);

            segment1.add(Psum,Psum,Psum,);

            segment2.add(Psum,Psum,);

        }

        l=ve[i][siz-]+,r=n;

        if(l<=r){

            int L=-l+siz*,R=-r+siz*;

            if(L>R) swap(L,R);

            Ans+=segment2.Q(-n,L-)*(R-L+);

            Ans+=R*segment2.Q(L,R);;

            Ans-=segment1.Q(L,R);

            segment1.add(L,R,L,);

            segment2.add(L,R,);

        }

    }printf("%lld\n",Ans);return ;

}

巴特西

[LOJ 6253] Yazid 的新生舞会

$solution:$

最新文章

热门文章