Skip to content

11265: 【原1265】raising pigs

题目

题目描述

author: 王立力 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1265

Description

小明读博后决定养猪致富,他现在有一个n*n(行和列编号分别为0~n-1)的猪圈。他一有空就会干如下两件事情:

1.买若干只猪养在某个猪圈格子里

2.数一数一个矩形里有多少只猪

但是小明要忙着买饲料,所以他想请你帮忙写一个程序完成这些事。

Input Format

第一行一个整数n,表示猪圈大小

以下若干行每行第一个数c,表示要干的事情的类型

  1. c=1,后面有3个整数x,y,a,表示在x,y位置增加了a只猪

  2. c=2,后面有4个整数 x1,y1,x2,y2,表示查询矩形(x1,y1,x2,y2)里猪的数量

  3. 表示结束

对于100%的数据有

n<=2000,0<=x,y,x1,y1,x2,y2<=n-1

a<=2000

总操作个数<=200000

保证最终答案在int范围内

Output Format

对于每一个询问(2,x1,y1,x2,y2),用一行输出矩形(x1,y1,x2,y2)里猪的数量

Sample Input

3 2 0 0 2 2 1 1 1 1 2 0 0 2 2 1 1 1 2 2 0 0 2 2 3

Sample Output

0 1 3

yyong119's solution

#include <iostream>
#include <cstdio>
#define MAX_N 2050
using namespace std;
int n, op;
int tree[MAX_N][MAX_N];
inline int read() {
    char ch = getchar(); int flag = 1, res = 0;
    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if (ch == '-') flag = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') res = res * 10 + ch - '0', ch = getchar();
    return res;
}
void add(int x, int y, int num) {
    for (; x <= n; x += x & -x)
        for (int tmp_y = y; tmp_y <= n; tmp_y += tmp_y & -tmp_y)
            tree[x][tmp_y] += num;
}
int query(int x, int y) {
    int res = 0;
    for (; x; x -= x & -x)
        for (int tmp_y = y; tmp_y; tmp_y -= tmp_y & -tmp_y)
            res += tree[x][tmp_y];
    return res;
}
int main() {
    n = read(); op = read();
    while(op != 3) {
        if (op == 1) {
            int x = read(), y = read(), a = read();
            ++x; ++y;
            add(x, y, a);
        }
        else {
            int x1 = read(), y1 = read(), x2 = read(), y2 = read();
            ++x1; ++x2; ++y1; ++y2;
            printf("%d\n", query(x2, y2) + query(x1 - 1, y1 - 1) - query(x2, y1 - 1) - query(x1 - 1, y2));
        }
        op = read();
    }
    return 0;
}