NC14502. Yazid 的新生舞会
描述
这道题是没有舞伴的Yazid用新生舞会的时间出的。
Yazid有一个长度为n的序列A，下标从1至n。显然地，这个序列共有个子区间。
对于任意一个子区间[l,r]，如果该子区间内的众数在该子区间的出现次数严格大于（即该子区间长度的一半），那么Yazid就说这个子区间是“新生舞会的”。
所谓众数，即为该子区间内出现次数最多的数。特别地，如果出现次数最多的数有多个，我们规定值最小的数为众数。
现在，Yazid想知道，共有多少个子区间是“新生舞会的”。
输入描述
第一行2个用空格隔开的非负整数n,type，表示序列的长度和数据类型。数据类型的作用将在备注中说明。第二行n个用空格隔开的非负整数，依次为A1,A2,... ,An，描述这个序列。
输出描述
输出一行一个整数，表示答案。
示例1
输入:
5 0 1 1 2 2 3
输出:
10
说明:
“新生舞会的”子区间有[1,1],[1,2],[1,3],[2,2],[2,4],[3,3],[3,4],[3,5],[4,4],[5,5]共10个。C++ 解法, 执行用时: 535ms, 内存消耗: 30864K, 提交时间: 2022-05-04 20:06:07
#include<bits/stdc++.h>
#define lowbit(x) (x&-x)
using namespace std;
const int N=5e5+10,P=N;
typedef long long LL;
LL t1[N*2],t2[N*2],t3[N*2];
vector<int>num[N];
int n,type;
LL res;
void add(int x,int v)
{
for(int i=x;i<N*2;i+=lowbit(i))
t1[i]+=v,t2[i]+=(LL)x*v,t3[i]+=(LL)x*x*v;
}
LL query(int x)
{
LL res=0;
for(int i=x;i;i-=lowbit(i))
res+=(LL)t1[i]*(x+1)*(x+2)-(LL)t2[i]*(2*x+3)+t3[i];
return res>>1;
}
int main()
{
cin>>n>>type;
for(int i=1;i<=n;i++)
{ int x;
cin>>x;
num[x+1].push_back(i);
}
for(int i=1;i<=n;i++)
{ int sum=0,last=0;
if(num[i].empty())continue;
num[i].push_back(n+1);
for(auto p:num[i])
{
int l=2*sum-p+1+P;
int r=2*sum-last+P;
res+=query(r-1)-query(l-2);
add(l,1),add(r+1,-1);
last=p;
sum++;
}
sum=0,last=0;
for(auto p:num[i])
{
int l=2*sum-p+1+P;
int r=2*sum-last+P;
add(l,-1),add(r+1,1);
last=p;
sum++;
}
}
cout<<res<<endl;
}