P11164

lsj2009 · 2025-09-10 09:12:03 · 题解

首先判断合法性。如果存在 L\le i<j<k\le R 使得 p_i>p_j>p_k 则不合法；找到 \max\limits_{p_i>p_j}{p_j}，如果存在 x<p_j 未在 p_{L\sim R} 中出现，说明必然构成 p_i>p_j>x，不合法。上面两者均容易在 \mathcal{O}((n+q)\log{n}) 复杂度内判断。

对于有解的询问，找到 v=\max\limits_{L\le i\le R}{p_i}，将所有未在 p_{L\sim R} 内出现的数分为 <v 的 A 类和 >v 的 B 类。有且仅有如下限制：

• A 类数必须递增。

• 在最后一个 A 类数之前的 B 类数必须递增。

枚举最后一个 A 类数位置 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}，其中 f_{n,k} 为长为 n 的排列 p，要求 p_{1\sim k} 递增，不存在 \ge 3 的递减子序列的方案数。枚举 1 的位置 j，要么 j=1 要么 j>k，其之前要求递增，得 f_{n,k}=\sum\limits_{k-1\le j<n}f_{n-1,j}，刻画为格路计数，那就是 (x,y) 可以走到 (x+1,0\sim y+1) 且要求 y\le x，将第 x 列向下平移 x 位，则 (x,y) 可以走到 (x+1,-x\sim y)，原本 y\le x 的限制自动满足；把格路按 y 轴其翻转，再将 (x,y)\to(x+1,y') 中 y 的变化一步步拆开，变成了 (x,y)\to(x+1,y)/(x,y+1) 要求不经过直线 y=x+1。而 f_{n,k} 在经过坐标变换后即从 (0,0) 走到 (n,n-k)，反射容斥一下得 f_{n,k}=\binom{2n-k}{n}-\binom{2n-k}{n+1}。

则答案为：

以计算

为例，两项分别是 (0,0)\to(a-1,i) 和 (0,0)\to(b,b-i) 的格路数，将第二条格路平移，使其首位相接，那就是计数 (\mathcal{P},\mathcal{A})，\mathcal{P} 是一条 (0,0)\to (a+b-1,b) 的格路，\mathcal{A} 是 \mathcal{P} 上一点且在第 a-1 列上。(\mathcal{P},\mathcal{A}) 可以和 (0,0)\to(a+b,b) 的所有格路构成双射：找到 (a-1,*)\to(a,*) 的边，将其删去，其后部分往前平移一格得到 \mathcal{P}，令 \mathcal{A}=(a-1,*)。故可得最终答案为：

复杂度瓶颈在于判断合法性为 \mathcal{O}((n+q)\log{n})。

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