自动搬运

查看原文

来自洛谷，原作者为

	jun头吉吉 alive

搬运于2025-08-24 22:27:48，当前版本为作者最后更新于2022-05-11 13:21:58，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意

平面直角坐标系上一个等腰直角三角形，维护 $4$ 种操作：

1. 加入 $(x,y)$
2. 把 $y\le l$ 的点横坐标变成 $\max(x,n-l)$
3. 把 $x\le l$ 的点纵坐标变成 $\max(y,n-l)$
4. 查询第 $i$ 个点现在的位置。

题解

从测试点出发。 前两个 subtask 我啥都没看出来，所以从第三个开始。

这个就是没有加点操作，并且形状是 $\ddots$。这个有什么用呢？手玩一下发现如果一开始满足这个性质，那么被推一次之后仍然满足这个性质，并且每次更改的是一段连续的点。然后这个玩意儿很容易维护，直接写平衡树即可，复杂度 $\mathcal O(Q\log Q)$，可以参考这份 11分代码。

然后看第四个 subtask，没有了 $x$ 递增 $y$ 递减的性质，怎么办呢？继续手玩，发现所有推过一次之后的点都满足上面的性质，所以我们只需要计算出每个点第一次被推的时间然后在那个时间加入即可。求第一次被推的时间求相当于求第一个覆盖的矩形，可以正着求直接找但是我只会两只 $\log$ 的，考虑倒过来，一个包含 $(a,b)$ 的矩形的右端点的横坐标在 $[a,N-b]$，于是单点改区间查就是一只 $\log$ 了，总的复杂度还是 $\mathcal O(Q\log Q)$，可以参考这份 64分代码。

也就是说，我们现在不支持中间加点，我们不希望有这个操作。可不可以没有这个操作呢？其实可以用一只 $\log$ 的代价扔掉这个操作，具体的做法就是线段树分治，每次询问放到 $\log Q$ 个区间上，那么每个区间内都是一个 subtask4，因此总的复杂度就是 $\mathcal O(Q\log^2Q)$，得到了 100分代码。

代码

#include<bits/stdc++.h>
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define pb push_back
#define pc putchar
#define chkmx(a,b) (a)=max((a),(b))
#define chkmn(a,b) (a)=min((a),(b))
#define fi first
#define se second
using namespace std;
template<class T>
void read(T&x){x=0;char c=getchar();bool f=0;for(;!isdigit(c);c=getchar())f^=c=='-';for(;isdigit(c);c=getchar())x=x*10+c-'0';if(f)x=-x;}
template<class T,class ...ARK>void read(T&x,ARK&...ark){read(x);read(ark...);}
template<class T>void write(T x){if(x<0)pc('-'),x=-x;if(x>=10)write(x/10);pc(x%10+'0');}
template<class T,class ...ARK>void write(T x,ARK...ark){write(x);pc(' ');write(ark...);}
template<class ...ARK>void writeln(ARK...ark){write(ark...);pc('\n');}
typedef long long ll;
const int mod=998244353;
struct mint{
	int x;mint(int o=0){x=o;}mint&operator+=(mint a){return(x+=a.x)%=mod,*this;}mint&operator-=(mint a){return(x+=mod-a.x)%=mod,*this;}
	mint&operator*=(mint a){return(x=1ll*x*a.x%mod),*this;}mint&operator^=( int b){mint a=*this;x=1;while(b)(b&1)&&(*this*=a,1),a*=a,b>>=1;return*this;}
	mint&operator/=(mint a){return*this*=(a^=mod-2);}friend mint operator+(mint a,mint b){return a+=b;}friend mint operator-(mint a,mint b){return a-=b;}
	friend mint operator*(mint a,mint b){return a*=b;}friend mint operator/(mint a,mint b){return a/=b;}friend mint operator^(mint a, int b){return a^=b;}
};
#define lowbit(x) ((x)&-(x))
#define mid ((l+r)>>1)
const int N=2e6+100;
int n,m,q,root,cnt;
mt19937 myrnd(114514);
namespace fhq{
	//x单调不降，y单调不升
	struct node{
		int x,y,tagx,tagy,lc,rc,rnd,fa;
		node(){tagx=tagy=-1,rnd=myrnd();}
		void clr(){x=y=lc=rc=fa=0;tagx=tagy=-1;}
	}t[N];
	void pushup(int x){
		if(t[x].lc)t[t[x].lc].fa=x;
		if(t[x].rc)t[t[x].rc].fa=x;
	}
	void pushtag(int x,int tagx,int tagy){
		if(!x)return;
		if(~tagx)t[x].x=t[x].tagx=tagx;
		if(~tagy)t[x].y=t[x].tagy=tagy;
	}
	void pushdown(int x){
		pushtag(t[x].lc,t[x].tagx,t[x].tagy);
		pushtag(t[x].rc,t[x].tagx,t[x].tagy);
		t[x].tagx=t[x].tagy=-1;
	}
	void splitX(int x,int&a,int&b,int k){
		//按x分裂 <=k 的给 a >k 的给 b
		if(!x)return a=b=0,void();
		pushdown(x);
		if(t[x].x<=k){
			a=x;splitX(t[x].rc,t[x].rc,b,k);
			pushup(a);
		}else{
			b=x;splitX(t[x].lc,a,t[x].lc,k);
			pushup(b);
		}
	}
	void splitY(int x,int&a,int&b,int k){
		//按y分裂 >=k 的给 a <k 的给 b
		if(!x)return a=b=0,void();
		pushdown(x);
		if(t[x].y>=k){
			a=x;splitY(t[x].rc,t[x].rc,b,k);
			pushup(a);
		}else{
			b=x;splitY(t[x].lc,a,t[x].lc,k);
			pushup(b);
		}
	}
	int merge(int x,int y){
		if(!x||!y)return x^y;
		pushdown(x);pushdown(y);
		if(t[x].rnd<t[y].rnd){
			t[x].rc=merge(t[x].rc,y);
			pushup(x);return x;
		}else{
			t[y].lc=merge(x,t[y].lc);
			pushup(y);return y;
		}
	}
	void dfs(int x){
		if(!x)return;
		pushdown(x);
		dfs(t[x].lc);
		dfs(t[x].rc);
	}
};
int x[N],y[N],tim[N];
int op[N],l[N];int qid[N];
namespace sgt{
	#define lc (x<<1)
	#define rc (x<<1|1)
	//单点覆盖 区间最小值
	vector<int>num;
	int mn[N<<2];
	void pushup(int x){mn[x]=min(mn[lc],mn[rc]);}
	void build(int x,int l,int r){mn[x]=q+1;if(l==r)return;build(lc,l,mid);build(rc,mid+1,r);}
	void mdf(int x,int l,int r,int p,int v){if(l==r)return mn[x]=v,void();if(p<=mid)mdf(lc,l,mid,p,v);else mdf(rc,mid+1,r,p,v);pushup(x);}
	int qry(int x,int l,int r,int ql,int qr){if(ql<=l&&r<=qr)return mn[x];if(r<ql||qr<l)return q+1;return min(qry(lc,l,mid,ql,qr),qry(rc,mid+1,r,ql,qr));}
	void init(){
		sort(num.begin(),num.end());num.resize(unique(num.begin(),num.end())-num.begin());
		build(1,0,num.size());
	}
	void mdf(int p,int v){
		p=lower_bound(num.begin(),num.end(),p)-num.begin();
		mdf(1,0,num.size(),p,v);
	}
	int qry(int ql,int qr){
		ql=lower_bound(num.begin(),num.end(),ql)-num.begin();
		qr=lower_bound(num.begin(),num.end(),qr)-num.begin();
		return qry(1,0,num.size(),ql,qr);
	}
}
int xx[N],yy[N],vcnt;vector<int>ids[N];
void ins(int id){
	fhq::t[id].x=xx[id],fhq::t[id].y=yy[id];
	int a,b,c;
	fhq::splitX(root,a,c,xx[id]);fhq::splitY(a,a,b,yy[id]);
	root=fhq::merge(fhq::merge(a,id),fhq::merge(b,c));
}
vector<int>qrys[N<<2];
void add(int x,int l,int r,int ql,int qr,int v){
	if(ql<=l&&r<=qr)return qrys[x].pb(v);
	if(r<ql||qr<l)return;
	add(lc,l,mid,ql,qr,v);add(rc,mid+1,r,ql,qr,v);
}
void solve(int x,int l,int r){
	sgt::num.clear();
	for(int i=l;i<=r;i++){
		ids[i].clear();
		if(op[i]==2)sgt::num.pb(n-::l[i]);
		if(op[i]==3)sgt::num.pb(::l[i]);
	}
	for(auto id:qrys[x])sgt::num.pb(xx[id]),sgt::num.pb(n-yy[id]);
	sgt::init();
	for(int i=r;i>=l;i--){
		if(op[i]==2)sgt::mdf(n-::l[i],i);
		if(op[i]==3)sgt::mdf(::l[i],i);
	}
	root=0;
	for(auto id:qrys[x])fhq::t[id].clr(),fhq::t[id].x=xx[id],fhq::t[id].y=yy[id],ids[sgt::qry(xx[id],n-yy[id])].pb(id);
	for(int i=l;i<=r;i++){
		if(op[i]==2){
			int a,b,c;
			fhq::splitX(root,a,c,n-::l[i]);
			fhq::splitY(a,a,b,::l[i]+1);
			fhq::pushtag(b,n-::l[i],-1);
			root=fhq::merge(fhq::merge(a,b),c);
			for(auto id:ids[i])xx[id]=n-::l[i],ins(id);
		}else if(op[i]==3){
			int a,b,c;
			fhq::splitX(root,a,c,::l[i]);
			fhq::splitY(a,a,b,n-::l[i]);
			fhq::pushtag(b,-1,n-::l[i]);
			root=fhq::merge(fhq::merge(a,b),c);
			for(auto id:ids[i])yy[id]=n-::l[i],ins(id);
		}
	}
	fhq::dfs(root);
	for(auto id:qrys[x])xx[id]=fhq::t[id].x,yy[id]=fhq::t[id].y;
	if(l==r)return;
	solve(lc,l,mid);solve(rc,mid+1,r);
}
signed main(){
	read(n,m,q);
	for(int i=1;i<=m;i++)cnt++,read(x[cnt],y[cnt]);
	for(int i=1;i<=q;i++){
		read(op[i]);
		if(op[i]!=4)read(l[i]);
		else tim[++cnt]=i,read(x[cnt],y[cnt]);
		if(op[i]==1){
			qid[i]=++vcnt;xx[vcnt]=x[l[i]],yy[vcnt]=y[l[i]];
			add(1,1,q,tim[l[i]],i,vcnt);
		}
	}
	solve(1,1,q);
	for(int i=1;i<=q;i++)if(op[i]==1)writeln(xx[qid[i]],yy[qid[i]]);
}