Description

Yazid有一个长度为n的序列A，下标从1至n。显然地，这个序列共有n(n+1)/2个子区间。对于任意一个子区间[l,r]
，如果该子区间内的众数在该子区间的出现次数严格大于(r?l+1)/2（即该子区间长度的一半），那么Yazid就说这
个子区间是"新生舞会的"。所谓众数，即为该子区间内出现次数最多的数。特别地，如果出现次数最多的数有多个
，我们规定值最小的数为众数。现在，Yazid想知道，共有多少个子区间是"新生舞会的"

N<=500000,0<=Type<=3
对于所有数据，保证 0 ≤ Ai ≤ n ? 1。
对于 type = 0 的数据，没有任何特殊约定。
对于 type = 1 的数据，保证 Ai ∈ {0, 1}。
对于 type = 2 的数据，保证序列 A 的众数在整个序列中的出现次数不超过 15。
对于 type = 3 的数据，保证 Ai ≤ 7。

Solution

想起了今年做cp，体验极差

一个暴力的做法是枚举众数，把众数看作1，其余看作-1，合法区间就是和>0的区间数量，我们枚举右端点对前缀和开权值线段树就可以了
考虑怎么优化这个暴力。对于一整段的-1我们合并贡献。记-1所在区间为[l,r]，那么右端点在l时查询值域在[-n,sum-2]，在l+1时是[-n,sum-3]，在i时是[-n,sum-1-(i-l+1)]，并且[-n,sum-1-(r-l+1)]这一段会被算(r-l+1)次。注意到这等价于求一个梯形区域，我们线段树维护rec[x]和rec[x]*x就可以求了

Code

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
#define fi first
#define se second
typedef long long LL;
typedef std:: pair <LL,LL> pair;
const int N=1000010;
std:: vector <int> vec[N];
LL sum1[N<<2],sum2[N<<2];
LL tag[N<<2];
bool clr[N<<2];
pair operator +(pair a,pair b) {
return pair(a.fi+b.fi,a.se+b.se);
}
int read() {
int x=0,v=1; char ch=getchar();
for (;ch<'0'||ch>'9';v=(ch=='-')?(-1):(v),ch=getchar());
for (;ch<='9'&&ch>='0';x=x*10+ch-'0',ch=getchar());
return x*v;
}
void push_down(int now,int tl,int tr,int mid) {
if (clr[now]) {
clr[now]=0;
clr[now<<1]=clr[now<<1|1]=1;
sum1[now<<1]=sum2[now<<1]=tag[now<<1]=0;
sum1[now<<1|1]=sum2[now<<1|1]=tag[now<<1|1]=0;
}
if (tag[now]) {
LL w=tag[now]; tag[now]=0;
tag[now<<1]+=w; tag[now<<1|1]+=w;
sum1[now<<1]+=w*(mid-tl+1);
sum1[now<<1|1]+=w*(tr-mid);
sum2[now<<1]+=w*(tl+mid)*(mid-tl+1)/2;
sum2[now<<1|1]+=w*(mid+1+tr)*(tr-mid)/2;
}
}
void modify(int now,int tl,int tr,int l,int r,LL v) {
if (r<l) return ;
if (tl>=l&&tr<=r) {
sum1[now]+=v*(r-l+1);
sum2[now]+=v*(r+l)*(r-l+1)/2;
tag[now]+=v;
return ;
}
int mid=(tl+tr)>>1;
push_down(now,tl,tr,mid);
modify(now<<1,tl,mid,l,std:: min(r,mid),v);
modify(now<<1|1,mid+1,tr,std:: max(mid+1,l),r,v);
sum1[now]=sum1[now<<1]+sum1[now<<1|1];
sum2[now]=sum2[now<<1]+sum2[now<<1|1];
}
pair query(int now,int tl,int tr,int l,int r) {
if (r<l) return pair(0,0);
if (tl>=l&&tr<=r) return pair(sum1[now],sum2[now]);
int mid=(tl+tr)>>1;
push_down(now,tl,tr,mid);
pair qx=query(now<<1,tl,mid,l,std:: min(r,mid));
pair qy=query(now<<1|1,mid+1,tr,std:: max(mid+1,l),r);
return qx+qy;
}
int main(void) {
freopen("data.in","r",stdin);
freopen("myp.out","w",stdout);
int n=read(); read();
rep(i,1,n) {
int x=read();
vec[x].push_back(i);
}
LL ans=0;
for (int now=0;now<n;++now) {
if (!vec[now].size()) continue;
clr[1]=1; sum1[1]=sum2[1]=tag[1]=0;
modify(1,-n,n,0,0,1);
vec[now].push_back(n+1);
for (int sum=0,L=1,i=0;i<vec[now].size();++i) {
int R=vec[now][i]-1;
if (L<=R) {
ans+=query(1,-n,n,-n,sum-1).fi*(1LL*R-L+1);
ans-=query(1,-n,n,sum-(R-L+1),sum-1).se;
ans+=query(1,-n,n,sum-(R-L+1),sum-1).fi*(1LL*sum-1-(R-L+1));
modify(1,-n,n,sum-(R-L+1),sum-1,1);
sum-=(R-L+1);
}
L=vec[now][i]+1;
if (i+1!=vec[now].size()) {
sum++,ans+=query(1,-n,n,-n,sum-1).fi;
modify(1,-n,n,sum,sum,1);
}
}
}
printf("%lld", ans);
return 0;
}

最后

以上就是爱笑发夹为你收集整理的bzoj5110 [CodePlus2017]Yazid 的新生舞会 线段树DescriptionSolutionCode的全部内容，希望文章能够帮你解决bzoj5110 [CodePlus2017]Yazid 的新生舞会 线段树DescriptionSolutionCode所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。