VIJOS 1512SuperBrother打鼹鼠(二维BIT)

VIJOS 1512SuperBrother打鼹鼠(二维BIT)

呵呵..

二维树状数组,第二维和第一维基本一样.

--------------------------------------------------------------------------------

#include<cstdio>
#include<cstring>
#include<cstring>
#include<algorithm>
 
#define rep(i, n) for(int i = 0; i < n; ++i)
#define Rep(i, r) for(int i = 1; i <= r; ++i)
#define clr(x, c) memset(x, c, sizeof(x))
 
using namespace std;
 
const int maxn = 1024 + 5;
 
int n, b[maxn][maxn];
 
#define lowbit(x) (x & -x)
 
void add(int x, int y, int v) {
for(int i = x; i <= n; i += lowbit(i)) 
   for(int j = y; j <= n; j += lowbit(j))
       b[i][j] += v;
}
 
int sum(int x, int y) {
int ans = 0;
for(int i = x; i > 0; i -= lowbit(i))
   for(int j = y; j > 0; j -= lowbit(j))
       ans += b[i][j];
return ans;
}
 
int main() {
freopen("test.in", "r", stdin);
clr(b, 0);
scanf("%d", &n);
int op;
while(scanf("%d", &op) == 1 && op != 3) {
if(op == 1) {
int x, y, v;
scanf("%d%d%d", &x, &y, &v);
++x; ++y;
add(x, y, v);
} else {
int x[2], y[2];
rep(i, 2) scanf("%d%d", &x[i], &y[i]);
printf("%d\n", sum(x[1] + 1, y[1] + 1) - sum(x[0], y[1] + 1) - sum(x[1] + 1, y[0]) + sum(x[0], y[0]));
}
}
return 0;
}

--------------------------------------------------------------------------------

P1512SuperBrother打鼹鼠
标签:[显示标签]

背景

SuperBrother在机房里闲着没事干(再对比一下他的NOIP,真是讽刺啊......),于是便无聊地开始玩“打鼹鼠”......

描述

在这个“打鼹鼠”的游戏中,鼹鼠会不时地从洞中钻出来,不过不会从洞口钻进去(鼹鼠真胆大……)。洞口都在一个大小为n(n<=1024)的正方形中。这个正方形在一个平面直角坐标系中,左下角为(0,0),右上角为(n-1,n-1)。洞口所在的位置都是整点,就是横纵坐标都为整数的点。而SuperBrother也不时地会想知道某一个范围的鼹鼠总数。这就是你的任务。

格式

输入格式

每个输入文件有多行。

第一行,一个数n,表示鼹鼠的范围。

以后每一行开头都有一个数m,表示不同的操作:
m=1,那么后面跟着3个数x,y,k(0<=x,y<n),表示在点(x,y)处新出现了k只鼹鼠;
m=2,那么后面跟着4个数x1,y1,x2,y2(0<=x1<=x2<n,0<=y1<=y2<n),表示询问矩形(x1,y1)-(x2,y2)内的鼹鼠数量;
m=3,表示老师来了,不能玩了。保证这个数会在输入的最后一行。

询问数不会超过10000,鼹鼠数不会超过maxlongint。

输出格式

对于每个m=2,输出一行数,这行数只有一个数,即所询问的区域内鼹鼠的个数。

样例1

样例输入1[复制]

4 1 2 2 5 2 0 0 2 3 3

样例输出1[复制]

5

限制

各个测试点1s

提示

水题一道。

所有数据均为随机生成,包括样例

上一篇:sql server 中删除表中数据truncate和delete的区别(转载自.net学习网)


下一篇:使用Visual Studio Code打开浏览器查看HTML文件