P9870题解

· · 题解

P9870 [NOIP2023] 双序列拓展

题目传送门

题解

T3 双序列拓展(expand)

考察：dp、人类智慧（

部分分启示正解。

将原题目转化为这样：两个指针分别指着两个序列，每次将任意至少一个指针向后移一个位置，并使每时每刻都满足两个指针所指的位置有单调的偏序关系。

所谓单调的偏序关系可以用第一个位置来判断，在下文我们只考虑 a<b 的情况。

我们考虑 dp：记 f_{i,j} 表示 a_{1-i} 能否和 b_{1-j} 匹配，那么有转移 f_{i,j}=[a_i<b_j]\operatorname{and}(f_{i-1,j}\operatorname{or}f_{i,j-1}\operatorname{or}f_{i-1,j-1})。此时即可 O(qnm) 完成本题。

我们考虑构造 01 矩阵 c，其中 c_{i,j}=[a_i<b_j]，那么等价于我们要判断是否存在只走 1，只能向下、向右、向右下的路径从 (1,1) 到 (n,m)。

其实我们不会向右下走，因为可以证明不存在

1 0
0 1

这样的矩阵，但对正解没啥作用，所以我就没管了。

由于性质保证，我们发现最后一列与最后一行都是 1。接下来我们考虑 a 除 a_n 外的最小值 a_{\min} 与 b 除 b_m 外的最小值 b_{\min}，如果 a_{\min}<b_{\min}，那么 a_{\min} 所在的列也全是 1，于是我们可以递归下去；否则，一定有 b_{\min} 所在的行全是 0。

对于 a_{\max} 和 b_{\max} 我们同样考虑，如果 b_{\max}>a_{\max} 那么就继续递归，否则一定有 a_{\max} 所在的列全是 0，然后你发现，b_{\min} 所在的行与 a_{\max} 所在的列把 (1,1) 围起来了！于是就直接返回 false。

实现的话预处理前缀 \min、\max 即可。

其实 70pts 就是 100pts 的一半，物理意义的一半，我们寻找全局 a_{\min} 和全局 b_{\max}，只要有一列或一行全是 0，那么就相当于分割了 (1,1) 和 (n,m)，否则做两次特殊性质即可。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int rd() {
    int s=0,m=0;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-')m=1;ch=getchar();}
    while( isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return m?-s:s;
}
int cc,n,m,q,c[500005],d[500005],a[500005],b[500005],pax[500005],pan[500005],sax[500005],san[500005],pbx[500005],pbn[500005],sbx[500005],sbn[500005];
bool calc1(int x,int y) {
    if(x==1||y==1) return 1;
    int ax=pax[x-1],an=pan[x-1],bx=pbx[y-1],bn=pbn[y-1];
    if(a[an]<b[bn]) return calc1(an,y);
    if(b[bx]>a[ax]) return calc1(x,bx);
    return 0;
}
bool calc2(int x,int y) {
    if(x==n||y==m) return 1;
    int ax=sax[x+1],an=san[x+1],bx=sbx[y+1],bn=sbn[y+1];
    if(a[an]<b[bn]) return calc2(an,y);
    if(b[bx]>a[ax]) return calc2(x,bx);
    return 0;
}
bool check() {
    if(a[1]>b[1]) {
        for(int i=1;i<=n;i++) a[i]*=-1;
        for(int i=1;i<=m;i++) b[i]*=-1;
    }
    pax[1]=1,pan[1]=1;
    for(int i=2;i<=n;i++)
        pax[i]=(a[pax[i-1]]>a[i]?pax[i-1]:i),
        pan[i]=(a[pan[i-1]]<a[i]?pan[i-1]:i);
    pbx[1]=1,pbn[1]=1;
    for(int i=2;i<=m;i++)
        pbx[i]=(b[pbx[i-1]]>b[i]?pbx[i-1]:i),
        pbn[i]=(b[pbn[i-1]]<b[i]?pbn[i-1]:i);
    sax[n]=n,san[n]=n;
    for(int i=n-1;i>=1;i--)
        sax[i]=(a[sax[i+1]]>a[i]?sax[i+1]:i),
        san[i]=(a[san[i+1]]<a[i]?san[i+1]:i);
    sbx[m]=m,sbn[m]=m;
    for(int i=m-1;i>=1;i--)
        sbx[i]=(b[sbx[i+1]]>b[i]?sbx[i+1]:i),
        sbn[i]=(b[sbn[i+1]]<b[i]?sbn[i+1]:i);
    int ax=pax[n],an=pan[n],bx=pbx[m],bn=pbn[m];
    if(a[an]>=b[bn]) return 0;
    if(b[bx]<=a[ax]) return 0;
    return calc1(an,bx)&calc2(an,bx);
}
signed main() {
    cin>>cc>>n>>m>>q;
    for(int i=1;i<=n;i++)
        a[i]=c[i]=rd();
    for(int i=1;i<=m;i++)
        b[i]=d[i]=rd();
    cout<<check();
    while(q--) {
        for(int i=1;i<=n;i++) a[i]=c[i];
        for(int i=1;i<=m;i++) b[i]=d[i];
        int k1=rd(),k2=rd();
        for(int i=1;i<=k1;i++) {
            int p=rd(),v=rd();
            a[p]=v;
        }
        for(int i=1;i<=k2;i++) {
            int p=rd(),v=rd();
            b[p]=v;
        }
        cout<<check();
    }
    return 0;
}

时间复杂度 O(q(n+m))。