题解：P10436 [JOISC 2024] 卡牌收集

· · 题解

首先，注意到对于一组询问，我们只需要关注每个数与 (T_j,W_j) 的相对大小关系。这一共有 9 种情况，于是我们直接做区间 DP，设一个形如 f(l,r,0/1/2,0/1/2) 的状态，即可得到 O(N^3M) 的做法；进一步使用 bitset 优化可以做到 O(\frac{N^3M}{w})，但是无法通过（甚至 N=2000,M=10 可能都无法通过）。

我们考虑想要得到一个 (T_j,W_j)，不论怎样，操作总是由两部分构成：

考虑能够保持到最后的条件。我们发现，如果某一侧全部都形如 (\ge T_j,<W_j)，或者全部都形如 (\le T_j,>W_j)，那么一定是不可能保持到最后的。否则，我们证明一定可以。

如果不是全部形如以上两种形态，那么相当于至少存在一个 (\le T_j,\le W_j) 或 (\ge T_j,\ge W_j)。我们在这一侧一直取 min 或取 max 就可以保留这个 (\le T_j,\le W_j) 或 (\ge T_j,\ge W_j)。最后，进行一次取 min 或取 max 即可。

现在我们考虑，用区间 [l,r] 造出了 (T_j,W_j)，如果是直接得到的也就是 l=r，这种情况是好判断的。

如果这个过程也经历了至少一次合并，我们设最后一步合并的两个区间为 [l,m]+[m+1,r]，那么这两个区间的结果有四种可能：

不管哪种情况，我们发现总是可以将操作改为：先分别合并出 [l,m] 和 [m+1,r]，然后把 [1,l-1] 得到的 (\le T_j,\le W_j) 或 (\ge T_j,\ge W_j) 合并到 [l,m] 里面，并保持形态不变；把 [r+1,N] 得到的 (\le T_j,\le W_j) 或 (\ge T_j,\ge W_j) 合并到 [m+1,r] 里面，最后再把 [1,m],[m+1,N] 合并。

于是，我们只需要考虑最后一步操作形如 [1,m]+[m+1,N] 的情形。

现在，我们可以把原问题转化为 O(N) 次判断如下的问题：

由对称性，其他情况也是类似的。

我们考虑想要造出一个 (T_j,\le W_j)，发现如果它是由两个均不为 (T_j,\le W_j) 的卡牌合并而来，那么唯一的情况就只有 (\ge T_j,\le W_j)+(T_j,>W_j)。

我们先来考虑，如何一个序列能否造出 (\ge T_j,\le W_j)。类似地，这个过程也由两部分组成：

这时我们发现，(\ge T_j,\le W_j) 不可能由两个均不为 (\ge T_j,\le W_j) 的卡牌合并而来。于是，唯一的情况只有：原序列中存在至少一个能保留到最后的 (\ge T_j,\le W_j)。

现在考虑一个 (\ge T_j,\le W_j) 能保留到最后的条件。发现如果某一侧全都是 (<T_j,>W_j) 那么肯定无解；否则这一侧必须存在 (\ge T_j,*) 或者 (*,\le W_j)（其中 * 表示任取）。对于这种情况，同理我们也可以先在这一边一直取 min 或 max 保留这个卡牌，最后进行一次操作留下 (<T_j,>W_j)。

现在，我们可以在 O(N) 时间内判断一个长为 N 的序列能否造出一个形如 (\ge T_j,\le W_j) 的卡牌。

回到原问题，考虑如何造出一个 (T_j,\le W_j) 的卡牌。下面我们证明，这等价于：

首先，必要性是显然的。对于充分性，假设我们使用了某个 k 满足 (S_k,V_k)（这里 S,V 是给定的初始序列）一开始就形如 (\ge T_j,\le W_j)，且两侧均存在至少一个 (\ge T_j,*) 或 (*,\le W_j)。

设 p 是序列中任意一个满足 S_p=T_j 的卡牌，分以下两种情况：

综上命题得证。

于是，我们可以在 O(N) 的时间内判断一个长为 N 的序列能否造出一个形如 (T_j,\le W_j) 的卡牌。对于每组询问我们都需要做 N 遍上述过程，于是总的时间复杂度为 O(N^2M)。

下面就是我们熟悉的部分了！相信在得到最后的条件后，作为 CN OIer 你的内心已经蠢蠢欲动了（雾

还是不妨设最后一步合并形如 (T_j,\le W_j)+(\le T_j,W_j)。

我们找到第一个形如 (T_j,*) 的卡牌 x，以及第一个形如 (\ge T_j,\le W_j) 且左侧存在至少一个 (\ge T_j,*) 或 (*,\le W_j)，或者左侧没有任何卡牌的卡牌 y。找到 y 右侧第一个形如 (\ge T_j,*) 或 (*,\le W_j) 的卡牌 z，那么能合成 (T_j,\le W_j) 的前缀只有 [1,y]（此时还需要 x\le y），以及所有的 [1,p]，其中 p\ge \max(x,z)。

同理我们也可以找到所有的后缀使得其能构造出 (\le T_j,W_j)。现在相当于给出 p_1,q_1,p_2,q_2，判断是否存在一个 i 满足 i\in \{p_1\}\cup[q_1,n],i+1\in \{p_2\}\cup [1,p_1]。分四种情况讨论即可。

对于找到这个前缀，可以发现只需要每组询问只需要做一次「查询 p 之后第一个 (\ge u,\le v) 的卡牌的位置」这样的询问，还有两次查询 (\ge u,*) 和 (*,\le v) 的询问。后两个都容易通过线段树二分或 ST 表解决，对于第一个，我们把询问按 u 排序后扫描线，那么只需要线段树二分同时维护单点修改即可。

最后还需要考虑直接拿着序列中一个 (T_j,W_j) 走到最后的情形。考虑把询问记忆化，每次枚举序列中的所有 (T_j,W_j) 并一一判断其前后是否分别都有一个 (\ge T_j,\ge W_j) 或 (\le T_j,\le W_j)。注意这并不是三维偏序，因为我们只需要判断存在性。同理按照 T 从小到大插入，每次线段树二分即可。

综上，本题在 O((N+M)\log N) 时间内解决。带有 8 倍常数，因为有四种情况且每次都要对前缀后缀同时算。

#include<bits/stdc++.h>

#define ll long long
#define mk make_pair
#define fi first
#define se second

using namespace std;

inline int read(){
    int x=0,f=1;char c=getchar();
    for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
    for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
    return x*f;
}

template<typename T>void cmax(T &x,T v){x=max(x,v);}
template<typename T>void cmin(T &x,T v){x=min(x,v);}

const int N=4e5+5;
int n,m,a[N],b[N],val[N],qx[N],qy[N];
vector<pair<int,int> >ques[N];
bool ans[N];
int st[N],ed[N];

struct sgt{
    int mx[N<<2],mn[N<<2];
    #define ls(p) (p<<1)
    #define rs(p) (p<<1|1)
    void pushup(int p){mx[p]=max(mx[ls(p)],mx[rs(p)]),mn[p]=min(mn[ls(p)],mn[rs(p)]);}
    void build(int l,int r,int p){
        if(l==r)return mn[p]=mx[p]=val[l],void();
        int mid=(l+r)>>1;
        build(l,mid,ls(p)),build(mid+1,r,rs(p)),pushup(p);
    }
    int geq(int l,int r,int v,int ql,int qr,int p){ // min i in [l,r] s.t. val[i]>=v
        if(mx[p]<v||l>r)return n+1;
        if(ql==qr)return ql;
        int mid=(ql+qr)>>1,ret=n+1;
        if(l<=mid)ret=geq(l,r,v,ql,mid,ls(p));
        if(ret!=n+1)return ret;
        return geq(l,r,v,mid+1,qr,rs(p));
    }
    int leq(int l,int r,int v,int ql,int qr,int p){ // min i in [l,r] s.t. val[i]<=v
        if(mn[p]>v||l>r)return n+1;
        if(ql==qr)return ql;
        int mid=(ql+qr)>>1,ret=n+1;
        if(l<=mid)ret=leq(l,r,v,ql,mid,ls(p));
        if(ret!=n+1)return ret;
        return leq(l,r,v,mid+1,qr,rs(p));
    }
    void mdf(int x,int v,int ql,int qr,int p){
        if(ql==qr)return mx[p]=mn[p]=v,void();
        int mid=(ql+qr)>>1;
        if(x<=mid)mdf(x,v,ql,mid,ls(p));
        else mdf(x,v,mid+1,qr,rs(p));
        pushup(p);
    }
}T1,T2,T3;

int pos[N],V,pv[N],q1[N],q2[N],qq[N];
vector<int>vals[N];
void solve1(){
    for(int i=1;i<=n;i++)val[i]=a[i];T1.build(1,n,1);
    for(int i=1;i<=n;i++)val[i]=b[i];T2.build(1,n,1);
    for(int i=1;i<=n;i++)val[i]=V+1;T3.build(1,n,1);

    for(int i=1;i<=V;i++)pv[i]=n+1,vector<int>().swap(vals[i]);
    for(int i=1;i<=n;i++)cmin(pv[a[i]],i),vals[a[i]].emplace_back(i);

    for(int u=V;u>=1;u--){
        for(int j:vals[u])T3.mdf(j,b[j],1,n,1);
        for(auto [v,id]:ques[u]){
            int p=0;
            if(a[1]>=u&&b[1]<=v)p=1;
            else{
                p=min(T1.geq(1,n,u,1,n,1),T2.leq(1,n,v,1,n,1));
                if(p>n){pos[id]=n+1,qq[id]=0;continue;}
                p=T3.leq(p+1,n,v,1,n,1);
                if(p>n){pos[id]=n+1,qq[id]=0;continue;}
            }
            int q=min(T1.geq(p+1,n,u,1,n,1),T2.leq(p+1,n,v,1,n,1));
            pos[id]=max(q,pv[u]);
            if(pv[u]<=p)qq[id]=p;
            else qq[id]=0;
        }
    }
}

void solve(){
    for(int i=1;i<=V;i++)vector<pair<int,int> >().swap(ques[i]);
    for(int i=1;i<=m;i++)ques[qx[i]].emplace_back(mk(qy[i],i));
    solve1();
    for(int i=1;i<=m;i++)st[i]=pos[i],q1[i]=qq[i];

    reverse(a+1,a+n+1),reverse(b+1,b+n+1);
    for(int i=1;i<=n;i++)swap(a[i],b[i]);for(int i=1;i<=m;i++)swap(qx[i],qy[i]);

    for(int i=1;i<=V;i++)vector<pair<int,int> >().swap(ques[i]);
    for(int i=1;i<=m;i++)ques[qx[i]].emplace_back(mk(qy[i],i));
    solve1();
    for(int i=1;i<=m;i++)ed[i]=n-pos[i]+1,q2[i]=n-qq[i]+1;

    for(int i=1;i<=m;i++){
        ans[i]|=(st[i]<ed[i]);
        if(q1[i]!=0)ans[i]|=(q1[i]<ed[i]);
        if(q2[i]!=n+1)ans[i]|=(st[i]<q2[i]);
        if(q1[i]!=0&&q2[i]!=n+1)ans[i]|=(q1[i]==q2[i]-1);
    }

    reverse(a+1,a+n+1),reverse(b+1,b+n+1);
    for(int i=1;i<=n;i++)swap(a[i],b[i]);for(int i=1;i<=m;i++)swap(qx[i],qy[i]);
}

bool s1[N],s2[N],t1[N],t2[N],can[N];
map<int,vector<int> >Map[N];
map<int,bool>res[N];

void solve_case1(){
    vector<vector<int> >ps(V+1);
    for(int i=1;i<=n;i++)ps[a[i]].emplace_back(i);
    for(int i=1;i<=n;i++)val[i]=n+1;T1.build(1,n,1);
    for(int i=1;i<=V;i++){
        for(int j:ps[i])T1.mdf(j,b[j],1,n,1);
        for(int j:ps[i])s1[j]=(T1.leq(1,n,b[j],1,n,1)<=j-1);
    }

    for(int i=1;i<=n;i++)val[i]=-1;T1.build(1,n,1);
    for(int i=V;i>=1;i--){
        for(int j:ps[i])T1.mdf(j,b[j],1,n,1);
        for(int j:ps[i])s2[j]=(T1.geq(1,n,b[j],1,n,1)<=j-1);
    }
    for(int i=1;i<=V;i++)ps[i].clear();

    reverse(a+1,a+n+1),reverse(b+1,b+n+1);
    for(int i=1;i<=n;i++)ps[a[i]].emplace_back(i);
    for(int i=1;i<=n;i++)val[i]=n+1;T1.build(1,n,1);
    for(int i=1;i<=V;i++){
        for(int j:ps[i])T1.mdf(j,b[j],1,n,1);
        for(int j:ps[i])t1[j]=(T1.leq(1,n,b[j],1,n,1)<=j-1);
    }

    for(int i=1;i<=n;i++)val[i]=-1;T1.build(1,n,1);
    for(int i=V;i>=1;i--){
        for(int j:ps[i])T1.mdf(j,b[j],1,n,1);
        for(int j:ps[i])t2[j]=(T1.geq(1,n,b[j],1,n,1)<=j-1);
    }
    for(int i=1;i<=V;i++)ps[i].clear();

    reverse(t1+1,t1+n+1),reverse(t2+1,t2+n+1),reverse(a+1,a+n+1),reverse(b+1,b+n+1);
    for(int i=1;i<=n;i++)can[i]=((s1[i]|s2[i]|(i==1))&(t1[i]|t2[i]|(i==n)));
    for(int i=1;i<=V;i++)Map[a[i]][b[i]].emplace_back(i);

    for(int i=1;i<=m;i++){
        if(res[qx[i]].find(qy[i])!=res[qx[i]].end()){ans[i]|=res[qx[i]][qy[i]];continue;}
        for(int j:Map[qx[i]][qy[i]])if(can[j]){ans[i]=res[qx[i]][qy[i]]=1;break;}
    }
}

signed main(void){

#ifndef ONLINE_JUDGE
    freopen("01-03.in","r",stdin);
    // freopen("in.txt","r",stdin);
#endif

    n=read(),m=read();
    for(int i=1;i<=n;i++)a[i]=read(),b[i]=read();
    for(int i=1;i<=m;i++)qx[i]=read(),qy[i]=read();

    vector<int>lsh(n+m);
    for(int i=1;i<=n;i++)lsh[i-1]=a[i];
    for(int i=1;i<=m;i++)lsh[i+n-1]=qx[i];
    sort(lsh.begin(),lsh.end());
    int V1=unique(lsh.begin(),lsh.end())-lsh.begin();lsh.resize(V1);
    for(int i=1;i<=n;i++)a[i]=lower_bound(lsh.begin(),lsh.end(),a[i])-lsh.begin()+1;
    for(int i=1;i<=m;i++)qx[i]=lower_bound(lsh.begin(),lsh.end(),qx[i])-lsh.begin()+1;

    lsh.resize(n+m);    
    for(int i=1;i<=n;i++)lsh[i-1]=b[i];
    for(int i=1;i<=m;i++)lsh[i+n-1]=qy[i];
    sort(lsh.begin(),lsh.end());
    int V2=unique(lsh.begin(),lsh.end())-lsh.begin();lsh.resize(V2);
    for(int i=1;i<=n;i++)b[i]=lower_bound(lsh.begin(),lsh.end(),b[i])-lsh.begin()+1;
    for(int i=1;i<=m;i++)qy[i]=lower_bound(lsh.begin(),lsh.end(),qy[i])-lsh.begin()+1;
    V=max(V1,V2);

    solve_case1();

    solve();

    for(int i=1;i<=n;i++)swap(a[i],b[i]);
    for(int i=1;i<=m;i++)swap(qx[i],qy[i]);
    solve();

    for(int i=1;i<=n;i++)a[i]=V-a[i]+1,b[i]=V-b[i]+1;
    for(int i=1;i<=m;i++)qx[i]=V-qx[i]+1,qy[i]=V-qy[i]+1;
    solve();

    for(int i=1;i<=n;i++)swap(a[i],b[i]);
    for(int i=1;i<=m;i++)swap(qx[i],qy[i]);
    solve();

    for(int i=1;i<=m;i++)if(ans[i])cout<<i<<" ";puts("");

    return 0;
}