2023NOIP A层联测6 数点

题目大意

给你一个排列$p$，对于每一个$i$，我们在平面上，放置一个点$(i,p_i)$。对于坐标上下限都在$1\sim n$内的全体$(\frac{n(n+1)}{2}{)}^2$矩形，求每个矩形内部点数的$k$次方之和。

形式化地，请你计算

∑ 1 ≤ l ≤ r ≤ n ∑ 1 ≤ d ≤ u ≤ n ∣ { i ∣ l ≤ i ≤ r ∨ d ≤ p i ≤ u } ∣ \sum\limits_{1\leq l\leq r\leq n}\sum\limits_{1\leq d\leq u\leq n}|\{i|l\leq i\leq r\vee d\leq p_i\leq u\}| 1≤l≤r≤n∑​1≤d≤u≤n∑​∣{i∣l≤i≤r∨d≤pi​≤u}∣

$1\le n\le 10^5,1\le k\le 3$

题解

我们可以考虑拆贡献，点数的$k$次方可以看成选$k$个点的方案的线性组合。

什么意思呢？就是在这$n$个点中有序地可重地选择$k$个点，将所有包含这$k$个点的矩形的贡献$+1$，注意所有从$n$个点中有序地可重地选$k$个点的方案都要被计算贡献。

为什么可以这样呢？对于每个矩形，设这个矩形内的点数为$t$，在这个矩形中有序地可重地选$k$个点的方案数为$t^k$，也就是说这个矩形在上面计算贡献的时候将贡献加了$t^k$次一。

下面，我们来求$k$为不同的值时的答案。

当$k=1$时

对每个点$(x,p_x)$，答案的贡献增加$x\times (n-x+1)\times p_x\times (n-p_x+1)$。

当$k=2$时

我们考虑选的两个点相同的情况和两个点不同的情况。

对于两个点相同的情况，这其实就是$k=1$的情况，每种情况会被算一次。

对于两个点不同的情况，我们可以分为顺序对和逆序对来考虑：

• 对于顺序对$x<y,p_x<p_y$，其贡献为$x\times p_x\times (n-y+1)\times (n-p_y+1)$，将$x\times p_x$存入树状数组中，再用$(n-y+1)\times (n-p_y+1)$来乘即可
• 对于逆序对$x<y,p_x>p_y$将排列翻转之后按顺序对的方法来做即可

因为选点是有序的，每种顺序对和逆序对都用两种选法被选到，所以两个点不同的情况的贡献要乘$2$。

当$k=3$时

将$k=1$的贡献计算一次（三次选择同一个点），$k=2$的贡献计算两次（三次选择两个不同的点），下面再考虑三次选择三个不同的点的贡献。

分为两种本质不同的情况：

情况1

------
|*   |
| *  |
|  * |
------
1
2
3
4
5

这种情况出现了$2$次（按$i$左右翻转，总共有$2$次），用两个树状数组维护即可。

情况2

------
|  * |
|*   |
| *  |
------
1
2
3
4
5

这种情况总共出现了$4$次（按$i$左右翻转，按$p_i$上下翻转，四个角度各一次，总共有$4$次），用线段树来维护即可。可以在加入第一个点时直接在对应位置上加数，在加入第二个点时将其后缀乘上对应的数，再加入第三个点时查询前缀和。

因为选点是有序的，每种顺序对和逆序对都用六种选法被选到，所以两个点不同的情况的贡献要乘$6$。

时间复杂度为$O(n\log n)$。

code

#include
#define lc k<<1
#define rc k<<1|1
using namespace std;
const long long mod=998244353;
int n,K,p[100005];
long long tr1[100005],tr2[100005];
long long s[500005],hv[500005],ly[500005];
int lb(int i){
	return i&(-i);
}
void pt1(int i,long long v){
	while(i<=n){
		tr1[i]=(tr1[i]+v)%mod;
		i+=lb(i);
	}
}
long long find1(int i){
	long long re=0;
	while(i){
		re=(re+tr1[i])%mod;
		i-=lb(i);
	}
	return re;
}
void pt2(int i,long long v){
	while(i<=n){
		tr2[i]=(tr2[i]+v)%mod;
		i+=lb(i);
	}
}
long long find2(int i){
	long long re=0;
	while(i){
		re=(re+tr2[i])%mod;
		i-=lb(i);
	}
	return re;
}
void build(int k,int l,int r){
	s[k]=hv[k]=ly[k]=0;
	if(l==r) return;
	int mid=l+r>>1;
	build(lc,l,mid);
	build(rc,mid+1,r);
}
void down(int k){
	s[lc]=(s[lc]+hv[lc]*ly[k])%mod;
	s[rc]=(s[rc]+hv[rc]*ly[k])%mod;
	ly[lc]=(ly[lc]+ly[k])%mod;
	ly[rc]=(ly[rc]+ly[k])%mod;
	ly[k]=0;
}
void ch(int k,int l,int r,int x,long long y){
	if(l==r&&l==x){
		hv[k]=y;
		s[k]=ly[k]=0;
		return;
	}
	if(ly[k]) down(k);
	int mid=l+r>>1;
	if(x<=mid) ch(lc,l,mid,x,y);
	else ch(rc,mid+1,r,x,y);
	hv[k]=(hv[lc]+hv[rc])%mod;
	s[k]=(s[lc]+s[rc])%mod;
}
void ts(int k,int l,int r,int x,int y,long long v){
	if(l>=x&&r<=y){
		ly[k]=(ly[k]+v)%mod;
		s[k]=(s[k]+v*hv[k])%mod;
		return;
	}
	if(ly[k]) down(k);
	int mid=l+r>>1;
	if(x<=mid) ts(lc,l,mid,x,y,v);
	if(y>mid) ts(rc,mid+1,r,x,y,v);
	s[k]=(s[lc]+s[rc])%mod;
}
long long find(int k,int l,int r,int x,int y){
	if(l>=x&&r<=y) return s[k];
	if(ly[k]) down(k);
	int mid=l+r>>1;
	long long re=0;
	if(x<=mid) re=(re+find(lc,l,mid,x,y))%mod;
	if(y>mid) re=(re+find(rc,mid+1,r,x,y))%mod;
	return re;
}
long long gt(){
	long long re=0;
	build(1,1,n);
	for(int i=1;i<=n;i++){
		re=(re+find(1,1,n,1,p[i])*(n-i+1)%mod*(n-p[i]+1)%mod)%mod;
		ts(1,1,n,p[i],n,p[i]);
		ch(1,1,n,p[i],i);
	}
	return re;
}
long long gt1(){
	long long re=0;
	for(int i=1;i<=n;i++){
		re=(re+1ll*i*(n-i+1)%mod*p[i]%mod*(n-p[i]+1)%mod)%mod;
	}
	return re;
}
long long gt2(){
	long long re=0;
	for(int i=1;i<=n;i++){
		re=(re+find1(p[i])*(n-i+1)%mod*(n-p[i]+1)%mod)%mod;
		pt1(p[i],1ll*i*p[i]%mod);
	}
	for(int i=1;i<=n;i++){
		tr1[i]=0;
		if(i<n-i+1) swap(p[i],p[n-i+1]);
	}
	for(int i=1;i<=n;i++){
		re=(re+find1(p[i])*(n-i+1)%mod*(n-p[i]+1)%mod)%mod;
		pt1(p[i],1ll*i*p[i]%mod);
	}
	for(int i=1;i<=n;i++){
		tr1[i]=0;
		if(i<n-i+1) swap(p[i],p[n-i+1]);
	}
	return re;
}
long long gt3(){
	long long re=0;
	for(int i=1;i<=n;i++){
		long long now=find1(p[i]);
		pt1(p[i],1ll*i*p[i]%mod);
		re=(re+find2(p[i])*(n-i+1)%mod*(n-p[i]+1)%mod)%mod;
		pt2(p[i],now);
	}
	for(int i=1;i<=n;i++){
		tr1[i]=tr2[i]=0;
		if(i<n-i+1) swap(p[i],p[n-i+1]);
	}
	for(int i=1;i<=n;i++){
		long long now=find1(p[i]);
		pt1(p[i],1ll*i*p[i]%mod);
		re=(re+find2(p[i])*(n-i+1)%mod*(n-p[i]+1)%mod)%mod;
		pt2(p[i],now);
	}
	for(int i=1;i<=n;i++){
		tr1[i]=tr2[i]=0;
		if(i<n-i+1) swap(p[i],p[n-i+1]);
	}
	re=(re+gt())%mod;
	for(int i=1;i<=n;i++)
	if(i<n-i+1) swap(p[i],p[n-i+1]);
	re=(re+gt())%mod;
	for(int i=1;i<=n;i++)
	p[i]=n-p[i]+1;
	re=(re+gt())%mod;
	for(int i=1;i<=n;i++)
	if(i<n-i+1) swap(p[i],p[n-i+1]);
	re=(re+gt())%mod;
	return re;
}
int main()
{
	freopen("points.in","r",stdin);
	freopen("points.out","w",stdout);
	scanf("%d%d",&n,&K);
	for(int i=1;i<=n;i++){
		scanf("%d",&p[i]);
	}
	if(K==1) printf("%lld",gt1());
	else if(K==2)  printf("%lld",(gt1()+2*gt2())%mod);
	else{
		printf("%lld",(gt1()+6*gt2()+6*gt3())%mod);
	}
	return 0;
}
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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173