P11164 [BalkanOI 2023] Permutations

发表于 分类于 本文字数： 6.8k 阅读时长 ≈ 8 分钟

P11164 [BalkanOI 2023] Permutations

思路

先判断是否有解。
即判断区间是否存在三元组 使得 ；或者二元组 使得 。
贪心的覆盖区间，三元组对于 我们只找最靠右的 和最靠左的 ；二元组对 只找最靠右的 。扫描线一遍 ，把权值都挂在 上维护即可。

然后求方案数。
先考虑一个弱化问题：将 的排列 放成最长递减子序列长度至多为二，共有多少种方案。
考虑一种类似维护连续段的转移，把序列按点 摊到平面上，称 为一个“谷”。
设 表示放完前 个数，最后一个“谷”在 的方案数。
发现我们新插入数只能是使最后一个“谷”向右移动，或者拼接在段的右端点上，即 会贡献给 。
在转移状态的平面上看这个方程，发现我们转移的路径是每次从当前层先到下一层，到下一层后可以选择向右转移若干状态或者不动。把这件事看成网格图上走路，每次必须向上走一步，然后可以选择向右走一些格子。每次选择是否向右走，以及向右走几格，对应方案与从 走到 的路径相对应。当 时状态无意义，即不能越过直线 。

回到原问题。
令 。小于 的数一定按升序放，而剩下的大于 的数在小于 的数放完前需要升序放。
这与我们刚才在网格图上走路的方式很像。
令 ，考虑共剩下 个数，其中小于 的有 个，大于 的数有 个。
然后像网格图上走路一样刻画放数的过程，走的步数与大于和小于 的数的个数向对应。即相当于从 走到 不越过 。
按 对称，反射容斥一下，答案为 。

代码

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
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T>
inline void read(T&x){
	int w = 0; x = 0;
	char ch = getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-') w = 1;
		ch = getchar();
	}
	while(ch>='0' && ch<='9'){
		x = (x<<1)+(x<<3)+(ch^48);
		ch = getchar();
	}
	if(w) x = ~x+1;
}
template <typename T,typename...Args>
inline void read(T&t,Args&...args){
	read(t); read(args...);
}
template <typename T>
inline T Max(T x,T y){ return (x > y ? x : y); }
template <typename T>
inline T Min(T x,T y){ return (x < y ? x : y); }
template <typename T>
inline T Abs(T x){ return (x < 0 ? ~x+1 : x); }
const int N = 3e5+10,INF = 0x3f3f3f3f;
const ll mod = 1e9+7;
int n,m,a[N];
ll ans[N];
struct G1{
	int l,r,id;
	inline int operator < (const G1&G){
		if(r^G.r) return r < G.r;
		return l < G.l;
	}
}g1[N];
struct G2{
	int l;
}g2[N];
struct Query{
	int l,r,id;
	inline int operator < (const Query&G) const{
		if(r^G.r) return r < G.r;
		return l < G.l;
	}
}q[N];
int st[N],stop;
struct Tree1{
	int minn[N<<2],maxn[N<<2];
	Tree1(){
		memset(minn,0x3f,sizeof(minn));
	}
	inline void build(int p,int nl,int nr){
		if(nl==nr){
			minn[p] = maxn[p] = a[nl];
			return ;
		}
		int mid = (nl+nr) >> 1;
		build(p<<1,nl,mid);
		build(p<<1|1,mid+1,nr);
		minn[p] = Min(minn[p<<1],minn[p<<1|1]);
		maxn[p] = Max(maxn[p<<1],maxn[p<<1|1]);
	}
	inline int query_min(int p,int nl,int nr,int ql,int qr){
		if(ql>qr) return INF;
		if(ql<=nl && nr<=qr) return minn[p];
		int mid = (nl+nr) >> 1;
		int res = INF;
		if(ql<=mid) res = Min(res,query_min(p<<1,nl,mid,ql,qr));
		if(qr>mid) res = Min(res,query_min(p<<1|1,mid+1,nr,ql,qr));
		return res;
	}
	inline int query_max(int p,int nl,int nr,int ql,int qr){
		if(ql>qr) return 0;
		if(ql<=nl && nr<=qr) return maxn[p];
		int mid = (nl+nr) >> 1;
		int res = 0;
		if(ql<=mid) res = Max(res,query_max(p<<1,nl,mid,ql,qr));
		if(qr>mid) res = Max(res,query_max(p<<1|1,mid+1,nr,ql,qr));
		return res;
	}
}t1;
struct Tree2{
	int vis[N<<2],maxn[N<<2];
	inline void update_vis(int p,int nl,int nr,int x){
		if(nl==nr){
			vis[p] = 1;
			return ;
		}
		int mid = (nl+nr) >> 1;
		if(x<=mid) update_vis(p<<1,nl,mid,x);
		else update_vis(p<<1|1,mid+1,nr,x);
		vis[p] = vis[p<<1]|vis[p<<1|1];
	}
	inline int query_vis(int p,int nl,int nr,int ql,int qr){
		if(ql>qr) return 0;
		if(ql<=nl && nr<=qr) return vis[p];
		int mid = (nl+nr) >> 1;
		int res = 0;
		if(ql<=mid) res = query_vis(p<<1,nl,mid,ql,qr);
		if(res) return res;
		if(qr>mid) res = query_vis(p<<1|1,mid+1,nr,ql,qr);
		return res;
	}
	inline void update_max(int p,int nl,int nr,int x,int k){
		if(nl==nr){
			maxn[p] = Max(maxn[p],k);
			return ;
		}
		int mid = (nl+nr) >> 1;
		if(x<=mid) update_max(p<<1,nl,mid,x,k);
		else update_max(p<<1|1,mid+1,nr,x,k);
		maxn[p] = Max(maxn[p<<1],maxn[p<<1|1]);
	}
	inline int query_max(int p,int nl,int nr,int ql,int qr){
		if(ql>qr) return 0;
		if(ql<=nl && nr<=qr) return maxn[p];
		int mid = (nl+nr) >> 1;
		int res = 0;
		if(ql<=mid) res = Max(res,query_max(p<<1,nl,mid,ql,qr));
		if(qr>mid) res = Max(res,query_max(p<<1|1,mid+1,nr,ql,qr));
		return res;
	}
}t2;
ll mul[N<<1],inv[N<<1];
inline ll quick_pow(ll x,ll y){
	ll res = 1;
	while(y){
		if(y&1) (res *= x)%=mod;
		(x *= x)%=mod;
		y >>= 1;
	}
	return res;
}
inline ll H(int maxn,int len){
	int ta = n-len;
	int tb = n-maxn-1;
	return (mul[ta+tb+1]*(ta-tb)%mod*inv[tb+1]%mod*inv[ta+1]%mod+mod)%mod;
}
int main(){
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);

	read(n);
	mul[0] = 1;
	for(int i=1;i<=n+n;++i) mul[i] = mul[i-1]*i%mod;
	inv[n+n] = quick_pow(mul[n+n],mod-2);
	for(int i=n+n;i;--i) inv[i-1] = inv[i]*i%mod;
	for(int i=1;i<=n;++i){
		read(a[i]);
		g1[i].id = i;
	}
	t1.build(1,1,n);
	for(int i=1;i<=n;++i){
		while(stop && a[i]>a[st[stop]]) --stop;
		g1[i].l = st[stop];
		st[++stop] = i;
	}
	stop = 0;
	for(int i=n;i;--i){
		while(stop && a[i]<a[st[stop]]) --stop;
		g1[i].r = st[stop];
		st[++stop] = i;
	}
	stop = 0;
	for(int i=1;i<=n;++i){
		while(stop && a[i]>a[st[stop]]) --stop;
		g2[i].l = st[stop];
		st[++stop] = i;
	}
	read(m);
	for(int i=1;i<=m;++i){
		read(q[i].l,q[i].r);
		q[i].id = i;
	}
	sort(g1+1,g1+1+n);
	sort(q+1,q+1+m);
	for(int i=1,nowq=1,nowg1=1;i<=n && nowq<=m;++i){
		while(g1[nowg1].r<=i && nowg1<=n){
			if(g1[nowg1].l && g1[nowg1].r) t2.update_vis(1,1,n,g1[nowg1].l);
			++nowg1;
		}
		if(g2[i].l) t2.update_max(1,1,n,g2[i].l,a[i]);
		while(q[nowq].r<=i && nowq<=m){
			if(!t2.query_vis(1,1,n,q[nowq].l,q[nowq].r)){
				if(t2.query_max(1,1,n,q[nowq].l,q[nowq].r)<Min(t1.query_min(1,1,n,1,q[nowq].l-1),t1.query_min(1,1,n,q[nowq].r+1,n))){
					ans[q[nowq].id] = H(t1.query_max(1,1,n,q[nowq].l,q[nowq].r),i-q[nowq].l+1);
				}
			}
			++nowq;
		}
	}
	for(int i=1;i<=m;++i) printf("%lld\n",ans[i]);

	fclose(stdin);
	fclose(stdout);
	return 0;
}