Yazid 的新生舞会------线段树+思维

大佬链接
原题链接、
这题确实有一点找不到头脑，一开始也是在想应该是分数字的种，然后对每一种种类进行贡献的计算，但是就不知道怎么计算某种数字的贡献了，还是参考了大佬的代码，才ac了。

因为众数，用vector维护每种数的所有出现位置，然后我们将这个数的所有位置看成+1，其它位置看成-1，于是答案就变成了求多少区间的和>0。

关于优化，我们考虑将所有连续的-1合并到一起，这样的话连续-1的个数就不会超过+1的个数+1了。因为区间和可以看成前缀相减，所以我们用s[i]表示前缀和，那么我们要统计的就是左面有多少s[j]<s[i]，自然想到用线段树来维护有多少个数的s值小于s[i]的个数。

可以创建一颗（-n到n）范围的一颗线段树，用于储存前缀和出现的次数。
然后我们的一段数字，是由一段-1，一段1，这样相互连接而成的，所以，接下来，考虑每一段对答案的贡献。
如果是一段1，可以看成是一个1，然后下一段仍然是一个1，所以我们要算的是一个1对答案的贡献。设这个1的位置是i，那么我们要算的就是s[i]-1>=s[x]，也就是在i之前，有多少个前缀和是小于等于s[i]-1。

如果是一段-1，有点难用文字表达，，，字丑，hhh

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define lson k<<1,l,mid
#define rson k<<1|1,mid+1,r
const int MX=5e5+9;
using namespace std;
int n,m,t1[MX<<3],t2[MX<<3],s1[MX<<3],s2[MX<<3],tag[MX<<3],clr[MX<<3];
vector<int> vec[MX];
void pushdown(int k){
if( clr[k] ){
tag[k<<1]=tag[k<<1|1]=0;
clr[k<<1]=clr[k<<1|1]=clr[k],clr[k]=0;
s1[k<<1]=s1[k<<1|1]=0;
s2[k<<1]=s2[k<<1|1]=0;
}
if( tag[k] ){
tag[k<<1]+=tag[k];
tag[k<<1|1]+=tag[k];
s1[k<<1]+=tag[k]*t1[k<<1],s1[k<<1|1]+=tag[k]*t1[k<<1|1];
s2[k<<1]+=tag[k]*t2[k<<1],s2[k<<1|1]+=tag[k]*t2[k<<1|1];
tag[k]=0;
}
}
void build(int k,int l,int r){
tag[k]=clr[k]=0;
if( l==r ){
t1[k]=1;
t2[k]=l;
return ;
}
int mid=(l+r)>>1;
build(lson);
build(rson);
t1[k]=t1[k<<1]+t1[k<<1|1];
t2[k]=t2[k<<1]+t2[k<<1|1];
}
void update(int k,int l,int r,int L,int R){
if(
L<=l && r<=R ){
s1[k]+=t1[k];
s2[k]+=t2[k];
tag[k]++;
return ;
}
pushdown(k);
int mid=(l+r)>>1;
if( L<=mid )
update(lson,L,R);
if( mid<R )
update(rson,L,R);
s1[k]=s1[k<<1]+s1[k<<1|1];
s2[k]=s2[k<<1]+s2[k<<1|1];
}
int que1(int k,int l,int r,int L,int R){
if( L<=l && r<=R )
return s1[k];
pushdown(k);
int mid=(l+r)>>1,ans=0;
if( L<=mid )
ans+=que1(lson,L,R);
if( mid<R )
ans+=que1(rson,L,R);
return ans;
}
int que2(int k,int l,int r,int L,int R){
if( L<=l && r<=R )
return s2[k];
pushdown(k);
int mid=(l+r)>>1,ans=0;
if( L<=mid )
ans+=que2(lson,L,R);
if( mid<R )
ans+=que2(rson,L,R);
return ans;
}
int main()
{
// freopen("input.txt","r",stdin);
scanf("%d %d",&n,&m);
for( int i=1,j ; i<=n ; i++ ){
scanf("%d",&j);
vec[j].push_back(i);
}
build(1,-n,n);
long long ans=0;
int sum=0;
for( int i=0 ; i<n ; i++ ){
if( vec[i].size()!=0 ){
clr[1]=1,tag[1]=s1[1]=s2[1]=0,sum=0;
update(1,-n,n,0,0);
vec[i].push_back(n+1);
for( int j=0 ; j<vec[i].size() ; j++ ){
if( (!j&&vec[i][j]!=1) || (j&&vec[i][j]>vec[i][j]-1) ){
int l=(j==0)?1:vec[i][j-1]+1;
int r=vec[i][j]-1;
ans+=que1(1,-n,n,-n,sum-1)*(r-l+1)-que2(1,-n,n,sum-(r-l+1),sum-1)+que1(1,-n,n,sum-(r-l+1),sum-1)*(sum-1-(r-l+1));
// 这是那个用图计算的代码表达式
update(1,-n,n,sum-(r-l+1),sum-1);
sum-=(r-l+1);
}
if( j!=vec[i].size()-1 ){
ans+=que1(1,-n,n,-n,sum);
sum++;
update(1,-n,n,sum,sum);
}
}
}
}
printf("%lldn",ans);
return 0;
}

最后

以上就是文静铃铛为你收集整理的Yazid 的新生舞会------线段树+思维的全部内容，希望文章能够帮你解决Yazid 的新生舞会------线段树+思维所遇到的程序开发问题。

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