[BZOJ5110][CODE+ DIV1 T4]Yazid 的新生舞会 线段树

题解网上太多了
推荐官方题解https://cp.thusaac.org/contests/5a131456aa5ec762c97f6231

#include <bits/stdc++.h>
#define ll long long
#define lf double
#define E complex<lf>
#define inf 0x3f3f3f3f
#define eps 1e-8
#define pa pair<int,int>
#define pb push_back
#define ms(x,y) memset(x,y,sizeof(x))
#define l(x) (x<<1)
#define r(x) (x<<1|1)
#define mod 1000000007
#define N 500010
using namespace std;
inline ll read() {
ll x=0,f=1;char c=getchar();
while (c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();
while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
return x*f;
}
int n,a[N];
vector <int> p[N];
bool clr[N<<2];//每次枚举一个新的众数时清空线段树的标记 
int v1[N<<2],v2[N<<2],t[N<<2]; //v1区间个数 v2区间i总和 t表示这个区间被加了多少次的标记 
ll sum1[N<<2],sum2[N<<2];//sum1 区间cnt[i]和 sum2区间i*cnt[i]和 
inline void pushdown(int x) {
if (clr[x]) clr[l(x)]=clr[r(x)]=1,sum1[l(x)]=sum1[r(x)]=sum2[l(x)]=sum2[r(x)]=t[l(x)]=t[r(x)]=clr[x]=0;
if (t[x])
sum1[l(x)]+=1ll*v1[l(x)]*t[x],sum1[r(x)]+=1ll*v1[r(x)]*t[x],
sum2[l(x)]+=1ll*v2[l(x)]*t[x],sum2[r(x)]+=1ll*v2[r(x)]*t[x],
t[l(x)]+=t[x],t[r(x)]+=t[x],t[x]=0;
}
inline void build(int x,int l,int r) {
if (l==r) {v1[x]=1,v2[x]=l;return ;}
int mid=l+r>>1;
build(l(x),l,mid),build(r(x),mid+1,r);
v1[x]=v1[l(x)]+v1[r(x)];
v2[x]=v2[l(x)]+v2[r(x)];
}
inline void modify(int x,int l,int r,int ql,int qr) {
if (ql==l&&qr==r) {
t[x]++,sum1[x]+=v1[x],sum2[x]+=v2[x];
return ;
}
pushdown(x);
int mid=l+r>>1;
if (qr<=mid) modify(l(x),l,mid,ql,qr);
else if (ql>mid) modify(r(x),mid+1,r,ql,qr);
else modify(l(x),l,mid,ql,mid),modify(r(x),mid+1,r,mid+1,qr);
sum1[x]=sum1[l(x)]+sum1[r(x)],sum2[x]=sum2[l(x)]+sum2[r(x)];
}
inline ll query_sum1(int x,int l,int r,int ql,int qr) {//查询区间cnt[i] 
if (ql==l&&qr==r) return sum1[x];
int mid=l+r>>1;
pushdown(x);
if (qr<=mid) return query_sum1(l(x),l,mid,ql,qr);
else if (ql>mid) return query_sum1(r(x),mid+1,r,ql,qr);
else return query_sum1(l(x),l,mid,ql,mid)+query_sum1(r(x),mid+1,r,mid+1,qr);
}
inline ll query_sum2(int x,int l,int r,int ql,int qr) {//查询区间i*cnt[i]和
if (ql==l&&qr==r) return sum2[x];
int mid=l+r>>1;
pushdown(x);
if (qr<=mid) return query_sum2(l(x),l,mid,ql,qr);
else if (ql>mid) return query_sum2(r(x),mid+1,r,ql,qr);
else return query_sum2(l(x),l,mid,ql,mid)+query_sum2(r(x),mid+1,r,mid+1,qr);
}
int main() {
n=read(),read();
for (int i=1; i<=n; i++) a[i]=read(),p[a[i]].pb(i);
build(1,-n,n); int sum=0;ll ans=0;
/*
设新序列b，其中若在原数列中这个数是我们枚举的众数
那么在b中权值为1，否则权值是-1
那么我们维护一个b的前缀和数组sum
并用cnt[j]表示j在sum中出现了多少次
对于每一个众数的出现位置p我们可以算出他这个位置的前缀和sum[p]
那么他对答案造成的贡献就是cnt[1~sum[p]-1]
否则对于每一个极长连续-1段[l,r]（也就是被两个众数夹在中间的部分）
我们可以列出他对答案造成贡献的式子
sum(i=1 to r-l+1) 这里我们是相当于枚举的第l+i-1个位置对答案的贡献
sum(j=-n to sum-1-i) 这个sum是上一个众数出现位置的前缀和)
cnt[j] 仔细想一想没有任何问题
那么这个式子我们怎么用数据结构来维护呢
我们可以先把每个cnt[j]乘以(r-l+1) 然后减掉我们多算的部分
首先对于-n~sum-(r-l+1)-1我们显然没有多算
对于sum-(r-l+1)~sum-1的部分 (我们减掉多余的就可以了)
*/
for (int i=0; i<n; i++) if (p[i].size()) {//i表示我们枚举的区间众数 
sum1[1]=sum2[1]=t[1]=sum=0,clr[1]=1;
p[i].pb(n+1);
modify(1,-n,n,0,0);
for (int j=0; j<p[i].size(); j++) {
if ((!j&&p[i][j]>1)||(j&&p[i][j]>p[i][j-1]+1)) {
int l=(j)?p[i][j-1]+1:1,r=p[i][j]-1;
if (j) ans+= query_sum1(1,-n,n,-n,sum-1)*(r-l+1)
-query_sum2(1,-n,n,sum-(r-l+1),sum-1)
+query_sum1(1,-n,n,sum-(r-l+1),sum-1)*(sum-1-(r-l+1));
modify(1,-n,n,sum-(r-l+1),sum-1);
sum-=(r-l+1);
}
if (j!=p[i].size()-1) sum++,ans+=query_sum1(1,-n,n,-n,sum-1),modify(1,-n,n,sum,sum);//插入了一个n+1 所以这个不计入答案 
}
}
cout << ans << endl;
}
/*
5 0
1 1 2 2 3
*/

最后

以上就是腼腆钻石为你收集整理的[BZOJ5110][CODE+ DIV1 T4]Yazid 的新生舞会 线段树的全部内容，希望文章能够帮你解决[BZOJ5110][CODE+ DIV1 T4]Yazid 的新生舞会 线段树所遇到的程序开发问题。

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