bzoj 5110 Yazid的新生舞会

题目大意：

一个数列，求有多少个区间$[l,r]$满足该区间的众数出现次数大于$\lceil \frac{r-l}{2} \rceil$

思路：

对于一个区间满足条件的众数明显是唯一的 所以设该数的前缀和数组为$S$

则一个区间$(l,r]$满足条件满足$2 \times (S_r-S_l)>(r-l)$ 移项后得到$2 \times S_r-r>2 \times S_l-l$

则对于$2 \times S_i-i$建立函数发现该函数由斜率为$\pm 1$组成

所有函数的关键点总数为$n$ 对于$y$轴建立权值线段树 发现中间连续的一段的贡献为一次函数

写一波一次函数即可

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define rep(i,s,t) for(register int i=(s),i__end=(t);i<=i__end;++i)
#define dwn(i,s,t) for(register int i=(s),i__end=(t);i>=i__end;++i)
#define ren(x) for(register int i=fst[x];i;i=nxt[i])
#define pb(a,x) vec[a].push_back(x);
#define ll long long
#define inf 2139062143
#define MAXN 1001000
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,N,tp,g[MAXN],hsh[MAXN],m,tagk[MAXN<<2],tagb[MAXN<<2];
ll sum[MAXN<<2],ans;
vector <int> vec[MAXN];
inline ll calc(ll k,ll b,int x,int y) {return ((ll)((ll)k*y+k*x+2*b)*((ll)y-x+1))/2;}
void pshd(int k,int l,int r,int mid)
{
    sum[k<<1]+=calc(tagk[k],tagb[k],l,mid);
    sum[k<<1|1]+=calc(tagk[k],tagb[k],mid+1,r);
    tagk[k<<1]+=tagk[k],tagk[k<<1|1]+=tagk[k],tagb[k<<1]+=tagb[k],tagb[k<<1|1]+=tagb[k];
    tagk[k]=tagb[k]=0LL;
}
void mdf(int k,int l,int r,int a,int b,ll d,ll t)
{
    if(l==a&&r==b) {tagb[k]+=t,tagk[k]+=d,sum[k]+=calc(d,t,l,r);return ;}
    int mid=l+r>>1;if(tagb[k]!=0||tagk[k]!=0) pshd(k,l,r,mid);
    if(b<=mid) mdf(k<<1,l,mid,a,b,d,t);else if(a>mid) mdf(k<<1|1,mid+1,r,a,b,d,t);
    else {mdf(k<<1,l,mid,a,mid,d,t);mdf(k<<1|1,mid+1,r,mid+1,b,d,t);}
    sum[k]=sum[k<<1]+sum[k<<1|1];
}
ll query(int k,int l,int r,int a,int b)
{
    if(l==a&&r==b) return sum[k];
    int mid=l+r>>1;if(tagb[k]!=0||tagk[k]!=0) pshd(k,l,r,mid);
    if(b<=mid) return query(k<<1,l,mid,a,b);
    else if(a>mid) return query(k<<1|1,mid+1,r,a,b);
    else return query(k<<1,l,mid,a,mid)+query(k<<1|1,mid+1,r,mid+1,b);
}
void work(int x)
{
    int t,las=0,pos;rep(i,1,vec[x].size()-1)
    {
        t=vec[x][i],pos=las-(t-vec[x][i-1])+1;
        ans+=query(1,0,N,pos+n,las+n);
        mdf(1,0,N,pos+n+1,las+n+1,1,-pos-n);
        if(las+n+2<=N) mdf(1,0,N,las+n+2,N,0,las-pos+1);
        las=pos+1;
    }
    las=0;rep(i,1,vec[x].size()-1)
    {
        t=vec[x][i],pos=las-(t-vec[x][i-1])+1;
        mdf(1,0,N,pos+n+1,las+n+1,-1,pos+n);
        if(las+n+2<=N) mdf(1,0,N,las+n+2,N,0,pos-las-1);
        las=pos+1;
    }
}
int main()
{
    n=read(),N=(n<<1)+5,tp=read();rep(i,1,n) {g[i]=read();if(!hsh[g[i]]) hsh[g[i]]=++m;}
    rep(i,1,m) pb(i,0);rep(i,1,n) pb(hsh[g[i]],i);rep(i,1,m) pb(i,n+1);
    rep(i,1,m) work(i);printf("%lld\n",ans);
}