题解：P12016 [NOISG 2025 Finals] 震踏

· · 题解

P12016 [NOISG 2025 Finals] Thumper

题目大意是有 m 个操作，每个操作给定一个点集中的点，其他点按规则远离这个点一次。

首先，暴力可以拿到 18 分的高分。

不难发现对于任意两个点，其关系是一定的，即：对于一个点 x 和一个点 y，每次点 x Thump 时点 y 的运动方向是一定的。

之后考虑方向问题。一个点的横坐标或纵坐标是否改变取决于它相较于这个操作的点在哪个区域。如图，中间的格子是某一操作的点，则在 y = x 或 y = -x 直线上方格上的点会是斜着走一格，其余格子会按区域的箭头方向走两格。（由于工具所限，此图一个方格对应图中四个灰色小方格，请忽略坐标上的灰色数字，下同）

斜着的区域显然不好处理。注意到每次操作每个点的曼哈顿距离加 2，无法把横坐标和纵坐标分开来处理，把它变回求切比雪夫距离的类似问题似乎会好做一些，考虑将图旋转 45 度。则点 (x, y) 会变成 (x + y, x - y)（不会切比雪夫距离的自行百度）

（似乎这样看着会舒服一些）

改为以浅蓝线为 x 轴，以红线为 y 轴建系。（你没看错，新建的 y 轴是倒着的）发现：对于一个操作，选定的点为 p，则所有横坐标严格比 p 小的点，横坐标减 2；所有横坐标严格比 p 大的点，横坐标加 2；纵坐标亦同理。

于是对于 x 轴和 y 轴在值域上维护一个数据结构记录横坐标或纵坐标的偏移量。每次一个询问需要区间加，询问结束后将每个点的横坐标与纵坐标加上其偏移量，最后将坐标转回来，即将点 (x', y') 转回 (\frac{x' + y'}{2}, \frac{x' - y'}{2})，需要单点查。此外，由于值域是 [-10 ^ 9, 10 ^ 9]（新坐标可能为负），需要离散化一下。

刚开始用的是线段树，但是 TLE 了，于是卡常，改成树状数组维护差分序列就 AC 了。

个人感觉思考及实现起来有些复杂，评绿似乎有点低了？（应该是我太菜了罢）

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int n, m, t[N];
struct node { int x, y; } a[N];
node aa[N]; // 坐标系旋转45°后的坐标

int orix[N], totx, oriy[N], toty;
void init() {
    for (int i = 1; i <= n; i++) orix[++totx] = aa[i].x;
    sort(orix + 1, orix + n + 1);
    totx = unique(orix + 1, orix + 1 + totx) - (orix + 1);
    for (int i = 1; i <= n; i++) oriy[++toty] = aa[i].y;
    sort(oriy + 1, oriy + n + 1);
    toty = unique(oriy + 1, oriy + 1 + toty) - (oriy + 1);
}
int gethashx(int val) { return lower_bound(orix + 1, orix + totx + 1, val) - orix; };
int gethashy(int val) { return lower_bound(oriy + 1, oriy + toty + 1, val) - oriy; };
// 以上是离散化操作

struct DS {
    int c[N];
    void add(int x, int val, int lim) { if (x == 0) x++; for (int i = x; i <= lim; i += i & -i) c[i] += val; }
    int query(int x) { int res = 0; for (int i = x; i; i -= i & -i) res += c[i]; return res; }
    void update(int x, int y, int val, int lim) { add(x, +val, lim), add(y + 1, -val, lim); }
};
DS X, Y; // 旋转后x坐标和y坐标的偏移量
// 以上为维护偏移量的 DS

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    freopen("thumper.in", "r", stdin);
    freopen("thumper.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i].x >> a[i].y;
    for (int i = 1; i <= m; i++)
        cin >> t[i];

    for (int i = 1; i <= n; i++) {
        aa[i].x = a[i].x + a[i].y;
        aa[i].y = a[i].x - a[i].y;
    }
    init();

    for (int i = 1; i <= n; i++) {
        aa[i].x = gethashx(aa[i].x);
        aa[i].y = gethashy(aa[i].y);
    }

    for (int i = 1; i <= m; i++) {
        int nx = aa[t[i]].x, ny = aa[t[i]].y;
        X.update(1, nx - 1, -2, totx), X.update(nx + 1, totx, +2, totx);
        Y.update(1, ny - 1, -2, toty), Y.update(ny + 1, toty, +2, toty);
    }

    for (int i = 1; i <= n; i++) {
        int nx = X.query(aa[i].x) + orix[aa[i].x],
            ny = Y.query(aa[i].y) + oriy[aa[i].y];
        cout << (nx + ny) / 2 << " " << (nx - ny) / 2 << '\n';
    }
    return 0;
}