题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=4456

题目：

N*N的网格，M个询问

p=2时输出到（x,y）的曼哈顿距离小于等于z的点对应的值之和

 

解题思路：

（1）到A（x,y）的曼哈顿距离小于等于z的点分布在以A为中心，中垂线的一半=z的菱形上（菱形的四个边都相同），把曼哈顿忽略转化为切比雪夫距离，到A（x,y）的曼哈顿距离小于等于z的点分布在以A'(A'为转为后的坐标)为中心，边长2*z的正方形内：(x,y) --->(x+y, x-y+N)，且转换后的网格相当于原来的4倍左右，但其实需要离散的点并没有那么多，网上的题解都是取了400万

（2）找到这个正方形的左上角和右下角并计算这个区间内的点的值的和（二维树状数组解决），相当于二维树状数组的单点更新和区间查询，注意不要越界！

（3）N最大为100000，点太多了，需要离散化，并且只离散化有用的点，先对M个询问给出的所有的点进行离散化，并且按照二维树状数组的方式进行离散化，因为只有用二维树状数组更新和求sum值的那些点才有用，才需要离散化

12年杭州区域赛的金牌题好像是，@(・●・)@溜了溜了

 

ac代码：

#include <bits/stdc++.h>

using namespace std;
const int maxn = 4000005;//神奇的400万，可能数据很水，而且好像也离散不出来那么多数
const int maxm = 80005;

#define lowbit(x) ((x)&(-x))
int N, M, W, E, H[maxn+5], fenw[maxn + 5];
int O[maxm], X[maxm], Y[maxm], Z[maxm];

inline int find (int x) {
    return lower_bound(H + 1, H + E, x) - H;
}

void hashPoint (int x, int y)
{
    for (int i = x; i <= W; i += lowbit(i))
    {
        for (int j = y; j <= W; j += lowbit(j))
            H[E++] = i * W + j;
    }
}

void add(int x, int y, int d)
{
    for (int i = x; i <= W; i += lowbit(i))
    {
        for (int j = y; j <= W; j += lowbit(j))
        {
            int pos = find(i * W + j);
            fenw[pos] += d;
        }
    }
}

int sum (int x, int y)
{
    int ret = 0;
    for (int i = x; i; i -= lowbit(i))
    {
        for (int j = y; j; j -= lowbit(j))
        {
            int pos = find(i * W + j);
            if (H[pos] == i * W + j) //可能没有找到这个值
                ret += fenw[pos];
        }
    }
    return ret;
}

void init ()
{
    E = 1;
    W = 2 * N;
    scanf("%d", &M);
    memset(fenw, 0, sizeof(fenw));

    for (int i = 1; i <= M; i++)
    {
        scanf("%d%d%d%d", &O[i], &X[i], &Y[i], &Z[i]);
        int x = X[i] + Y[i];
        int y = X[i] - Y[i] + N;
        if (O[i] == 1)
            hashPoint(x, y);
    }
    sort(H + 1, H + E);
    E = unique(H + 1, H + E) - H;
}

void solve() {
    for (int i = 1; i <= M; i++)
    {
        int x = X[i] + Y[i];
        int y = X[i] - Y[i] + N;

        if (O[i] == 1)
            add(x, y, Z[i]);
        else
            {
            int a = max(1, x - Z[i]);
            int b = max(1, y - Z[i]);
            int c = min(W, x + Z[i]);
            int d = min(W, y + Z[i]);
            printf("%d\n", sum(c, d) - sum(c, b-1) - sum(a-1, d) + sum(a-1, b-1));
        }
    }
}

int main ()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    while (scanf("%d", &N) == 1 && N)
    {
        init();
        solve();
    }
    return 0;
}