（很久之前刷的题现在看起来十分陌生a）

题意：

给你一个长度为n的序列A，定义一个区间$[l,r]$是“新生舞会的”当且仅当该区间的众数次数严格大于$\frac{r-l+1}{2}$，求有多少子区间是“新生舞会的”。

$n\leq 500000,0\leq A_{i} \leq n-1$

 

题解：

关于区间众数的问题一般有一个套路：枚举众数后转换成区间求和问题。

考虑枚举众数k，若将序列中等于k的元素视作+1，其他视作-1，那么“新生舞会的“区间必然满足区间之和大于0。

问题变成了如何快速求出有多少个区间之和大于0的子区间。

考虑枚举右端点r并记录前缀和sum，那么要求的就是有多少左端点l满足$sum[l]<sum[r]$

直接用一个线段树维护即可。（树状数组也行，但跟后面的做法无关）

但是这样复杂度是$O(n^2)$的，无法通过本题。

注意到枚举众数后，序列中1的个数的总数是n。

容易发现连续的-1总数也为n，那么我们考虑将一段连续的-1一起考虑。

假设一段-1的起点是l，终点是r，sum值i出现了$cnt(i)$次，那么这段-1作为右端点时对答案的贡献之和就是

$\sum_{i=l}^{r}{\sum_{j=-inf}^{i-1}{cnt(j)}}$

$=\sum_{j=-inf}^{r-1}{\sum_{i=max(j+1,l)}^{r}{cnt(j)}}$

$=(r-l+1)\times{\sum_{i=-inf}^{l-1}{cnt(i)}}+\sum_{i=l}^{r}{(r-i)\times cnt(j)}$

那么直接维护两个线段树表示$cnt(i)$和$cnt(i)\times i$即可。

对于每段-1，统计答案后在其对应值域区间加，然后计算单个1的贡献即可。

复杂度$O(nlogn)$，比较难写，特别是清空线段树时需要注意clear标记的写法。

 

代码：

#include<bits/stdc++.h>
#define maxn 2000005
#define maxm 500005
#define inf 0x7fffffff
#define ll long long

using namespace std;
ll N,M,A[maxn],B[maxn],lz1[maxn<<2],lz2[maxn<<2]; 
ll s1[maxn<<2],s2[maxn<<2],vis[maxn];
vector<ll> pos[maxn]; 

inline ll read(){
    ll x=0,f=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*f;
}

inline void pushup1(ll k){s1[k]=s1[k<<1]+s1[k<<1|1];}
inline void pushdown1(ll len,ll k){
    if(k>=(maxn<<2)) return; 
    if(!lz1[k]) return;
    if(lz1[k]==-2){
        s1[k<<1]=s1[k<<1|1]=0;
        lz1[k<<1]=lz1[k<<1|1]=-2;
        lz1[k]=0; return;
    }
    if(lz1[k<<1]==-2) pushdown1(len+1>>1,k<<1),lz1[k<<1]=0,s1[k<<1]=0;
    if(lz1[k<<1|1]==-2) pushdown1(len>>1,k<<1|1),lz1[k<<1|1]=0,s1[k<<1|1]=0;
    lz1[k<<1]+=lz1[k],lz1[k<<1|1]+=lz1[k];
    s1[k<<1]+=lz1[k]*((len+1)>>1),s1[k<<1|1]+=lz1[k]*((len)>>1);
    lz1[k]=0; return;
}
inline ll qry1(ll x,ll y,ll l,ll r,ll k){
    pushdown1(r-l+1,k); 
    if(x<=l && r<=y) return s1[k];
    ll mid=(l+r)>>1,ans=0;
    if(x<=mid) ans+=qry1(x,y,l,mid,k<<1);
    if(y>mid) ans+=qry1(x,y,mid+1,r,k<<1|1);
    return ans;
}
inline void upd1(ll x,ll y,ll l,ll r,ll k){
    pushdown1(r-l+1,k); 
    if(x<=l && r<=y){s1[k]+=(r-l+1),lz1[k]++;return;}
    ll mid=(l+r)>>1;
    if(x<=mid) upd1(x,y,l,mid,k<<1);
    if(y>mid) upd1(x,y,mid+1,r,k<<1|1);
    pushup1(k); return;
} 

inline void pushup2(ll k){s2[k]=s2[k<<1]+s2[k<<1|1];}
inline ll dc(ll x,ll y){return (x+y)*(y-x+1)/2;}
inline void pushdown2(ll l,ll r,ll k){
    if(k>=(maxn<<2)) return;
    if(!lz2[k]) return;
    if(lz2[k]==-2){
        s2[k<<1]=s2[k<<1|1]=0;
        lz2[k<<1]=lz2[k<<1|1]=-2;
        lz2[k]=0; return;
    }
    ll mid=(l+r)>>1;
    if(lz2[k<<1]==-2) pushdown2(l,mid,k<<1),lz2[k<<1]=0,s2[k<<1]=0;
    if(lz2[k<<1|1]==-2) pushdown2(mid+1,r,k<<1|1),lz2[k<<1|1]=0,s2[k<<1|1]=0; 
    lz2[k<<1]+=lz2[k],lz2[k<<1|1]+=lz2[k];
    s2[k<<1]+=lz2[k]*dc(l,mid),s2[k<<1|1]+=lz2[k]*dc(mid+1,r);
    lz2[k]=0; return;
}
inline ll qry2(ll x,ll y,ll l,ll r,ll k){
    pushdown2(l,r,k);
    if(x<=l && r<=y) return s2[k];
    ll mid=(l+r)>>1,ans=0;
    if(x<=mid) ans+=qry2(x,y,l,mid,k<<1);
    if(y>mid) ans+=qry2(x,y,mid+1,r,k<<1|1);
    return ans;
}
inline void upd2(ll x,ll y,ll l,ll r,ll k){
    pushdown2(l,r,k); 
    if(x<=l && r<=y){s2[k]+=dc(l,r),lz2[k]++;return;}
    ll mid=(l+r)>>1;
    if(x<=mid) upd2(x,y,l,mid,k<<1);
    if(y>mid) upd2(x,y,mid+1,r,k<<1|1);
    pushup2(k); return;
}

inline ll calc(ll x){
    ll ans=0,sum=N; pos[x].push_back(N+1);
    for(ll i=0;i<pos[x].size()-1;i++){
        ll lp=pos[x][i]+1,rp=pos[x][i+1]-1; 
        if(pos[x][i]!=0) sum++;
        ans+=qry1(1,sum-1,1,M,1); 
        ll tp=qry1(1,sum-1,1,M,1);
        upd1(sum,sum,1,M,1),upd2(sum,sum,1,M,1);
        if(lp<=rp){
            ll l=sum-(rp-lp+1),r=sum-1; sum-=(rp-lp+1);
            ll num=(l==1)?0:(qry1(1,l-1,1,M,1)*(r-l+1))+((r)*qry1(l,r-1,1,M,1)-qry2(l,r-1,1,M,1));
            ans+=num,upd1(l,r,1,M,1),upd2(l,r,1,M,1);
        }
    }
    s1[1]=s2[1]=0,lz1[1]=lz2[1]=-2;
    return ans;
}

int main(){ 
    N=read(),M=(N<<1|1); ll not_used=read();
    for(ll i=1;i<=N;i++) A[i]=read()+1;
    for(ll i=1;i<=N;i++) 
        if(!vis[A[i]]) vis[A[i]]=1,pos[A[i]].push_back(0);
    for(ll i=1;i<=N;i++) pos[A[i]].push_back(i);
    memset(vis,0,sizeof(vis)); ll ans=0;
    for(ll i=1;i<=N;i++) 
        if(!vis[A[i]]) vis[A[i]]=1,ans+=calc(A[i]);
    printf("%lld\n",ans); 
    return 0;
}

Yazid