【BZOJ5110】[CodePlus2017]Yazid 的新生舞会
Description
Yazid有一个长度为n的序列A，下标从1至n。显然地，这个序列共有n(n+1)/2个子区间。对于任意一个子区间[l,r]，如果该子区间内的众数在该子区间的出现次数严格大于(r?l+1)/2（即该子区间长度的一半），那么Yazid就说这个子区间是"新生舞会的"。所谓众数，即为该子区间内出现次数最多的数。特别地，如果出现次数最多的数有多个，我们规定值最小的数为众数。现在，Yazid想知道，共有多少个子区间是"新生舞会的"
Input
第一行2个用空格隔开的非负整数n,type，表示序列的长度和数据类型。数据类型的作用将在子任务中说明。
第二行n个用空格隔开的非负整数，依次为A1,A2,...,An，描述这个序列。
N<=500000,0<=Type<=3
对于所有数据，保证 0 ≤ Ai ≤ n ? 1。
对于 type = 0 的数据，没有任何特殊约定。
对于 type = 1 的数据，保证 Ai ∈ {0, 1}。
对于 type = 2 的数据，保证序列 A 的众数在整个序列中的出现次数不超过 15。
对于 type = 3 的数据，保证 Ai ≤ 7。
Output
输出一行一个整数，表示答案。
Sample Input
5 0
1 1 2 2 3
1 1 2 2 3
Sample Output
10
//"新生舞会的" 子区间有 [1, 1], [1, 2], [1, 3], [2, 2], [2, 4], [3, 3],
[3, 4], [3, 5], [4, 4], [5, 5]共 10 个。
//"新生舞会的" 子区间有 [1, 1], [1, 2], [1, 3], [2, 2], [2, 4], [3, 3],
[3, 4], [3, 5], [4, 4], [5, 5]共 10 个。
题解：考虑枚举众数，我们用vector维护每种数的所有出现位置，然后我们将这个数的所有位置看成+1，其它位置看成-1，于是答案就变成了求多少区间的和>0。
我们考虑将所有连续的-1合并到一起，这样的话连续-1的个数就不会超过+1的个数+1了，然后枚举右端点。因为区间和可以看成前缀相减，所以我们用s[i]表示前缀和，那么我们要统计的就是左面有多少s[j]<s[i]，自然想到用线段树来维护有多少个数的s值等于一个数。那么，对于一个+1，我们可以用简单的线段树区间求和搞定；对于一段-1，这段区间对答案的贡献就是$\sum\limits_{i=1}^{r-l+1}\sum\limits_{j=-\infty}^{s[l-1]-1-i}cnt[j]$（cnt表示有多少个数的s等于j）。发现这个东西可以用线段树维护cnt[i]和i*cnt[i]来实现，于是此题就做完了。
但是由于BZ太慢了，所以搞了若干个卡常小优化才过~
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#define lson x<<1
#define rson x<<1|1
using namespace std;
const int maxn=500010;
typedef long long ll;
ll ans;
int n;
vector<int> p[maxn];
int s1[maxn<<3],z1[maxn<<3];
ll s2[maxn<<3],z2[maxn<<3];
int tag[maxn<<3];
bool clr[maxn<<3];
inline void pushdown(int x)
{
if(clr[x]) clr[lson]=clr[rson]=1,s1[lson]=s1[rson]=s2[lson]=s2[rson]=tag[lson]=tag[rson]=clr[x]=0;
if(tag[x]) s1[lson]+=z1[lson]*tag[x],s1[rson]+=z1[rson]*tag[x],s2[lson]+=z2[lson]*tag[x],s2[rson]+=z2[rson]*tag[x],tag[lson]+=tag[x],tag[rson]+=tag[x],tag[x]=0;
}
void build(int l,int r,int x)
{
if(l==r)
{
z1[x]=1,z2[x]=l;
return ;
}
int mid=(l+r)>>1;
build(l,mid,lson),build(mid+1,r,rson);
z1[x]=z1[lson]+z1[rson],z2[x]=z2[lson]+z2[rson];
}
void updata(int l,int r,int x,int a,int b)
{
if(a<=l&&r<=b)
{
s1[x]+=z1[x],s2[x]+=z2[x],tag[x]++;
return ;
}
pushdown(x);
int mid=(l+r)>>1;
if(a<=mid) updata(l,mid,lson,a,b);
if(b>mid) updata(mid+1,r,rson,a,b);
s1[x]=s1[lson]+s1[rson],s2[x]=s2[lson]+s2[rson];
}
int query1(int l,int r,int x,int a,int b)
{
if(a<=l&&r<=b) return s1[x];
pushdown(x);
int mid=(l+r)>>1;
if(b<=mid) return query1(l,mid,lson,a,b);
if(a>mid) return query1(mid+1,r,rson,a,b);
return query1(l,mid,lson,a,b)+query1(mid+1,r,rson,a,b);
}
ll query2(int l,int r,int x,int a,int b)
{
if(a<=l&&r<=b) return s2[x];
pushdown(x);
int mid=(l+r)>>1;
if(b<=mid) return query2(l,mid,lson,a,b);
if(a>mid) return query2(mid+1,r,rson,a,b);
return query2(l,mid,lson,a,b)+query2(mid+1,r,rson,a,b);
}
inline char nc()
{
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int rd()
{
int ret=0,f=1; char gc=nc();
while(!isdigit(gc)) {if(gc=='-') f=-f; gc=nc();}
while(isdigit(gc)) ret=ret*10+(gc^'0'),gc=nc();
return ret*f;
}
int main()
{
n=rd(),rd();
register int i,j,l,r,sum;
for(i=1;i<=n;i++) j=rd(),p[j].push_back(i);
build(-n,n,1);
for(i=0;i<n;i++) if(p[i].size())
{
s1[1]=s2[1]=tag[1]=sum=0,clr[1]=1;
p[i].push_back(n+1);
updata(-n,n,1,0,0);
for(j=0;j<(int)p[i].size();j++)
{
if((!j&&p[i][j]>1)||(j&&p[i][j]>p[i][j-1]+1))
{
l=(!j)?1:(p[i][j-1]+1),r=p[i][j]-1;
if(j) ans+=query1(-n,n,1,-n,sum-1)*(r-l+1)-query2(-n,n,1,sum-(r-l+1),sum-1)+query1(-n,n,1,sum-(r-l+1),sum-1)*(sum-1-(r-l+1));
updata(-n,n,1,sum-(r-l+1),sum-1);
sum-=(r-l+1);
}
if(j!=(int)p[i].size()-1) sum++,ans+=query1(-n,n,1,-n,sum-1),updata(-n,n,1,sum,sum);
}
}
printf("%lld",ans);
return 0;
}//5 0 1 1 0 1 1