[BZOJ5110]Yazid 的新生舞会

题目大意

有一个长度为n的序列A，下标从1至n。显然地，这个序列共有 n(n+1)2 个子区间。问有多少个子区间[l,r]，对于这个子区间[l,r]，如果该子区间内的众数在该子区间的出现次数严格大于 r−l+12 （即该子区间长度的一半）。

Solution

对于序列中的每一种数分别考虑。对于每一种数x，如果有数组a,a[i]=1表示下标为i的位置上是x,a[i]=0表示下标为i的位置上不是x。
对a数组求前缀和得到前缀和数组S
对于数x来说，一个合法的区间当且仅当 S[r]−S[l−1]>r−l+12 ,即 S[r]−S[l]>r−l2 。(用l-1替换l)
就得到了2S[r]-r>2S[l]-l。令b[i]=2S[i]-i。答案就成了求b[i]的顺序对个数。有一种经典的线段树做法。
然而数的种数有很多，如果対没种数都暴力维护所有b[i],复杂度会达到 O(n2lgn)

考虑每种数，它的a[i]=0/1。只有这个数存在的位置上，S数组才会发生改变。所以b[i]被分成了许多段等差数列，段数为序列中这种数的个数+1。对于每一段等差数列，是可以同时处理的。
如：对于一段等差数列[l..r] (不是区间，而是b[i]的权值)，只要计算[-n..l-1],[-n..l],[-n..l+1],…,[-n..r-1]的所有值的和。对于一个b[i]，维护两种值：出现次数p[b[i]]以及p[b[i]]*(n-b[i])。这样，[l..r]的答案= ∑ri=l[p[i]∗(n−i)]−∑ri=lp[i]∗(n−r)+∑l=1i=−np[i]∗(r−l+1) 。分别用线段树维护。
复杂度变成了 O(段数lgn)=O(nlgn) 。

另外要注意一个细节，就是在枚举另外一种数时要清空线段树，不能用memset，要在线段数的根部打标记。

Code

#include<cstdio>
#include<algorithm>
typedef long long ll;
using namespace std;
int tag1[2000010],tag2[2000010],pos[2000010],flag[500010],Next[500010],n,a[500010],Tag1[2000010],Tag2[2000010];
ll tree1[2000010],tree2[2000010];
inline void pushdown1(int t,int l,int r)
{
if (Tag1[t]>-1)
{
tree1[t<<1]=tree1[t<<1|1]=tag1[t<<1]=tag1[t<<1|1]=0;
Tag1[t<<1]=Tag1[t<<1|1]=0;
Tag1[t]=-1;
}
if (tag1[t])
{
tag1[t<<1]+=tag1[t];
tag1[t<<1|1]+=tag1[t];
int mid=(l+r)>>1;
int Ll=n-mid,rr=n-l;
tree1[t<<1]+=(ll)tag1[t]*(ll)(Ll+rr)*(ll)(rr-Ll+1)/2;
Ll=n-r,rr=n-mid-1;
tree1[t<<1|1]+=(ll)tag1[t]*(ll)(Ll+rr)*(ll)(rr-Ll+1)/2;
tag1[t]=0;
}
}
inline void pushdown2(int t,int l,int r)
{
if (Tag2[t]>-1)
{
tree2[t<<1]=tree2[t<<1|1]=tag2[t<<1]=tag2[t<<1|1]=0;
Tag2[t<<1]=Tag2[t<<1|1]=0;
Tag2[t]=-1;
}
if (tag2[t])
{
int mid=(l+r)>>1;
tag2[t<<1]+=tag2[t];
tag2[t<<1|1]+=tag2[t];
tree2[t<<1]+=(ll)tag2[t]*(mid-l+1);
tree2[t<<1|1]+=(ll)tag2[t]*(r-mid);
tag2[t]=0;
}
}
void modify1(int l,int r,int x,int y,int t)
{
if (l==x&&y==r)
{
tag1[t]++;
int Ll=n-r,rr=n-l;
tree1[t]+=(ll)(Ll+rr)*(ll)(rr-Ll+1)/2;
return;
}
pushdown1(t,l,r);
int mid=(l+r)>>1;
if (y<=mid) modify1(l,mid,x,y,t<<1);
else if (x>mid) modify1(mid+1,r,x,y,t<<1|1);
else modify1(l,mid,x,mid,t<<1),modify1(mid+1,r,mid+1,y,t<<1|1);
tree1[t]=tree1[t<<1]+tree1[t<<1|1];
}
void modify2(int l,int r,int x,int y,int t)
{
if (l==x&&y==r)
{
tag2[t]++;
tree2[t]+=r-l+1;
return;
}
pushdown2(t,l,r);
int mid=(l+r)>>1;
if (y<=mid) modify2(l,mid,x,y,t<<1);
else if (x>mid) modify2(mid+1,r,x,y,t<<1|1);
else modify2(l,mid,x,mid,t<<1),modify2(mid+1,r,mid+1,y,t<<1|1);
tree2[t]=tree2[t<<1]+tree2[t<<1|1];
}
ll query1(int l,int r,int x,int y,int t)
{
if (l==x&&y==r) return tree1[t];
pushdown1(t,l,r);
int mid=(l+r)>>1;
if (y<=mid) return query1(l,mid,x,y,t<<1);
if (x>mid) return query1(mid+1,r,x,y,t<<1|1);
return query1(l,mid,x,mid,t<<1)+query1(mid+1,r,mid+1,y,t<<1|1);
}
ll query2(int l,int r,int x,int y,int t)
{
if (l==x&&y==r) return tree2[t];
pushdown2(t,l,r);
int mid=(l+r)>>1;
if (y<=mid) return query2(l,mid,x,y,t<<1);
if (x>mid) return query2(mid+1,r,x,y,t<<1|1);
return query2(l,mid,x,mid,t<<1)+query2(mid+1,r,mid+1,y,t<<1|1);
}
int main()
{
int type;
scanf("%d%d",&n,&type);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
for (int i=n;i;i--)
{
Next[i]=pos[a[i]];
pos[a[i]]=i;
}
ll ans=0;
for (int i=1;i<=n;i++)
{
if (flag[a[i]]) continue;
flag[a[i]]=1;
int Pos=i,s=0;
Tag1[1]=Tag2[1]=tag1[1]=tag2[1]=tree1[1]=tree2[1]=0;
modify1(-n,n,1-Pos,0,1);
modify2(-n,n,1-Pos,0,1);
while (Pos&&Pos<=n)
{
int p1=Next[Pos];
if (!p1) p1=n+1;
p1--;
s++;
int r=(s<<1)-Pos,l=(s<<1)-p1;
ans+=query1(-n,n,l,r,1)-query2(-n,n,l,r,1)*(n-r);
if (l>-n) ans+=query2(-n,n,-n,l-1,1)*(r-l+1);
modify1(-n,n,l,r,1);
modify2(-n,n,l,r,1);
Pos=p1+1;
}
}
printf("%lldn",ans);
return 0;
}
//代码那么丑，我果然比较菜。

最后

以上就是平常方盒为你收集整理的[BZOJ5110]Yazid 的新生舞会的全部内容，希望文章能够帮你解决[BZOJ5110]Yazid 的新生舞会所遇到的程序开发问题。

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