HDU4456-Crowd

Crowd

                                                                    Time Limit: 5000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
                                                                                            Total Submission(s): 2594    Accepted Submission(s): 612

Problem Description

City F in the southern China is preparing *s festival celebration along the streets to celebrate the festival. 
Since frequent accidents had happened last year when the citizens went out to admire the colorful *s, City F is planning to develop a system to calculate the degree of congestion of the intersection of two streets. 
The map of City F is organized in an N×N grid (N north-south streets and N west-east street). For each intersection of streets, we define a density value for the crowd on the intersection. 
Initially, the density value of every intersection is zero. As time goes by, the density values may change frequently. A set of cameras with new graphical recognition technology can calculate the density value of the intersection easily in a short time.
But the administrator of the police office is planning to develop a system to calculate the degree of congestion. For some consideration, they come up with a conception called "k-dimension congestion degree". The "k-dimension congestion degree" of intersection (x0,y0) is represented as "c(x0,y0,k)", and it can be calculated by the formula below:

Here, d(x,y) stands for the density value on intersection (x,y) and (x,y) must be in the N×N grid. The formula means that all the intersections in the range of manhattan distance k from (x0,y0) effect the k-dimension congestion degree of (x0,y0) equally, so we just simply sum them up to get the k-dimension congestion degree of (x0,y0). 
The figure below shows a 7×7 grid, and it shows that if you want to get the 2-dimension congestion degree of intersection (4,2),you should sum up the density values of all marked intersections.

 

Input

These are multiple test cases. 
Each test case begins with a line with two integers N, M, meaning that the city is an N×N grid and there will be M queries or events as time goes by. (1 ≤ N ≤10 000, 1 ≤ M ≤ 80 000) Then M lines follow. Each line indicates a query or an event which is given in form of (p, x, y, z), here p = 1 or 2, 1 ≤ x ≤ N, 1 ≤ y ≤ N. 
The meaning of different p is shown below.
1. p = 1 the value of d(x,y) is increased by z, here -100 ≤ z ≤ 100.
2. p = 2 query the value of c(x,y,z), here 0 ≤ z ≤ 2N-1.
Input is terminated by N=0.

 

Output

For each query, output the value for c(x,y,z) in a line.

 

Sample Input

8 5 1 8 8 1 1 1 1 -2 2 5 5 6 1 5 5 3 2 2 3 9 3 2 1 3 2 -9 2 3 2 0 0

 

Sample Output

1 1 -9

 

Source

2012 Asia Hangzhou Regional Contest

 

Recommend

 

题意：给定一个n*n的网格，有两种操作，一种是改变网格上的某个单点的权值，另一种是求到一点曼哈顿距离为小于等于k的所有的权值和，初始化网格所有点的权值为0。

解题思路：题目中主要要解决的两个问题是：如何将题目中的曼哈顿距离转化为规则的矩形，以及如何避免开辟一个巨大的数组。解决这两个问题后就是一个简单的二维树状数组了

转化为矩形：把所有的点都旋转45度，需要一个2n*2n的数组数组才能容下坐标转换之后的图，坐标的转化方式为xx=x-y+n,yy=x+y。可以这样看，转化之后的同行相邻两列的坐标差为(-1, 1), 相邻两列相邻两行的坐标差为(1, 1)。如果以(0, 0)为参考点（即该点转化前后位置不发生变化），那么(x, y)就变为(x-y, x+y)，因为所有的点都应该在这个2n*2n的矩形中，因此我们给(1,1)这个点衡坐标加上n，纵坐标也可以-1，这样就能让最靠左边的点的列从1开始，这样转化后(1,1)->(n,2),(1,n)->(1,n+1),(n,1)->(2n-1,n+1),(n,n)->(n, 2n)。

避免开一个大的数组：转化之后的数组达到了20000*20000，所以需要进行离散化，离散化后就可以存的下了

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <climits>

using namespace std;

#define LL long long
const int INF = 0x3f3f3f3f;

int n,m,w;
int h[5000009],cnt,a[5000009];
int p[80009],x[80009],y[80009],z[80009];

int lowbit(int k)
{
    return k&-k;
}

void f(int x,int y)
{
    for (int i=x;i<=w;i+=lowbit(i))
        for (int j=y;j <=w;j+=lowbit(j))
            h[cnt++]=i*w+j;
}

void add(int x,int y,int val)
{
    for(int i = x; i <= w; i += lowbit(i))
        for(int j = y; j <= w; j += lowbit(j))
        {
            int k=lower_bound(h,h+cnt,i*w+j)-h;
            a[k]+=val;
        }
}

int getsum(int x,int y)
{
    int sum=0;
    for(int i=x;i;i-=lowbit(i))
        for(int j=y;j;j-=lowbit(j))
        {
            int k=lower_bound(h,h+cnt,i*w+j)-h;
            if(h[k]==i*w+j) sum+=a[k];
        }
    return sum;
}

int main()
{
    while(~scanf("%d",&n)&&n)
    {
        scanf("%d", &m);
        w=n*2;
        cnt=0;
        memset(a, 0, sizeof a);
        for (int i=0;i<m;i++)
        {
            scanf("%d%d%d%d",&p[i],&x[i],&y[i],&z[i]);
            int xx=x[i]-y[i]+n;
            int yy=x[i]+y[i];
            if(p[i]==1) f(xx,yy);
        }
        sort(h,h+cnt);
        cnt=unique(h,h+cnt)-h;
        for(int i=0;i<m;i++)
        {
            int xx=x[i]-y[i]+n;
            int yy=x[i]+y[i];
            if(p[i]==1) add(xx,yy,z[i]);
            else
            {
                int x1 = max(1, xx-z[i]);
                int y1 = max(1, yy-z[i]);
                int x2 = min(w, xx+z[i]);
                int y2 = min(w, yy+z[i]);
                printf("%d\n", getsum(x2, y2) - getsum(x1 - 1, y2) - getsum(x2, y1 - 1) + getsum(x1 - 1, y1 - 1));
            }
        }
    }
    return 0;
}