P11164 [BalkanOI 2023] Permutations

思路

先判断是否有解。
即判断区间是否存在三元组 \((p_i,p_j,p_k)(i < j < k)\) 使得 \(p_i > p_j > p_k\)；或者二元组 \((p_i,p_j)(i<j)\) 使得 \(p_i > p_j > \min_{k=1}^{L-1} \min_{k=R+1}^{n} \space p_k\)。
贪心的覆盖区间，三元组对于 \(j\) 我们只找最靠右的 \(i\) 和最靠左的 \(k\)；二元组对 \(j\) 只找最靠右的 \(i\)。扫描线一遍 \(j\)，把权值都挂在 \(i\) 上维护即可。

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

回到原问题。
令 \(mx = \max_{i=L}^{R} \space p_i\)。小于 \(mx\) 的数一定按升序放，而剩下的大于 \(mx\) 的数在小于 \(mx\) 的数放完前需要升序放。
这与我们刚才在网格图上走路的方式很像。
令 \(Len = R-L+1\)，考虑共剩下 \(n-Len\) 个数，其中小于 \(mx\) 的有 \(mx-Len\) 个，大于 \(mx\) 的数有 \(n-mx\) 个。
然后像网格图上走路一样刻画放数的过程，走的步数与大于和小于 \(mx\) 的数的个数向对应。即相当于从 \((mx,Len)\) 走到 \((n,n)\) 不越过 \(y=x\)。
按 \(y=x+1\) 对称，反射容斥一下，答案为 \(C_{2n-mx-Len}^{n-Len} - C_{2n-mx-Len}^{n-Len+1}\)。

代码

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;
}