Crowd
Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2576 Accepted Submission(s): 608
Problem Description
City F in the southern China is preparing lanterns 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 lanterns, 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
Sample Output
1
1
-9
Source
2012 Asia Hangzhou Regional Contest
看到坐标變換，有沒有想到什麼？對了，就是WOJ那題！
記得當時那題，Soul Artist，是靜态的求和，直接用一個坐标變換加上二維的字首和數組即可。這題也是類似的，不過他是動态的單點修改，動态區間查詢。那麼這就要用到二維樹狀數組了。
我們先複習一下坐标變換。我們發現，由于修改是manhattan距離範圍内的點，是以修改的區域是一個菱形（正方形），是以等價于同一條斜對角線上的點有某些相同的性質。我們坐标變換，另x'=x-y+n，y'=x+y-1，則發現同一條斜對角線上的點要麼x'相同要麼y'相同。于是，我們便可以在新的坐标下建立樹狀數組，用樹狀數組解決修改和查詢的操作。
#include<bits/stdc++.h>
#define N 4000100
using namespace std;
struct BinaryIndexTree
{
int c[N],n,t,num[N];
inline void init()
{
t=0;
memset(c,0,sizeof(c));
}
inline void Hash(int x,int y)
{
for (int i=x;i<=n;i+=lowbit(i))
for (int j=y;j<=n;j+=lowbit(j))
num[++t]=i*n+j;
}
inline void Sort()
{
sort(num+1,num+1+t);
t=unique(num+1,num+1+t)-num;
}
inline int Find(int x)
{
return lower_bound(num+1,num+t,x)-num;
}
inline int lowbit(int x)
{
return x&-x;
}
inline void updata(int x,int y,int k)
{
for (int i=x;i<=n;i+=lowbit(i))
for (int j=y;j<=n;j+=lowbit(j))
{
int pos=Find(i*n+j);
if (num[pos]==i*n+j) c[pos]+=k;
}
}
inline int getsum(int x,int y)
{
int ans=0;
for (int i=x;i;i-=lowbit(i))
for (int j=y;j;j-=lowbit(j))
{
int pos=Find(i*n+j);
if (num[pos]==i*n+j) ans+=c[pos];
}
return ans;
}
} BIT;
int n,m,op[N/5],x[N/5],y[N/5],z[N/5];
int main()
{
while(~scanf("%d",&n)&&n!=0)
{
BIT.n=2*n;
BIT.init();
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d%d",&op[i],&x[i],&y[i],&z[i]);
if (op[i]==1) BIT.Hash(x[i]-y[i]+n,x[i]+y[i]-1);
}
BIT.Sort();
for(int i=1;i<=m;i++)
{
int xx=x[i]-y[i]+n;
int yy=x[i]+y[i]-1;
if (op[i]==2)
{
int x1=max(1,xx-z[i]);
int y1=max(1,yy-z[i]);
int x2=min(2*n,xx+z[i]);
int y2=min(2*n,yy+z[i]);
printf("%d\n",BIT.getsum(x1-1,y1-1)-BIT.getsum(x1-1,y2)-BIT.getsum(x2,y1-1)+BIT.getsum(x2,y2));
} else BIT.updata(xx,yy,z[i]);
}
}
return 0;
}