P9870 [NOIP2023] 双序列拓展

用户头像 发布于 16 小时前 78 次阅读 OI

钦定 X1>Y1X_1>Y_1，不难发现必须满足 Xmax>Ymax, Xmin>YminX_{max}>Y_{max},\ X_{min}>Y_{min}，

再看特殊性质，不难发现直接递归求解即可，每次检查是否能达到当前的 XmaxX_{max} 或 YminY_{min}。

这里的 XmaxX_{max} 和 YminY_{min} 将原序列分成了两个部分，而两个部分正好是特殊性质，所以分两次递归即可。

代码：

#include<bits/stdc++.h>
using namespace std;

const int N=5e5+5;
int n,m,q;
int x[N],y[N],a[N],b[N],ta[N],tb[N];
int pma[N],pmi[N],pmb[N],pmj[N];
int sma[N],smi[N],smb[N],smj[N];

void init(){
    pma[1]=pmi[1]=1;
    for(int i=2;i<=n;i++){
        pmi[i]=a[i]<a[pmi[i-1]]?i:pmi[i-1];
        pma[i]=a[i]>a[pma[i-1]]?i:pma[i-1];
    }
    pmb[1]=pmj[1]=1;
    for(int i=2;i<=m;i++){
        pmj[i]=b[i]<b[pmj[i-1]]?i:pmj[i-1];
        pmb[i]=b[i]>b[pmb[i-1]]?i:pmb[i-1];
    }
    sma[n]=smi[n]=n;
    for(int i=n-1;i>=1;i--){
        smi[i]=a[i]<a[smi[i+1]]?i:smi[i+1];
        sma[i]=a[i]>a[sma[i+1]]?i:sma[i+1];
    }
    smb[m]=smj[m]=m;
    for(int i=m-1;i>=1;i--){
        smj[i]=b[i]<b[smj[i+1]]?i:smj[i+1];
        smb[i]=b[i]>b[smb[i+1]]?i:smb[i+1];
    }
}

bool chk1(int i,int j){
    if(i==1||j==1) return 1;
    if(a[pmi[i-1]]<b[pmj[j-1]]) return chk1(pmi[i-1],j);
    if(b[pmb[j-1]]>a[pma[i-1]]) return chk1(i,pmb[j-1]);
    return 0;
}

bool chk2(int i,int j){
    if(i==n||j==m) return 1;
    if(a[smi[i+1]]<b[smj[j+1]]) return chk2(smi[i+1],j);
    if(b[smb[j+1]]>a[sma[i+1]]) return chk2(i,smb[j+1]);
    return 0;
}

bool sol(){
    if(a[1]>=b[1]) return 0;
    init();
    int ma=pma[n],mj=pmj[m];
    if(a[pmi[n]]>=b[pmj[m]]||b[pmb[m]]<=a[pma[n]]) return 0;
    return chk1(pmi[n],pmb[m])&&chk2(pmi[n],pmb[m]);
}

int main(){
    scanf("%*d%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++) scanf("%d",&x[i]);
    for(int i=1;i<=m;i++) scanf("%d",&y[i]);
    for(int i=1;i<=n;i++) ta[i]=x[i];
    for(int i=1;i<=m;i++) tb[i]=y[i];
    for(int i=1;i<=n;i++) a[i]=ta[i];
    for(int i=1;i<=m;i++) b[i]=tb[i];
    bool res1=sol();
    swap(n,m);
    for(int i=1;i<=n;i++) a[i]=tb[i];
    for(int i=1;i<=m;i++) b[i]=ta[i];
    bool res2=sol();
    swap(n,m);
    putchar(res1||res2?'1':'0');
    while(q--){
        for(int i=1;i<=n;i++) ta[i]=x[i];
        for(int i=1;i<=m;i++) tb[i]=y[i];
        int kx,ky;
        scanf("%d%d",&kx,&ky);
        while(kx--){
            int p,v;
            scanf("%d%d",&p,&v);
            ta[p]=v;
        }
        while(ky--){
            int p,v;
            scanf("%d%d",&p,&v);
            tb[p]=v;
        }
        for(int i=1;i<=n;i++) a[i]=ta[i];
        for(int i=1;i<=m;i++) b[i]=tb[i];
        bool res1=sol();
        swap(n,m);
        for(int i=1;i<=n;i++) a[i]=tb[i];
        for(int i=1;i<=m;i++) b[i]=ta[i];
        bool res2=sol();
        swap(n,m);
        putchar(res1||res2?'1':'0');
    }
    return 0;
}