专栏文章

P11164

llsj2009Isj2OO9
P11164题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minya72r
此快照首次捕获于
2025/12/02 10:19
3 个月前
此快照最后确认于
2025/12/02 10:19
3 个月前
查看原文
首先判断合法性。如果存在 L≤i<j<k≤RL\le i<j<k\le R 使得 pi>pj>pkp_i>p_j>p_k 则不合法；找到 max⁡pi>pjpj\max\limits_{p_i>p_j}{p_j}，如果存在 x<pjx<p_j 未在 pL∼Rp_{L\sim R} 中出现，说明必然构成 pi>pj>xp_i>p_j>x，不合法。上面两者均容易在 O((n+q)log⁡n)\mathcal{O}((n+q)\log{n}) 复杂度内判断。
对于有解的询问，找到 v=max⁡L≤i≤Rpiv=\max\limits_{L\le i\le R}{p_i}，将所有未在 pL∼Rp_{L\sim R} 内出现的数分为 <v<v 的 A 类和 >v>v 的 B 类。有且仅有如下限制：
  • A 类数必须递增。
  • 在最后一个 A 类数之前的 B 类数必须递增。
枚举最后一个 A 类数位置 ii，答案为 ∑a≤i≤a+b(i−1a−1)fb,i−a=∑0≤i≤b(i+a−1a−1)fb,i\sum\limits_{a\le i\le a+b}\binom{i-1}{a-1}f_{b,i-a}=\sum\limits_{0\le i\le b}\binom{i+a-1}{a-1}f_{b,i}，其中 fn,kf_{n,k} 为长为 nn 的排列 pp，要求 p1∼kp_{1\sim k} 递增，不存在 ≥3\ge 3 的递减子序列的方案数。枚举 11 的位置 jj，要么 j=1j=1 要么 j>kj>k，其之前要求递增，得 fn,k=∑k−1≤j<nfn−1,jf_{n,k}=\sum\limits_{k-1\le j<n}f_{n-1,j}，刻画为格路计数，那就是 (x,y)(x,y) 可以走到 (x+1,0∼y+1)(x+1,0\sim y+1) 且要求 y≤xy\le x，将第 xx 列向下平移 xx 位，则 (x,y)(x,y) 可以走到 (x+1,−x∼y)(x+1,-x\sim y)，原本 y≤xy\le x 的限制自动满足；把格路按 yy 轴其翻转，再将 (x,y)→(x+1,y′)(x,y)\to(x+1,y') 中 yy 的变化一步步拆开，变成了 (x,y)→(x+1,y)/(x,y+1)(x,y)\to(x+1,y)/(x,y+1) 要求不经过直线 y=x+1y=x+1。而 fn,kf_{n,k} 在经过坐标变换后即从 (0,0)(0,0) 走到 (n,n−k)(n,n-k)，反射容斥一下得 fn,k=(2n−kn)−(2n−kn+1)f_{n,k}=\binom{2n-k}{n}-\binom{2n-k}{n+1}。
则答案为：
∑0≤i≤b(i+a−1a−1)((2b−ib)−(2b−ib+1))\sum\limits_{0\le i\le b}\binom{i+a-1}{a-1}\left( \binom{2b-i}{b}-\binom{2b-i}{b+1}\right)
以计算
∑0≤i≤b(i+a−1a−1)(2b−ib)\sum\limits_{0\le i\le b}\binom{i+a-1}{a-1}\binom{2b-i}{b}
为例，两项分别是 (0,0)→(a−1,i)(0,0)\to(a-1,i) 和 (0,0)→(b,b−i)(0,0)\to(b,b-i) 的格路数，将第二条格路平移，使其首位相接，那就是计数 (P,A)(\mathcal{P},\mathcal{A})，P\mathcal{P} 是一条 (0,0)→(a+b−1,b)(0,0)\to (a+b-1,b) 的格路，A\mathcal{A} 是 P\mathcal{P} 上一点且在第 a−1a-1 列上。(P,A)(\mathcal{P},\mathcal{A}) 可以和 (0,0)→(a+b,b)(0,0)\to(a+b,b) 的所有格路构成双射：找到 (a−1,∗)→(a,∗)(a-1,*)\to(a,*) 的边，将其删去，其后部分往前平移一格得到 P\mathcal{P}，令 A=(a−1,∗)\mathcal{A}=(a-1,*)。故可得最终答案为：
(a+2ba+b)−(a+2ba+b+1)\binom{a+2b}{a+b}-\binom{a+2b}{a+b+1}
复杂度瓶颈在于判断合法性为 O((n+q)log⁡n)\mathcal{O}((n+q)\log{n})。
CPP
#include<bits/stdc++.h>
// #define int long long
// #pragma GCC optimize(3,"Ofast","inline")
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ll long long
#define bint __int128
#define ull unsigned long long
#define uint unsigned int
#define ld double
#define PII pair<int,int>
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define umap unordered_map
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
#define pcnt(x) __builtin_popcount(x)
#define lg(x) (31-__builtin_clz(x))
using namespace std;
void file_IO() {
	freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);
}
bool M1;
const int INF=0x3f3f3f3f;
const ll INFLL=0x3f3f3f3f3f3f3f3f;
const ld eps=1e-9;template<int p>
struct mint {
	int x;
	mint() {
		x=0;
	}
	mint(int _x) {
		x=_x;
	}
	friend mint operator + (mint a,mint b) {
		return a.x+b.x>=p? a.x+b.x-p:a.x+b.x;
	}
	friend mint operator - (mint a,mint b)  {
		return a.x<b.x? a.x-b.x+p:a.x-b.x;
	}
	friend mint operator * (mint a,mint b) {
		return 1ll*a.x*b.x%p;
	}
	friend mint operator ^ (mint a,ll b) {
		mint res=1,base=a;
		while(b) {
			if(b&1)
				res*=base;
			base*=base; b>>=1;
		}
		return res;
	}
	friend mint operator ~ (mint a) {
		return a^(p-2);
	}
	friend mint operator / (mint a,mint b) {
		return a*(~b);
	}
	friend mint & operator += (mint& a,mint b) {
		return a=a+b;
	}
	friend mint & operator -= (mint& a,mint b) {
		return a=a-b;
	}
	friend mint & operator *= (mint& a,mint b) {
		return a=a*b;
	}
	friend mint & operator /= (mint& a,mint b) {
		return a=a/b;
	}
	friend mint operator ++ (mint& a) {
		return a+=1;
	}
	friend mint operator -- (mint& a) {
		return a-=1;
	}
};
const int MOD=1e9+7;
#define mint mint<MOD>
const int N=6e5+5;
mint jc[N],inv_jc[N];
mint C(int n,int m) {
	if(m<0||n<m)
		return 0;
	return jc[n]*inv_jc[n-m]*inv_jc[m];
}
void init(int n=6e5) {
	jc[0]=1;
	rep(i,1,n)
		jc[i]=jc[i-1]*i;
	inv_jc[n]=~jc[n];
	per(i,n-1,0)
		inv_jc[i]=inv_jc[i+1]*(i+1);
}
int f[N],g[N],a[N],n,q;
struct BIT {
	int tree[N];
	void update(int x,int k) {
		while(x)
			chkmax(tree[x],k),x-=x&-x;
	}
	int query(int x) {
		int res=0;
		while(x<=n)
			chkmax(res,tree[x]),x+=x&-x;
		return res;
	}
}; BIT T1,T2,T3,T4,T5;
struct BITadd {
	int tree[N];
	void update(int x,int k) {
		while(x<=n)
			tree[x]+=k,x+=x&-x;
	}
	int query(int x) {
		int res=0;
		while(x)
			res+=tree[x],x-=x&-x;
		return res;
	}
}; BITadd T6;
vector<PII> ask[N];
mint ans[N];
void solve() {
	scanf("%d",&n);
	rep(i,1,n) {
		scanf("%d",&a[i]);
		f[i]=T1.query(a[i]);
		g[i]=T2.query(a[i]);
		T1.update(a[i],i);
		T2.update(a[i],f[i]);
	}
	scanf("%d",&q);
	rep(i,1,q) {
		int l,r;
		scanf("%d%d",&l,&r);
		ask[r].push_back(make_pair(l,i));
	}
	int mx=0;
	rep(i,1,n) {
		T3.update(i,a[i]);
		T4.update(f[i],a[i]);
		T5.update(n-a[i]+1,n-i);
		T6.update(a[i],1);
		chkmax(mx,g[i]);
		for(auto x:ask[i]) {
			int l=x.first,k=x.second;
			if(mx>=l)
				continue;
			int t=T4.query(l);
			if(T6.query(t)!=t||n-T5.query(n-t+1)<l)
				continue;
			int v=T3.query(l),c0=v-(i-l+1),c1=n-v;
			ans[k]=C(c0+c1*2,c0+c1)-C(c0+c1*2,c0+c1+1);
		}
	}
	rep(i,1,q)
		printf("%d\n",ans[i].x);
}
bool M2;
// g++ P11164.cpp -std=c++14 -Wall -O2 -o P11164
signed main() {
	// file_IO();
	int testcase=1;
	init();
	// scanf("%d",&testcase);
	while(testcase--)
		solve();
	debug("used time = %dms\n",(signed)(1000*clock()/CLOCKS_PER_SEC));
	debug("used memory = %dMB\n",(signed)((&M1-&M2)/1024/1024));
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...