[NOIP2023] 双序列拓展

· · 题解

不知道为什么场上就是认定了这题是不可做题，也同样觉得 T4 不可做，结果拼完 7.5KB 暴力之后会了但是来不及写。只能说打的像个小丑。

首先有一个显然的平方 dp，把转移放在网格图之后相当于限定了 x_i\ge y_j 的位置为障碍，求 (1,1) 和 (n,m) 是否八连通。（y_j\ge x_i 的部分同理，是对称的。）

观察到对于 x_i>x_k，满足 x_k\ge y_j 的 j 一定是满足 x_i\ge y_j 的 j 的子集，因此 (1,1) 和 (n,m) 不连通只有四种情况：

一、二直接判就行了；三、四两种是对称的，只考虑三怎么判断。

枚举 i，要找到最小的 j 满足 y_j\le \min\limits _{k=1}^{i} x_k，相当于找到最小的 j 满足 \min\limits_{k=1}^{j} y_k\le \min\limits _{k=1}^{i} x_k。j 具有单调性，随 i 的增大而增大，因此维护一个指针 j 即可。

全部是赛后没看题解的情况下想的。什么时候正式考试能拼一点，不要天天当四暴力战神呢。

#include<bits/stdc++.h>
typedef int ll;
typedef long double ld;
typedef unsigned long long ull;
#define pii pair<ll,ll>
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define per(i,a,b) for(ll i=(a);i>=(b);--i)
using namespace std;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void write(ll x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
const ll N=5e5+9,INF=2e9;
ll c,n,m,q,x[N],y[N],tx[N],ty[N],px[N],py[N];
void work(ll*x,ll*y,ll n,ll m){
    //x[i]>=y[j] (i,j) obstacle
    if(*max_element(x+1,x+n+1)>=*max_element(y+1,y+m+1))return putchar('0'),void();
    if(*min_element(x+1,x+n+1)>=*min_element(y+1,y+m+1))return putchar('0'),void();
    px[0]=py[0]=INF;
    rep(i,1,n)px[i]=min(px[i-1],x[i]);
    rep(i,1,m)py[i]=min(py[i-1],y[i]);
    ll p=0,c=0;
    rep(i,1,n){
        while(p<=m&&py[p]>px[i])p++,c=max(c,y[p]);
        if(p<=m&&x[i]>=c)return putchar('0'),void();
    }
    px[n+1]=py[m+1]=INF;
    per(i,n,1)px[i]=min(px[i+1],x[i]);
    per(i,m,1)py[i]=min(py[i+1],y[i]);
    p=m+1,c=0;
    per(i,n,1){
        while(p>=1&&py[p]>px[i])p--,c=max(c,y[p]);
        if(p>=1&&x[i]>=c)return putchar('0'),void();
    }
    putchar('1');
}
void solve(){
    if(x[1]==y[1])putchar('0');
    else if(x[1]<y[1])work(x,y,n,m);
    else work(y,x,m,n);
}
int main(){
    c=read(),n=read(),m=read(),q=read();
    rep(i,1,n)tx[i]=read();
    rep(i,1,m)ty[i]=read();
    rep(i,1,n)x[i]=tx[i];
    rep(i,1,m)y[i]=ty[i];
    solve();
    while(q--){
        rep(i,1,n)x[i]=tx[i];
        rep(i,1,m)y[i]=ty[i];
        ll kx=read(),ky=read();
        while(kx--){
            ll a=read(),b=read();
            x[a]=b;
        }
        while(ky--){
            ll a=read(),b=read();
            y[a]=b;
        }
        solve();
    }
    return 0;
}