自动搬运

查看原文

来自洛谷，原作者为

	Rainbow_qwq **

搬运于2025-08-24 23:09:34，当前版本为作者最后更新于2025-02-09 22:05:49，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

下面把 $r\to r-1$。则问题转化为：选择所有被 $[ql,qr]$ 包含的区间，判断是否能覆盖 $[ql,qr]$ 内的所有整点。

下称一个操作的范围为 $[ql,qr,tl,tr]$（区间，时间区间），一个询问为 $[ql,qr,t]$。

先对序列分治，计算所有跨过 $mid$ 的询问。

考虑先算跨过 $mid$ 的区间的贡献。对于询问 $[ql,qr,t]$，能覆盖到的最小位置 $x$ 就是存在一个操作 $[x,r,tl,tr]$ 使得 $x\in [ql,mid],r\le qr,t\in [tl,tr]$。对时间维度扫描线，线段树二分即可。

然后考虑所有在两边的区间，能不能把剩下的空隙填上。假设考虑左边，我们对时间轴开一个线段树，扫描序列维度（$i=l\to mid$）。

每次扫到一个询问就放在线段树上，维护当前这个询问的右端点到了哪里。扫到一个操作就是区间取 max。做完 $[i,r]$ 的所有操作后，不断取线段树上最小值，如果 $<i$ 了就弹掉。

时间复杂度 $O(q\log^2 q)$。

struct Max{
	int x;
	Max (int xx=-inf){
		x=xx;
	}
};
Max operator +(Max a,Max b){
	return Max(max(a.x,b.x));
}

struct Min{
	int x;
	Min (int xx=inf){
		x=xx;
	}
};
Min operator +(Min a,Min b){
	return Min(min(a.x,b.x));
}

struct opMin{
	int x;
	opMin (int xx=inf){
		x=xx;
	}
};

struct opMax{
	int x;
	opMax (int xx=-inf){
		x=xx;
	}
};

void operator +=(opMax &a,opMax b){
	a.x=max(a.x,b.x);
}
void operator +=(opMin &a,opMin b){
	a.x=min(a.x,b.x);
}

void operator +=(Min &a,opMax b){
	a.x=max(a.x,b.x);
}
void operator +=(Max &a,opMin b){
	a.x=min(a.x,b.x);
}

int n,q,m,m2;
int qwq[maxn];
int ql[maxn],qr[maxn],dl[maxn],tl[maxn],tr[maxn],tim[maxn];

struct node{
	int ql,qr,tl,tr;
};

int fid[maxn];

int c[maxn];
bool ask(int l,int r){
	For(i,l-1,r+1) c[i]=0;
	For(i,1,m) if(!dl[i]) {
		if(ql[i]>=l && qr[i]<=r) ++c[ql[i]],--c[qr[i]+1];
	}
	For(i,l,r) {
		c[i]+=c[i-1];
		if(!c[i]) return 0;
	}
	return 1;
}

bool res[maxn];

int dest(vector<node>&ts,vector<node>&qs){
	vi tmp;
	for(auto [ql,qr,tl,tr]:ts) tmp.pb(tl),tmp.pb(tr);
	for(auto [ql,qr,tl,tr]:qs) tmp.pb(tl);
	sort(ALL(tmp));
	tmp.erase(unique(ALL(tmp)),tmp.end());
	auto V=[&](int x){
		x=lower_bound(ALL(tmp),x)-tmp.begin();
		return x+1;
	};
	for(auto &[ql,qr,tl,tr]:ts) tl=V(tl),tr=V(tr);
	for(auto &[ql,qr,tl,tr]:qs) tl=V(tl);
	return tmp.size();
}

multiset<int>s[maxn];

vi in[maxn],ot[maxn],qq[maxn];

int tol[maxn],tor[maxn];
int qid[maxn];

int t3[maxn],t4[maxn];

void solve(int l,int r,vector<node>ts,vector<node>qs)
{
	if(!SZ(qs)) return;
	
//	cout<<"solve "<<l<<" "<<r<<endl;
	
	int m=dest(ts,qs);
	int mid=l+r>>1;
	
//	cout<<"m: "<<m<<endl;
	
	segt1<Min>T1;
	segt1<Max>T2;
	
	vector<node>QL,QR,TL,TR;
	
	For(i,1,m) s[i].clear(),in[i].clear(),ot[i].clear(),qq[i].clear();
	
	For(i,0,SZ(ts)-1){
		auto [ql,qr,tl,tr]=ts[i];
		if(ql<=mid && qr>mid) in[tl].pb(i),ot[tr].pb(i);
		else if(qr<=mid) TL.pb(ts[i]);
		else TR.pb(ts[i]);
	}
	bool hav=0;
	For(i,0,SZ(qs)-1){
		auto [ql,qr,tl,tr]=qs[i];
		if(ql<=mid && qr>mid) qq[tl].pb(i),tol[tr]=mid+1,tor[tr]=mid;
		else if(qr<=mid) QL.pb(qs[i]);
		else QR.pb(qs[i]);
	}
	
	T1.init(mid-l+1);
	T2.init(r-mid);
	
	auto gval=[&](int x){
		if(x<=mid){
			return s[x].empty()? inf:*s[x].begin();
		}else{
			return s[x].empty()?-inf:*s[x].rbegin();
		}
	};
	
	auto upd1=[&](int x){
		if(x<=mid){
			T1.upd(x-l+1,{gval(x)});
		}else{
			T2.upd(x-mid,{gval(x)});
		}
	};
	
	For(i,1,m){
		for(auto id:in[i]){
			auto [ql,qr,tl,tr]=ts[id];
			s[ql].insert(qr);
			s[qr].insert(ql);
			upd1(ql);
			upd1(qr);
		}
		for(auto id:qq[i]){
			auto [ql,qr,tl,ii]=qs[id];
		//	cout<<"ID "<<id<<endl;
			tol[ii]=T1.findL(ql-l+1,mid-l+1,[&](Min t){
				return t.x<=qr;
			});
			tor[ii]=T2.findR(1,qr-mid,[&](Max t){
				return t.x>=ql;
			});
			tol[ii]+=l-1;
			tor[ii]+=mid;
			if(!(tol[ii]>=l && tol[ii]<=mid)) tol[ii]=mid+1;
			if(!(tor[ii]>=mid+1 && tor[ii]<=r)) tor[ii]=mid;
		}
		for(auto id:ot[i]){
			auto [ql,qr,tl,tr]=ts[id];
		//	cout<<"del: "<<ql<<" "<<qr<<endl;
			s[ql].erase(s[ql].find(qr));
			s[qr].erase(s[qr].find(ql));
		//	cout<<"done.\n";
			upd1(ql);
			upd1(qr);
		}
	}
	
	For(i,0,m) in[i].clear(),ot[i].clear(),qq[i].clear();
	
//	cout<<"QWQ\n";
	
	segt<Min,opMax>T3;
	segt<Max,opMin>T4;
	
	T3.init(m);
	T4.init(m);
	For(i,l,r) in[i].clear(),qq[i].clear();
    
	For(i,0,SZ(TL)-1){
		auto [ql,qr,tl,tr]=TL[i];
		in[ql].pb(i);
	}
	For(i,0,SZ(qs)-1){
		auto [ql,qr,tl,tr]=qs[i];
		if(ql<=mid && qr>mid) qq[ql].pb(i),qq[qr].pb(i);
	}
	For(i,l,mid){
		for(auto id:qq[i]){
			auto [ql,qr,tl,ii]=qs[id];
			qid[tl]=ii;
			T3.upd(tl,{i-1});
		}
		for(auto id:in[i]){
			auto [ql,qr,tl,tr]=TL[id];
			T3.mdf(tl,tr,{qr});
		}
		while(1){
			int p=T3.findL(1,m,[&](Min t){
				return t.x<i;
			});
			if(!(p>=1&&p<=m)) break;
			int ii=qid[p];
			if(i<tol[ii]) res[ii]=0;
			T3.upd(p,{inf});
		}
	}
	For(i,l,mid) in[i].clear(),qq[i].clear();
	
	For(i,0,SZ(TR)-1){
		auto [ql,qr,tl,tr]=TR[i];
		in[qr].pb(i);
	}
	Rep(i,r,mid+1){
		for(auto id:qq[i]){
			auto [ql,qr,tl,ii]=qs[id];
			qid[tl]=ii;
			T4.upd(tl,{i+1});
		}
		for(auto id:in[i]){
			auto [ql,qr,tl,tr]=TR[id];
			T4.mdf(tl,tr,{ql});
		}
		while(1){
			int p=T4.findR(1,m,[&](Max t){
				return t.x>i;
			});
			if(!(p>=1&&p<=m)) break;
			int ii=qid[p];
			if(tor[ii]<i) res[ii]=0;
			T4.upd(p,{-inf});
		}
	}
	
	
	
	For(i,mid+1,r) in[i].clear(),qq[i].clear();
	
	solve(l,mid,TL,QL);
	solve(mid+1,r,TR,QR);
}

void work()
{
	n=read(),q=read();
	
	vector<node> Qs,Ts;
	For(i,1,q){
		int op=read();
		if(op==1){
			++m,ql[m]=read(),qr[m]=read()-1;
			dl[m]=0;
			fid[i]=m;
			tl[m]=m2+1;
			if(ql[m]==qr[m]) ++qwq[ql[m]];
			tr[m]=-1;
		}
		if(op==2){
			int x=read();
			x=fid[x];	
			assert(!dl[x]);
			if(ql[x]==qr[x]) --qwq[ql[x]];
			dl[x]=1;
			tr[x]=m2;
		}
		if(op==3){
			int l=read(),r=read()-1;
			++m2;
			if(l==r) res[m2]=(qwq[l]);
			else Qs.pb({l,r,m2,m2}),res[m2]=1;
			tim[m2]=i;
		}
	}
	
	For(i,1,m){
		if(tr[i]==-1)tr[i]=m2;
		if(tl[i]<=tr[i]) Ts.pb({ql[i],qr[i],tl[i],tr[i]});
	}
	
	solve(1,n-1,Ts,Qs);
	For(i,1,m2) {
		if(res[i])puts("Y");
		else puts("N");
	}
}

signed main()
{
//	freopen("my.out","w",stdout);
	int T=1;
	while(T--)work();
	return 0;
}