AT_abc439_f AT_abc439_f [ABC439F] Beautiful Kadomatsu

思路

省流：线段树。
首先我们发现，若按照 $(i,a_i)$ 的坐标在平面直角坐标系中建图，并且将每个点与它前面和后面（如果存在的话）的点相连，那么趋势一定呈一个波浪状。
又发现题目中要求的两种点就是波浪的波峰和波谷。
显然这两种点的数量最多相差 $1$，且差值取决于开头和结尾的趋势。
若要使得波峰数量比波谷数量多，则开头必定为增加，而结尾必定为减少。
考虑对正序对及逆序对计数。
显然可以用线段树求出正、逆序对的数量，表示为 $smr$ 和 $bgr$。
然后由于 $l,r,l<r$ 中间怎么选点不影响，则每个正、逆序对之间的点可任意选或不选，方案数为 $2^{r-l-1}$ 次。
而当 $l=r$ 时，中间无点可选。
那所有贡献则为 $\sum_{i=1}^n smr_i\cdot bgr_i$ 加上 $\sum_{i=1}^n\sum_{j=i+1}^n smr_i\cdot bgr_j\cdot 2^{j-i-1}$。
第一部分可以 $O(n)$ 地求出，直接暴力即可。
第二部分还需要我们进一步化简：

  • $2^x$ 可以直接预处理；
  • 用一个 $sum$ 处理当前 $i$ 对应的所有 $j$，$sum=\sum_{i=2}^n bgr_i\cdot 2^{i-2}$；

对于每下一个 $i$，先从 $sum$ 中去掉下一次统计中没有的 $bgr_{i+1}$，再将 $sum$ 除以 $2$，即乘以 $2$ 在模 $998244353$ 意义下的逆元 $499122177$ 即可。
每一步在答案中加上 $sum\cdot smr_i$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<bits/stdc++.h>
#define fir first
#define sec second 
#define int long long
#define pii pair<int,int>
#define fep(i,s,e) for(int i=s;i<e;i++)
#define pef(i,s,e) for(int i=s;i>e;i--)
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define per(i,s,e) for(int i=s;i>=e;i--)
namespace FastIO{
	template<typename T>inline void read(T &x){
		x=0;int f=1;char c=getchar();
		for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
		for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);x*=f;
	}
	template<typename T,typename...Args>
    inline void read(T &x,Args&...args){
        read(x);
        read(args...);
    }
	template<typename T>void print(T x){
		if(x<0)x=-x,putchar('-');
		if(x>9)print(x/10);
		putchar((x%10)^48);
	}
}
using namespace std;
using namespace FastIO;
const int N=3e5+47,mod=998244353,inv=499122177;
int n,a[N],smr[N],bgr[N],ans;
int p[N],sum;
struct segment_tree{
	int c[4*N];
	int laz[4*N];
	void make_tag(int p,int k,int s,int t){
		c[p]+=k*(t-s+1);
		laz[p]+=k;
	}
	void push_down(int p,int s,int t){
		if(laz[p]==0)return;
		int mid=(s+t)/2;
		make_tag(p*2,laz[p],s,mid);
		make_tag(p*2+1,laz[p],mid+1,t);
		laz[p]=0;
	}
	void update(int p,int k,int l,int r,int s,int t){
		if(l<=s&&t<=r){
			make_tag(p,k,s,t);
			return;
		}
		push_down(p,s,t);
		int mid=(s+t)/2;
		if(l<=mid)update(p*2,k,l,r,s,mid);
		if(r>mid)update(p*2+1,k,l,r,mid+1,t);
		c[p]=c[p*2]+c[p*2+1];
	}
	int getsum(int p,int l,int r,int s,int t){
		if(l<=s&&t<=r){
			return c[p];
		}
		push_down(p,s,t);
		int mid=(s+t)/2;
		int sum=0;
		if(l<=mid)sum+=getsum(p*2,l,r,s,mid);
		if(r>mid)sum+=getsum(p*2+1,l,r,mid+1,t);
		return sum;
	}
}G,T;
signed main(){
	read(n);
	p[0]=1;
	rep(i,1,n){
		p[i]=p[i-1]*2%mod;
	}
	rep(i,1,n){
		read(a[i]);
	}
	rep(i,1,n){
		G.update(1,1,a[i],a[i],1,n);
		smr[i]=G.getsum(1,1,a[i],1,n)-G.getsum(1,a[i],a[i],1,n);
	}
	per(i,n,1){
		T.update(1,1,a[i],a[i],1,n);
		bgr[i]=T.getsum(1,1,a[i],1,n)-T.getsum(1,a[i],a[i],1,n);
	}
	rep(i,1,n){
		ans+=smr[i]*bgr[i]%mod;
		ans%=mod;
	}
	rep(i,2,n){
		sum+=bgr[i]*p[i-2];
		sum%=mod;
	}
	rep(i,1,n){
		ans+=smr[i]*sum%mod;
		ans%=mod;
		sum-=bgr[i+1];
		sum=(sum%mod+mod)%mod;
		sum*=inv;
		sum%=mod;
	}
	print(ans);
}