Submission #67007544

---

Source Code Expand

#include <bits/stdc++.h>
#define ll long long
#define N 500010
using namespace std;
ll read(){
	char cc;
	while(1){cc=getchar();if((cc>='0'&&cc<='9')||cc=='-')break;}
	ll sum=0,flag=1;
	cc=='-'?flag=-1:sum=(cc^48);
	while(1){cc=getchar();if(!(cc>='0'&&cc<='9'))break;sum=(sum<<1)+(sum<<3)+(cc^48);}
	return sum*flag;
}
void write(ll x){
	if(!x)putchar('0');
	if(x<0){x=-x;putchar('-');}
	ll cc[25],cntt=0;
	while(x){cc[++cntt]=x%10;x/=10;}
	for(ll i=cntt;i>=1;i--)putchar(cc[i]+'0');
	putchar('\n');
}

const ll mod=998244353;

ll n,p[N],t[N<<2],T[N],tag[N<<2],sum=0,ans=0,shu2[N];
void add(ll &x,ll y){x=(x+y)%mod;}


void init(){
	sum=0;
	memset(T,0,sizeof(T));
	memset(t,0,sizeof(t));
	for(ll i=1;i<=n*4;i++)tag[i]=1;
}
void change1(ll x){for(;x<=n;x+=x&-x)T[x]++;}
ll ask1(ll x){ll ans=0;for(;x;x-=x&-x)ans+=T[x];return ans;}

void mul(ll x,ll w){
	tag[x]=tag[x]*w%mod;
	t[x]=t[x]*w%mod;
}
void pushdown(ll x){
	if(tag[x]!=1){
		mul(x<<1,tag[x]);
		mul(x<<1|1,tag[x]);
		tag[x]=1;
	}
}
void change(ll x,ll l,ll r,ll L,ll R,ll w){
	if(L>R)return ;
	if(L<=l&&r<=R){
		mul(x,w);
		return ;
	}
	pushdown(x);
	ll mid=(l+r)>>1;
	if(mid>=L)change(x<<1,l,mid,L,R,w);
	if(mid<R)change(x<<1|1,mid+1,r,L,R,w);
	t[x]=(t[x<<1]+t[x<<1|1])%mod;
}
void changesi(ll x,ll l,ll r,ll L,ll w){
	if(l==r){
		t[x]=w;
		return ;
	}
	pushdown(x);
	ll mid=(l+r)>>1;
	if(mid>=L)changesi(x<<1,l,mid,L,w);
	else changesi(x<<1|1,mid+1,r,L,w);
	t[x]=(t[x<<1]+t[x<<1|1])%mod;
}
ll ask(ll x,ll l,ll r,ll L,ll R){
	if(L>R)return 0;
	if(L<=l&&r<=R)return t[x];
	pushdown(x);
	ll mid=(l+r)>>1;
	if(mid>=L&&mid<R)return (ask(x<<1,l,mid,L,R)+ask(x<<1|1,mid+1,r,L,R))%mod;
	if(mid>=L)return ask(x<<1,l,mid,L,R);
	return ask(x<<1|1,mid+1,r,L,R);
}
int main(){
	shu2[0]=1;
	for(ll i=1;i<=500000;i++)shu2[i]=shu2[i-1]*2%mod;
	n=read();
	for(ll i=1;i<=n;i++)p[i]=read();

// maxi maxp
	init();
	for(ll i=1;i<=n;i++){
		ll shu=ask1(p[i]);
		change1(p[i]);
		changesi(1,1,n,p[i],p[i]*shu2[shu]%mod);
		add(sum,i*ask(1,1,n,p[i],n)%mod);
		// printf("%lld : %lld\n",i,ask(1,1,n,p[i],n));
		change(1,1,n,p[i]+1,n,2);
	}
	add(ans,sum);
	// printf("%lld \n",sum);
	// return 0;

// maxi minp
	init();
	for(ll i=1;i<=n;i++){
		ll shu=i-1-ask1(p[i]);
		change1(p[i]);
		changesi(1,1,n,p[i],p[i]*shu2[shu]%mod);
		add(sum,i*ask(1,1,n,1,p[i])%mod);
		// printf("%lld : %lld\n",i,ask(1,1,n,1,p[i]));
		change(1,1,n,1,p[i]-1,2);
	}
	add(ans,mod-sum);
	// printf("%lld \n",sum);

// mini maxp
	init();
	for(ll i=n;i>=1;i--){
		ll shu=ask1(p[i]);
		change1(p[i]);
		changesi(1,1,n,p[i],p[i]*shu2[shu]%mod);
		add(sum,i*ask(1,1,n,p[i],n)%mod);
		change(1,1,n,p[i]+1,n,2);
	}
	add(ans,mod-sum);
	// printf("%lld \n",sum);

// mini minp
	init();
	for(ll i=n;i>=1;i--){
		ll shu=n-i-ask1(p[i]);
		change1(p[i]);
		changesi(1,1,n,p[i],p[i]*shu2[shu]%mod);
		add(sum,i*ask(1,1,n,1,p[i])%mod);
		change(1,1,n,1,p[i]-1,2);
	}
	add(ans,sum);
	// printf("%lld \n",sum);


	write(ans);
	return 0;
}

Submission Info

Judge Result