题目性质

不难发现，震踏具有以下性质：

• 任何兔子之间的相对位置不会改变，即：若兔子 $a$ 初始位于兔子 $b$ 的左上方，那么兔子 $a$ 一定不会通过若干次操作到达兔子 $b$ 左下、右上或右下角。

解法

注意到对于第 $i(1≤i≤m)$ 次震踏，第 $t_i$ 只兔子所在的两条斜线将整个平面分为了四部分：

如果将整个平面顺时针旋转 $45°$，不难发现两条斜线形成了一个以兔子 $t_i$ 为原点的平面直角坐标系，其中原平面中斜方向上的一格是该坐标系中的单位长度。

由于原平面中以上 $\rightarrow$ 下为 $r$ 方向正方向，以左 $\rightarrow$ 右为 $c$ 方向正方向，为了方便叙述，下文将左上 $\rightarrow$ 右下称为 $a$ 方向正方向，将左下 $\rightarrow$ 右上称为 $b$ 方向正方向。

那么，可以定义兔子 $j(1≤j≤n)$ 的新坐标 $(a_j,b_j)$：

$a_j = r_j+c_j$

$b_j = 10^9-r_j+c_j$

第 $j$ 只兔子的移动可以被拆解为 $a$ 方向和 $b$ 方向上的移动：

1. $a$ 方向：

• 若兔子 $j$ 位于兔子 $t_i$ 上方，则 $a_j \gets a_j-1$。
• 若兔子 $j$ 位于兔子 $t_i$ 下方，则 $a_j \gets a_j+1$。

2. $b$ 方向：

• 若兔子 $j$ 位于兔子 $t_i$ 左侧，则 $b_j \gets b_j-1$。
• 若兔子 $j$ 位于兔子 $t_i$ 右侧，则 $b_j \gets b_j+1$。

很明显，可以用两个差分数组分别维护 $a$ 方向和 $b$ 方向上每次震踏的修改操作，所有震踏进行后再对每个差分数组求前缀和，即可求出每只兔子的最终坐标。

由于有相对位置不会改变的性质，可以将兔子 $j$ 的初始坐标 $a_j$ 和坐标 $b_j$ 存在两个数组中并排序，每次震踏时只记录 $\triangle a_j$ 和 $\triangle b_j$。

震踏进行后，需要把每只兔子 $j$ 坐标 $(a_j',b_j')$ 转化回原平面的坐标 $(r_j',c_j')$：

1. $a$ 坐标：

$a$ 方向正方向上的移动，实际上是在原图中向右下方移动，因此：

$r_j \gets r_j+\triangle a_j$

$c_j \gets c_j+\triangle a_j$

2. $b$ 坐标：

$b$ 方向正方向上的移动，实际上是在原图中向右上方移动，因此：

$r_j \gets r_j-\triangle b_j$

$c_j \gets c_j+\triangle b_j$

代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+5,INF=1e9;
struct rabbit{int r,c;}r[MAXN];
struct line{
	int k,sp;//k:坐标  sp:兔子编号 
	bool operator<(const line &a)const{return k<a.k;}
	bool operator<=(const line &a)const{return k<=a.k;}
};
int n,m,cfa[MAXN],cfb[MAXN],_a[MAXN],_b[MAXN];
//cfa/cfb:维护a/b坐标变化量的差分数组  _a/_b:最终a/b坐标的变化量 
vector<line> a,b;
//a/b:记录每只兔子初始时的a/b坐标 
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>r[i].r>>r[i].c;
		a.push_back((line){r[i].r+r[i].c,i});
		b.push_back((line){INF-r[i].r+r[i].c,i});
	}
	sort(a.begin(),a.end());
	sort(b.begin(),b.end());
	for(int i=1,t;i<=m;i++){
		cin>>t;
		int kta=r[t].r+r[t].c,ktb=INF-r[t].r+r[t].c;
		//kta/ktb:第t_i只兔子的a/b坐标 
		int la=lower_bound(a.begin(),a.end(),(line){kta,1})-a.begin(),
		ra=upper_bound(a.begin(),a.end(),(line){kta,1})-a.begin(),
		lb=lower_bound(b.begin(),b.end(),(line){ktb,1})-b.begin(),
		rb=upper_bound(b.begin(),b.end(),(line){ktb,1})-b.begin();
		cfa[0]+=-1,cfa[la]+=1;
		cfa[ra]+=1,cfa[n]+=-1;
		cfb[0]+=-1,cfb[lb]+=1;
		cfb[rb]+=1,cfb[n]+=-1;
	}
	for(int i=0;i<n;i++){
		cfa[i]+=cfa[i-1],cfb[i]+=cfb[i-1];
		_a[a[i].sp]=cfa[i],_b[b[i].sp]=cfb[i];
	}
	for(int i=1;i<=n;i++){
		r[i].r+=_a[i]-_b[i];
		r[i].c+=_a[i]+_b[i];
		cout<<r[i].r<<" "<<r[i].c<<endl; 
	}
}

AC记录

后记

作为首批参加NOISG的国内选手，在考场上我维护了两棵线段树，导致了最后一个点超时。提醒各位，注意常数优化。