题目描述

题解

考虑对于 $k$k 的答案如何计算，非常暴力的话就是找出合法的 $(i,j)$(i,j) ，它对答案的贡献就是 $2^{i-1}\times 2^{n-j}$2i−1×2n−j ，然后我们稍微想一下，如果 $i$i 有很多个 $j$j 都是合法的话，或者 $j$j 有很多个 $i$i 都是合法的话，那其实就是对 $2^{n-j}$2n−j 做后缀和和对 $2^{i-1}$2i−1 做前缀和

于是我们可以在求 $k$k 的答案的时候维护4个树状数组： $<k$<k 的前缀和、后缀和， $>k$>k 的前缀和、后缀和，然后考虑从 $k-1$k−1 到 $k$k 的时候要把 $k$k 的信息从 $>k$>k 的树状数组和答案中删掉，然后再扔到 $<k$<k 的树状数组中去更新答案即可

效率： $O(nlogn)$O(nlogn)

代码

#include <cstdio>
using namespace std;
const int N=1e5+5,P=1e9+7;
int n,a[N],w[N],p[N],s[4][N],S;
void upd(int o,int x,int v){
	for (;x<=n;x+=x&-x) (s[o][x]+=v)%=P;
}
int qry(int o,int x){
	int v=0;
	for (;x;x-=x&-x) (v+=s[o][x])%=P;
	return v;
}
void Upd(int o,int x,int v){
	for (;x;x-=x&-x) (s[o][x]+=v)%=P;
}
int Qry(int o,int x){
	int v=0;
	for (;x<=n;x+=x&-x) (v+=s[o][x])%=P;
	return v;
}
int main(){
	scanf("%d",&n);w[0]=1;
	for (int i=1;i<=n;i++)
		scanf("%d",&a[i]),
		w[i]=(w[i-1]<<1)%P,p[a[i]]=i;
	for (int i=1;i<=n;i++)
		upd(0,i,w[i-1]),Upd(1,i,w[n-i]);
	for (int x,i=1;i<=n;i++){
		x=p[i];
		upd(0,x,P-w[x-1]);
		Upd(1,x,P-w[n-x]);
		(S+=P-1ll*Qry(3,x)*w[x-1]%P)%=P;
		(S+=P-1ll*qry(2,x)*w[n-x]%P)%=P;
		printf("%d\n",S);
		(S+=1ll*Qry(1,x)*w[x-1]%P)%=P;
		(S+=1ll*qry(0,x)*w[n-x]%P)%=P;
		upd(2,x,w[x-1]);
		Upd(3,x,w[n-x]);
	}
	return 0;
}

• 点赞
• 收藏
• 分享
• • 文章举报

Johnny817 发布了128 篇原创文章 · 获赞 5 · 访问量 1万+ 私信 关注