自动搬运

查看原文

来自洛谷，原作者为

	云浅知处 喵

搬运于2025-08-24 22:57:56，当前版本为作者最后更新于2024-06-21 19:43:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

首先，注意到对于一组询问，我们只需要关注每个数与 $(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)$，不论怎样，操作总是由两部分构成：

• 用区间 $[l,r]$ 造出来一个 $(T_j,W_j)$。
• 然后无伤通关 $[1,l-1]$ 和 $[r+1,N]$，把这个 $(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]$，那么这两个区间的结果有四种可能：

• $(T_j,\le W_j)+(\le T_j,W_j)$
• $(T_j,\ge W_j)+(\ge T_j,W_j)$
• $(\le T_j,W_j)+(T_j,\le W_j)$
• $(\ge T_j,W_j)+(T_j,\ge W_j)$

不管哪种情况，我们发现总是可以将操作改为：先分别合并出 $[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)$，发现如果它是由两个均不为 $(T_j,\le W_j)$ 的卡牌合并而来，那么唯一的情况就只有 $(\ge T_j,\le W_j)+(T_j,>W_j)$。

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

• 用区间 $[l,r]$ 造出来一个 $(\ge T_j,\le W_j)$。
• 然后无伤通关 $[1,l-1]$ 和 $[r+1,N]$，把这个 $(\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)$ 的卡牌。下面我们证明，这等价于：

• 存在至少一个形如 $(T_j,*)$ 的卡牌，且这个序列能造出 $(\ge 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$ 的卡牌，分以下两种情况：

• $p=k$。这种情况下，我们类似地在左右先进行操作，可以发现总是能保留这个 $(T_j,\le W_j)$。
• $p\neq k$。不妨设 $p<k$，那么我们在右侧正常操作，对于左侧，我们无脑保留 $T_j$（在不关心第二维的情况下，这当然是可以做到的），然后最后把留下来的 $(T_j,*)$ 和 $(\ge T_j,\le W_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;
}