HDU 4456 Crowd 座标旋转 二维树状数组
HDU 4456 Crowd 坐标旋转 二维树状数组
大意就是给出一个矩阵
初始每个位置上的值都为0
然后有两种操作
一种是更改某个位置上的值
另一个是求某个位置附近曼哈顿距离不大于K的所有位置的值的总和
然后这里用了一个非常牛叉的技巧
将所有点绕原点左旋45°
然后新的坐标也很好计算
x' = (x - y) * sqrt(2) / 2
y' = (x + y) * sqrt(2) / 2
由于都是小数
所以乘个sqrt(2) 就成整数了
即
x' = (x - y)
y' = x + y
由于x- y可能是负数。所以把点都右移一下 x' = x + y + n （n是矩阵宽度）然后矩阵的宽度和长度也就各自扩大了一倍
然后我们就可以惊奇的发现
原先是求 abs(x - x0) + abs(y - y0) <= k 的所有位置的值的和
现在变成了 abs(x' - x0') <= k 或者abs(y' - y0') <= k 就可以了
也就变成了求一个子矩阵的和
然后就可以欢快的用二维树状数组来解了
但是发现题目给的范围比较大
1W*1W的矩阵
但是询问的话 有8W
那么我们可以就把所有询问中树状数组操作过程中用到的点给离散出来。
然后就可以节省内存了
离散的话可以有两种方法
一种是线性探测再散列
这个可以在线处理询问
另一个就是先把所有可能用到的都取出来，然后先都离散了，离线处理询问
离散之后，每个x,y都应该对应一个唯一的数。我们就可以用一个一维的数组，来完成这个二维树状数组的功能
首先是先把询问存起来的离散方式
这种有点慢 需要1600ms
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define MAXN 4001003
#define MAXM 88888
using namespace std;
int n, m;
int W;
int h[MAXN], cnt;
int a[MAXN];
int pp[MAXN], xx[MAXN], yy[MAXN], zz[MAXN];
inline int lowbit(int x)
{
return x & -x;
}
void ready(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 pos = lower_bound(h, h + cnt, i * W + j) - h;
a[pos] += val;
}
}
int getsum(int x, int y)
{
int sum = 0;
for(int i = x; i > 0; i -= lowbit(i))
for(int j = y; j > 0; j -= lowbit(j))
{
int pos = lower_bound(h, h + cnt, i * W + j) - h;
if(h[pos] == i * W + j)
sum += a[pos];
}
return sum;
}
int main()
{
int p, x, y, z, xa, xb, ya, yb, newx, newy;
while(scanf("%d", &n) != EOF && 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", &pp[i], &xx[i], &yy[i], &zz[i]);
newx = xx[i] - yy[i] + n;
newy = xx[i] + yy[i];
if (pp[i] == 1)
ready(newx, newy);
}
sort(h, h + cnt);
cnt = unique(h, h + cnt) - h;
for(int i = 0; i < m; i++)
{
newx = xx[i] - yy[i] + n;
newy = xx[i] + yy[i];
if(pp[i] == 1) add(newx, newy, zz[i]);
else
{
xa = max(1, newx - zz[i]);
ya = max(1, newy - zz[i]);
xb = min(W, newx + zz[i]);
yb = min(W, newy + zz[i]);
printf("%d\n", getsum(xb, yb) - getsum(xa - 1, yb) - getsum(xb, ya - 1) + getsum(xa - 1, ya - 1));
}
}
}
return 0;
}
另一种是线性探测再散列
这种的话，需要模一个大的素数
但是素数选择不慎的话会导致TLE
选择好了就比较快 800ms
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define MAXN 4001003
#define MAXM 88888
using namespace std;
int n, m;
int W;
int h[MAXN];
int a[MAXN];
int hash(int x)
{
int pos = x % MAXN;
while(true)
{
if(h[pos] == 0 || h[pos] == x)
{
h[pos] = x;
return pos;
}
pos++;
if(pos == MAXN) pos = 0;
}
}
int gethash(int x)
{
int pos = x % MAXN;
while(true)
{
if(h[pos] == 0 || h[pos] == x) return pos;
pos++;
if(pos == MAXN) pos = 0;
}
}
inline int lowbit(int x)
{
return x & -x;
}
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))
a[hash(i * W + j)] += val;
}
int getsum(int x, int y)
{
int sum = 0;
for(int i = x; i > 0; i -= lowbit(i))
for(int j = y; j > 0; j -= lowbit(j))
sum += a[gethash(i * W + j)];
return sum;
}
int main()
{
int p, x, y, z, xa, xb, ya, yb, newx, newy;
while(scanf("%d", &n) != EOF && n)
{
scanf("%d", &m);
W = n * 2;
memset(a, 0, sizeof(a));
memset(h, 0, sizeof(h));
for(int i = 0; i < m; i++)
{
scanf("%d%d%d%d", &p, &x, &y, &z);
newx = x - y + n;
newy = x + y;
if(p == 1) add(newx, newy, z);
else
{
xa = max(1, newx - z);
ya = max(1, newy - z);
xb = min(W, newx + z);
yb = min(W, newy + z);
printf("%d\n", getsum(xb, yb) - getsum(xa - 1, yb) - getsum(xb, ya - 1) + getsum(xa - 1, ya - 1));
}
}
}
return 0;
}