题解：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}。最终答案为 f_{n+1,n+1}。
在转移状态的平面上看这个方程，发现我们转移的路径是每次从当前层先到下一层，到下一层后可以选择向右转移若干状态或者不动。把这件事看成网格图上走路，每次必须向上走一步，然后可以选择向右走一些格子。每次选择是否向右走，以及向右走几格，对应方案与从 (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;
}