专栏文章

科技改变生活

qqczrz6v4nhp6u
P10436题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mip27iew
此快照首次捕获于
2025/12/03 04:57
3 个月前
此快照最后确认于
2025/12/03 04:57
3 个月前
查看原文
一个思维量小很多的做法。

Solution

哇又是神秘操作判定合不合法，考虑类似 P12294 搞一个 DFA 出来判定。
但是会遇到问题：字符集的大小实在太大。尝试把字符集缩小到常数级。
注意到对于一组询问 (x,y)(x,y)，只有 aia_i 与 xx 的大小关系和 bib_i 与 yy 的大小关系有用。令 sgn(x)=[x>0]−[x<0]{\rm sgn}(x)=[x>0]-[x<0]（即 x>0x>0 时为 11，x=0x=0 时为 00，x<0x<0 时为 −1-1），则我们可以将 ai←sgn(ai−x),bi←sgn(bi−y)a_i\gets {\rm sgn}(a_i-x),b_i\gets {\rm sgn}(b_i-y)，最后查询能否合出 (0,0)(0,0) 即可。
那么现在的字符集已经小到足够搞一个 DFA 出来了。沿用 P12294 的方法：设阈值 X,ZX,Z，枚举长度 ≤X\le X 的串 x,yx,y，若对于所有长度 ≤Z\le Z 的串 zz 都有 f(x+z)=f(y+z)f(x+z)=f(y+z)（f(s)f(s) 表示串 ss 能否合出 (0,0)(0,0)），则认为 xx 和 yy 等价。每个等价类中任意取出一个长度最小的字符串，按照转移关系即可建出 DFA。经过试验，本题中取 X=4,Z=3X=4,Z=3 即可造出正确的 DFA，此时 DFA 的点数为 2424。
把这个 DFA 表出来，每次询问都在自动机上走即可获得一个 O(nq)O(nq) 的做法，可以获得 7171 分。
然后考虑优化。直接套一个 D2T2 做法应该可以做到 O((n+q)n∣S∣)O((n+q)\sqrt{n|S|})（其中 SS 为 DFA 的状态集合），然而太不优美了。尝试找一些 DFA 的性质。
Observation 1\bf Observation~1：DFA 忽略自环后是 DAG。
Observation 2\bf Observation~2：这个 DAG 的最长路包括 88 个节点。
考虑每次跳出不是自环的一步，根据上面的分析这样至多会跳 88 次，于是我们将问题转化为了区间查满足 ai<x,bi<ya_i<x,b_i<y 的最小的 ii（两个小于号可以独立地变为大于号，不过本质相同故忽略）。直接树套树维护后缀矩形 min⁡\min 即可做到 O(nlog⁡2n+q∣P∣∣Σ∣log⁡2n)O(n\log^2 n+q|P||\Sigma|\log^2 n)，其中 PP 为最长路的状态集合，Σ\Sigma 为字符集。这个看起来能过吗。
然后考虑优化。经过 qbf 提醒考虑每次把所有点跳一步。对 aa 那维离线扫描线，以下标的线段树并维护 min⁡bi\min b_i，每次线段树二分即可在 O(log⁡n)O(\log n) 时间内找出转化后问题的答案。
于是原问题就被我们做到了 O((n+q)∣P∣∣Σ∣log⁡n)O((n+q)|P||\Sigma|\log n)，若可持久化还可做到 O(n∣Σ∣log⁡n+q∣P∣∣Σ∣log⁡n)O(n|\Sigma|\log n+q|P||\Sigma|\log n)，虽然需要卡常但已经足够通过了。这不神奇吗？？？

Code

造自动机代码：
CPP
bool Mst;
#include<bits/stdc++.h>
using namespace std;
using ui=unsigned int;
using ll=long long;
using ull=unsigned long long;
using i128=__int128;
using u128=__uint128_t;
using pii=pair<int,int>;
#define fi first
#define se second
constexpr int N=2005,X=4,Z=3;
int mrg1[9][9],mrg2[9][9];
bool f[48427562][9];bool ck[48427562];char bel[48427562];
int del[10],pw[10],tot;pii s[N];int to[N][9];bool val[N];
bool Med;
int main(){
	cerr<<abs(&Mst-&Med)/1048576.0<<endl;
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	for(int i=0;i<9;i++)
		for(int j=0;j<9;j++){
			mrg1[i][j]=max(i/3,j/3)*3+max(i%3,j%3);
			mrg2[i][j]=min(i/3,j/3)*3+min(i%3,j%3);
		}
	pw[0]=1;
	for(int i=1;i<=X+Z;i++)pw[i]=pw[i-1]*9;
	for(int i=1;i<=X+Z;i++)del[i]=del[i-1]+pw[i-1];
	for(int i=0;i<9;i++)f[del[1]+i][i]=1;
	ck[del[1]+4]=1;
	for(int i=2;i<=X+Z;i++){
		for(int r=0;r<pw[i];r++){
			auto &arr=f[del[i]+r];
			for(int j=1;j<i;j++){
				int p=r%pw[j],q=r/pw[j];
				for(int x=0;x<9;x++)if(f[del[j]+p][x])
					for(int y=0;y<9;y++)if(f[del[i-j]+q][y])
						arr[mrg1[x][y]]=arr[mrg2[x][y]]=1;
			}
			ck[del[i]+r]=arr[4];
		}
	}
	for(int i=0;i<=X;i++)
		for(int r=0;r<pw[i];r++){
			bel[del[i]+r]=-1;
			for(int o=1;o<=tot;o++){
				int j=s[o].fi,p=s[o].se;bool ok=1;
				for(int k=0;k<=Z;k++){
					for(int q=0;q<pw[k];q++)
						if(ck[del[i+k]+r+q*pw[i]]!=ck[del[j+k]+p+q*pw[j]]){
							ok=0;
							break;
						}
					if(!ok)break;
				}
				if(ok){
					bel[del[i]+r]=o;
					break;
				}
			}
			if(!~bel[del[i]+r]){
				++tot;
				bel[del[i]+r]=tot;
				s[tot]=make_pair(i,r);
			}
		}
	for(int i=1;i<=tot;i++){
		int j=s[i].fi,r=s[i].se;
		val[i]=ck[del[j]+r];
		for(int k=0;k<9;k++)
			to[i][k]=bel[del[j+1]+r+k*pw[j]];
	}
	cout<<tot<<'\n';
	cout<<"constexpr bool val[]={0,";
	for(int i=1;i<=tot;i++)cout<<val[i]<<",}"[i==tot];
	cout<<";\n";
	cout<<"constexpr int to[][9]={\n";
	cout<<"    {},\n";
	for(int i=1;i<=tot;i++){
		cout<<"    {";
		for(int j=0;j<9;j++)
			cout<<to[i][j]<<",}"[j==8];
		if(i<tot)cout<<',';
		cout<<'\n';
	}
	cout<<"};\n";
	return 0;
}
AC 代码（复杂度 O((n+q)∣P∣∣Σ∣log⁡n)O((n+q)|P||\Sigma|\log n)）：
CPP
bool Mst;
#include<bits/stdc++.h>
using namespace std;
using ui=unsigned int;
using ll=long long;
using ull=unsigned long long;
using i128=__int128;
using u128=__uint128_t;
using pii=pair<int,int>;
#define fi first
#define se second
constexpr int N=5e5+5,Q=2e5+5,T=N+Q,INF=1e9;
constexpr bool val[]={0,0,0,0,0,0,1,0,0,0,0,1,0,1,0,0,0,0,1,0,0,0,0,0,0};
constexpr int to[][9]={
	{}, // 0
	{2,3,4,5,6,7,8,9,2}, // 1
	{2,3,10,5,6,7,12,9,2}, // 2
	{3,3,3,18,18,14,15,15,3}, // 3
	{10,3,4,7,20,7,10,3,10}, // 4
	{5,13,16,5,13,16,5,19,5}, // 5
	{11,11,17,11,11,11,22,11,11}, // 6
	{7,14,7,16,18,7,16,18,7}, // 7
	{12,9,12,5,21,5,8,9,12}, // 8
	{9,15,15,19,13,13,9,9,9}, // 9
	{10,3,10,16,6,7,23,15,10}, // 10
	{11,11,11,11,11,11,11,11,11}, // 11
	{12,15,23,5,6,16,12,9,12}, // 12
	{11,11,11,11,11,11,22,11,11}, // 13
	{14,14,14,18,18,14,18,18,14}, // 14
	{15,15,15,11,11,11,15,15,15}, // 15
	{16,11,16,16,11,16,16,11,16}, // 16
	{11,11,17,11,11,11,11,11,11}, // 17
	{11,11,17,11,11,11,11,11,11}, // 18
	{19,13,13,19,13,13,19,19,19}, // 19
	{20,14,20,18,18,14,24,18,20}, // 20
	{21,13,24,19,13,13,21,19,21}, // 21
	{11,11,11,11,11,11,22,11,11}, // 22
	{23,15,23,16,6,16,23,15,23}, // 23
	{24,11,24,11,11,11,24,11,24} // 24
};
int _id,_Test,n,q,a[N],b[N],x[Q],y[Q];
pii cur[Q],nxt[Q];
bool mark[Q];
int nx[T],lx,ny[T],ly;
vector<int> va[T],vb[T],vx[T],vy[T];
int L[N<<2],R[N<<2],M[N<<2],Min[N<<2],ver[N];
void build(int l,int r,int p=1){
	L[p]=l,R[p]=r,M[p]=(l+r)>>1,Min[p]=INF;
	if(l==r){
		ver[l]=p;
		return;
	}
	build(L[p],M[p],p<<1);
	build(M[p]+1,R[p],p<<1|1);
}
inline void ins(int x,int v){
	for(int p=ver[x];p;p>>=1)
		Min[p]=min(Min[p],v);
}
int vec[2][N],len[2];
inline void clr(){
	vec[0][len[0]=1]=1;
	for(bool op=0;len[op];op^=1){
		len[!op]=0;
		for(int i=1;i<=len[op];i++){
			int p=vec[op][i];
			if(Min[p]==INF)continue;
			Min[p]=INF;
			if(L[p]<R[p]){
				vec[!op][++len[!op]]=p<<1;
				vec[!op][++len[!op]]=p<<1|1;
			}
		}
	}
}
inline int qry(int l,int r,int v,int p=1){
	if(l>r||Min[p]>=v)return n+1;
	if(L[p]==R[p])return L[p];
	if(r<=M[p])return qry(l,r,v,p<<1);
	if(M[p]<l)return qry(l,r,v,p<<1|1);
	int res=qry(l,r,v,p<<1);
	if(res<=n)return res;
	return qry(l,r,v,p<<1|1);
}
inline bool ck(int x,int k){return to[x][k]!=x;}
inline void ckmin(pii &a,const pii &b){if(a.fi>b.fi)a=b;}
int pos[N];
void solve0(){ // 4
	for(int i=1;i<=lx;i++){
		if(!va[i].size()||!vx[i].size())continue;
		sort(vx[i].begin(),vx[i].end(),[&](int x,int y){
			return cur[x].fi<cur[y].fi;
		});
		const auto &v0=va[i],&v1=vx[i];
		int l=v0.size()-1,r=v1.size()-1;
		while(r>=0){
			while(l>=0&&v0[l]>=cur[v1[r]].fi)
				pos[b[v0[l]]]=v0[l],l--;
			int o=v1[r];
			if(!mark[o]&&ck(cur[o].se,4))
				ckmin(nxt[o],make_pair(pos[y[o]],4));
			r--;
		}
		while((++l)<(int)v0.size())
			pos[b[v0[l]]]=n+1;
	}
}
void solve1(){ // 1, 3, 5, 7
	for(int i=1;i<=lx;i++){
		if(!va[i].size()||!vx[i].size())continue;
		const auto &v0=va[i],&v1=vx[i];
		for(const auto &o:v0)
			ins(o,b[o]);
		for(const auto &o:v1)
			if(!mark[o]&&ck(cur[o].se,3))
				ckmin(nxt[o],make_pair(qry(cur[o].fi,n,y[o]),3));
		clr();
		for(const auto &o:v0)
			ins(o,ly-b[o]+1);
		for(const auto &o:v1)
			if(!mark[o]&&ck(cur[o].se,5))
				ckmin(nxt[o],make_pair(qry(cur[o].fi,n,ly-y[o]+1),5));
		clr();
	}
	
	for(int i=1;i<=ly;i++){
		if(!vb[i].size()||!vy[i].size())continue;
		const auto &v0=vb[i],&v1=vy[i];
		for(const auto &o:v0)
			ins(o,a[o]);
		for(const auto &o:v1)
			if(!mark[o]&&ck(cur[o].se,1))
				ckmin(nxt[o],make_pair(qry(cur[o].fi,n,x[o]),1));
		clr();
		for(const auto &o:v0)
			ins(o,lx-a[o]+1);
		for(const auto &o:v1)
			if(!mark[o]&&ck(cur[o].se,7))
				ckmin(nxt[o],make_pair(qry(cur[o].fi,n,lx-x[o]+1),7));
		clr();
	}
}
void solve2(){ // 0, 2, 6, 8
	for(int i=1;i<=lx;i++){
		const auto &v0=va[i],&v1=vx[i];
		for(const auto &o:v1)
			if(!mark[o]&&ck(cur[o].se,0))
				ckmin(nxt[o],make_pair(qry(cur[o].fi,n,y[o]),0));
		for(const auto &o:v0)
			ins(o,b[o]);
	}
	clr();
	
	for(int i=1;i<=lx;i++){
		const auto &v0=va[i],&v1=vx[i];
		for(const auto &o:v1)
			if(!mark[o]&&ck(cur[o].se,2))
				ckmin(nxt[o],make_pair(qry(cur[o].fi,n,ly-y[o]+1),2));
		for(const auto &o:v0)
			ins(o,ly-b[o]+1);
	}
	clr();
	
	for(int i=lx;i>=1;i--){
		const auto &v0=va[i],&v1=vx[i];
		for(const auto &o:v1)
			if(!mark[o]&&ck(cur[o].se,6))
				ckmin(nxt[o],make_pair(qry(cur[o].fi,n,y[o]),6));
		for(const auto &o:v0)
			ins(o,b[o]);
	}
	clr();
	
	for(int i=lx;i>=1;i--){
		const auto &v0=va[i],&v1=vx[i];
		for(const auto &o:v1)
			if(!mark[o]&&ck(cur[o].se,8))
				ckmin(nxt[o],make_pair(qry(cur[o].fi,n,ly-y[o]+1),8));
		for(const auto &o:v0)
			ins(o,ly-b[o]+1);
	}
	clr();
}
void Solve(){
	cin>>n>>q;
	lx=ly=0;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i];
		nx[++lx]=a[i];
		ny[++ly]=b[i];
	}
	for(int i=1;i<=q;i++){
		cin>>x[i]>>y[i];
		nx[++lx]=x[i];
		ny[++ly]=y[i];
		cur[i]=make_pair(1,1),mark[i]=0;
	}
	sort(nx+1,nx+lx+1),lx=unique(nx+1,nx+lx+1)-nx-1;
	sort(ny+1,ny+ly+1),ly=unique(ny+1,ny+ly+1)-ny-1;
	for(int i=1;i<=n;i++){
		a[i]=lower_bound(nx+1,nx+lx+1,a[i])-nx;
		b[i]=lower_bound(ny+1,ny+ly+1,b[i])-ny;
	}
	for(int i=1;i<=q;i++){
		x[i]=lower_bound(nx+1,nx+lx+1,x[i])-nx;
		y[i]=lower_bound(ny+1,ny+ly+1,y[i])-ny;
	}
	for(int i=1;i<=lx;i++){
		va[i].clear(),va[i].shrink_to_fit();
		vx[i].clear(),vx[i].shrink_to_fit();
	}
	for(int i=1;i<=ly;i++){
		vb[i].clear(),vb[i].shrink_to_fit();
		vy[i].clear(),vy[i].shrink_to_fit();
	}
	for(int i=1;i<=n;i++){
		va[a[i]].emplace_back(i);
		vb[b[i]].emplace_back(i);
	}
	for(int i=1;i<=q;i++){
		vx[x[i]].emplace_back(i);
		vy[y[i]].emplace_back(i);
	}
	for(int i=1;i<=ly;i++)pos[i]=n+1;
	build(1,n);
	for(int t=1;t<8;t++){
		bool flag=0;
		for(int i=1;i<=q;i++){
			nxt[i]=make_pair(n+1,9);
			flag|=!mark[i];
		}
		if(!flag)break;
		solve0(),solve1(),solve2();
		for(int i=1;i<=q;i++)if(!mark[i]){
			if(nxt[i].fi<=n)
				cur[i]=make_pair(nxt[i].fi+1,to[cur[i].se][nxt[i].se]);
			else
				mark[i]=1;
		}
	}
	for(int i=1;i<=q;i++)
		if(val[cur[i].se])
			cout<<i<<' ';
	cout<<'\n';
}
bool Med;
int main(){
	cerr<<abs(&Mst-&Med)/1048576.0<<endl;
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	_Test=1;
	while(_Test--)Solve();
	return 0;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...