本文共 4665 字，大约阅读时间需要 15 分钟。

题目大意

在二维平面给出$n$个点，每个点都有一个权值，且横纵坐标是正整数且范围均是$[1,6000]$，现在有四种操作：

• 插入一个不存在的点
• 删除一个已经存在的点
• 输入一个点和长度$k$，权值$w$，距离该点欧几里得距离为$\sqrt{k}$的所有点的权值都增加$k$
• 输入一个点和长度$k$，求出距离该点欧几里得距离为$\sqrt{k}$的所有点的权值和

解题思路

不难发现，该题的坐标范围很小，时间给了$12s$而且内存给的很大$1024M$，因此考虑暴力。但是一开始写了个假算法，我们想的是距离点$(x_0,y_0)$为$\sqrt{k}$的点满足圆的方程$(x_0-x{)}^2+(y_0-y{)}^2=k$，而且$k$的范围是$1e7$，考虑枚举$\sqrt{k}$范围内的所有$dx=x_0-x$，判断$d{y}^2$是否是平方数，然后判断是否在范围内等等，这样统计，最后得出的时间复杂度为$10^{9.5}$，感觉可以过但是还是被卡了…

实际上内存这么大，$k$最多为$1e7$，完全没必要枚举$dx$，只需要预处理每个$k$对应的 { d x , d y } \{dx,dy\} { dx,dy}对，圆上的整点个数是常数个，这样预处理后每次都是常数的枚举，显然这个算法是可以通过的。至于权值，显然一个二维数组就可以存下，但是本题还有一个卡点，注意$memset()$的时间复杂度是$O(n)$，如果每次都对一个$1e7$的数组预处理，$T=1000$次操作就被卡爆了，这时我们也可以利用本题输入和修改的点是有限的，那么就依靠内存，每次存下上次出现的所有点然后初始化权值为零，真是血的教训！

这次训练赛的这道题让我们以后估计时间复杂度更加谨慎，感觉可以过却超时的题目一定要从题目给出的各个范围的数下手，有可能有意想不到的时间优化。

#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef pair<int, int> pii;const int maxn = 1e7 + 10;const int inf = 1e7;int T, n, m;ll lastAns = 0;int val[6100][6100];vector<pii> points[maxn], all;struct hash_pair {       template<class T1, class T2>    size_t operator()(const pair<T1, T2> &p) const {           auto hash1 = hash<T1>{   }(p.first);        auto hash2 = hash<T2>{   }(p.second);        return hash1 ^ hash2;    }};unordered_map<pii, bool, hash_pair> vis;void init() {       for (int i = 0; i < 3300; i++) {           for (int j = 0; j < 3300; j++) {               if (i * i + j * j <= inf) {                   points[i * i + j * j].push_back(pii(i, j));            }        }    }}inline bool check(int x, int y) {       if (x <= 0 || x > 6000 || y <= 0 || y > 6000) return 0;    if (!val[x][y]) return 0;    return 1;}inline void add(int x, int y, int k, int w) {       vis.clear();    for (auto p: points[k]) {           int dx = p.first, dy = p.second;        if (check(x + dx, y + dy) && !vis[{   x + dx, y + dy}]) val[x + dx][y + dy] += w, vis[{   x + dx, y + dy}] = 1;        if (check(x + dx, y - dy) && !vis[{   x + dx, y - dy}]) val[x + dx][y - dy] += w, vis[{   x + dx, y - dy}] = 1;        if (check(x - dx, y + dy) && !vis[{   x - dx, y + dy}]) val[x - dx][y + dy] += w, vis[{   x - dx, y + dy}] = 1;        if (check(x - dx, y - dy) && !vis[{   x - dx, y - dy}]) val[x - dx][y - dy] += w, vis[{   x - dx, y - dy}] = 1;    }}inline ll getSum(int x, int y, int k) {       ll ans = 0;    vis.clear();    for (auto p:points[k]) {           int dx = p.first, dy = p.second;        if (check(x + dx, y + dy) && !vis[{   x + dx, y + dy}]) ans += val[x + dx][y + dy], vis[{   x + dx, y + dy}] = 1;        if (check(x + dx, y - dy) && !vis[{   x + dx, y - dy}]) ans += val[x + dx][y - dy], vis[{   x + dx, y - dy}] = 1;        if (check(x - dx, y + dy) && !vis[{   x - dx, y + dy}]) ans += val[x - dx][y + dy], vis[{   x - dx, y + dy}] = 1;        if (check(x - dx, y - dy) && !vis[{   x - dx, y - dy}]) ans += val[x - dx][y - dy], vis[{   x - dx, y - dy}] = 1;    }    return ans;}int main() {       init();    scanf("%d", &T);    for (int Case = 1; Case <= T; Case++) {           lastAns = 0;        for (auto p:all) {               val[p.first][p.second] = 0;        }        all.clear();        scanf("%d%d", &n, &m);        printf("Case #%d:\n", Case);        for (int i = 1, x, y, w; i <= n; i++) {               scanf("%d%d%d", &x, &y, &w);            val[x][y] = w;            all.push_back({   x, y});        }        for (int i = 1, op, x, y, k, w; i <= m; i++) {               scanf("%d", &op);            if (op == 1) {                   scanf("%d%d%d", &x, &y, &w);                x = ((x + lastAns) % 6000) + 1;                y = ((y + lastAns) % 6000) + 1;                val[x][y] = w;                all.push_back({   x, y});            } else if (op == 2) {                   scanf("%d%d", &x, &y);                x = ((x + lastAns) % 6000) + 1;                y = ((y + lastAns) % 6000) + 1;                val[x][y] = 0;            } else if (op == 3) {                   scanf("%d%d%d%d", &x, &y, &k, &w);                x = ((x + lastAns) % 6000) + 1;                y = ((y + lastAns) % 6000) + 1;                add(x, y, k, w);            } else if (op == 4) {                   scanf("%d%d%d", &x, &y, &k);                x = ((x + lastAns) % 6000) + 1;                y = ((y + lastAns) % 6000) + 1;                ll ans = getSum(x, y, k);                lastAns = ans;                printf("%lld\n", ans);            }        }    }    return 0;}