luogu P4062 [Code+#1]Yazid 的新生舞会（线段树+套路）

今天原来是平安夜啊

感觉这题是道好题。

一个套路枚举权值\(x\)，把权值等于\(x\)的设为1，不等于的设为-1，然后问题转化为多少个区间权值和大于。

发现并不是很好做，还有一个套路，用前缀和查分来表示区间。然后就是

\[i<j
\]

\[sum[i]<sum[j]
\]

然后树状数组可以做\(a[i]\leq7\)的数据。

那么\(a[i]\)那么大该怎么办？

考虑我们构建的\(1,-1\)数列中连续-1的数列很多。

然后这些连续-1不会互相影响的贡献，然后我们考虑直接算出这些连续-1的贡献。

设这段连续-1的两端的sum为\(l,r\)。贡献为：

\[\sum_{i=l}^r\sum_{j=-inf}^{i-1}cnt[j]=(r-l+1)*\sum_{i=-inf}^{l-1}cnt[i]+\sum_{i=l}^r(r-i)*cnt[i]
\]

然后我们在线段树上维护\(i\)和\(cnt[i]\)，然后用线段树可以把这个-1序列\(logn\)处理掉。

然后每一个1单独处理，最后总复杂度\(O(nlogn)\)

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<vector>

using namespace std;

#define int long long

#define mid ((l+r)>>1)

#define ls now<<1

#define rs now<<1|1

const int N=501000;

vector<int> vec[N];

int sum[N*2*5],sumi[N*2*5],lazy[N*2*5],a[N],b[N],last,lastsum,ans,n;

int read(){

	int sum=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}

	return sum*f;

}

void update(int now){

	sum[now]=sum[ls]+sum[rs];

	sumi[now]=sumi[ls]+sumi[rs];

}

void pushdown(int l,int r,int now){

	if(lazy[now]==0)return;

	if(l==r)return;

	sum[ls]+=(mid-l+1)*lazy[now];

	sumi[ls]+=(mid+l)*(mid-l+1)/2*lazy[now];

	sum[rs]+=(r-(mid+1)+1)*lazy[now];

	sumi[rs]+=(r+mid+1)*(r-(mid+1)+1)/2*lazy[now];

	lazy[ls]+=lazy[now];

	lazy[rs]+=lazy[now];

	lazy[now]=0;

}

void add(int l,int r,int L,int R,int k,int now){

	if(R<l||L>r)return;

	pushdown(l,r,now);

	if(L<=l&&r<=R){

		sum[now]+=(r-l+1)*k;

		sumi[now]+=(l+r)*(r-l+1)/2*k;

		lazy[now]+=k;

		return;

	}

	add(l,mid,L,R,k,ls);

	add(mid+1,r,L,R,k,rs);

	update(now);

}

int check(int l,int r,int L,int R,int now){

	if(R<l||L>r)return 0;

	pushdown(l,r,now);

	if(L<=l&&r<=R)return sum[now];

	return check(l,mid,L,R,ls)+check(mid+1,r,L,R,rs);

}

int checki(int l,int r,int L,int R,int now){

	if(R<l||L>r)return 0;

	pushdown(l,r,now);

	if(L<=l&&r<=R)return sumi[now];

	return checki(l,mid,L,R,ls)+checki(mid+1,r,L,R,rs);

}

signed main(){

	n=read();int hh=read();

	for(int i=1;i<=n;i++)a[i]=read(),b[i]=a[i];

	sort(b+1,b+1+n);

	int tot=unique(b+1,b+1+n)-b-1;

	for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+1+tot,a[i])-b;

	for(int i=1;i<=n;i++)vec[a[i]].push_back(i);

	add(1,2*n,n,n,1,1);

	for(int i=1;i<=tot;i++){

		vec[i].push_back(n+1);

		last=0;lastsum=0;

		for(int j=0;j<vec[i].size();j++){

			int L=vec[i][j]-last-1;

			int l=lastsum-L;

			int r=lastsum-1;

			if(vec[i][j]!=last+1){

				ans+=L*check(1,2*n,1,l+n-1,1);

				ans+=(r+n)*check(1,2*n,l+n,r+n,1);

				ans-=checki(1,2*n,l+n,r+n,1);

				add(1,2*n,l+n,r+n,1,1);

			}

			if(vec[i][j]==n+1)continue;

			ans+=check(1,2*n,1,l+n,1);

			add(1,2*n,l+1+n,l+1+n,1,1);

			last=vec[i][j];lastsum=l+1;

		}

		last=0;lastsum=0;

		for(int j=0;j<vec[i].size();j++){

			int L=vec[i][j]-last-1;

			int l=lastsum-L;

			int r=lastsum-1;

			if(vec[i][j]!=last+1)add(1,2*n,l+n,r+n,-1,1);

			if(vec[i][j]==n+1)continue;

			add(1,2*n,l+1+n,l+1+n,-1,1);

			last=vec[i][j];lastsum=l+1;

		}

	}

	printf("%lld\n",ans);

	return 0;

}

巴特西

luogu P4062 [Code+#1]Yazid 的新生舞会（线段树+套路）

最新文章

热门文章