#P2683. 简单题

    ID: 1745 传统题 1000ms 512MiB 尝试: 2582 已通过: 602 难度: 7 上传者: 标签>CF2200提高二维树状数组离线预收集坐标局部离散化二分查找容斥原理

简单题

题目描述

你有一个 N×NN\times N 的棋盘,每个格子内有一个整数,初始时的时候全部为 00,现在需要维护两种操作:

命令 参数限制 内容
1 x y A 1≤x,y≤N1\le x,y\le N,AA 是正整数 将格子(x,yx,y)里的数字加上 AA
2 x1 y1 x2 y2 1≤x1≤x2≤N1\le x1 \le x2 \le N,1≤y1≤y2≤N1\le y1 \le y2 \le N 输出 (x1,y1x1,y1),(x2,y2x2,y2)这个矩形内的数字和。
3 无 终止程序

输入格式

输入文件第一行一个正整数 NN。

接下来每行一个操作,以单独一行 3 结束。所有参数按输入的值直接使用。

输出格式

对于每个 22 操作,输出一个对应的答案。

4
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3
3
5

数据规模和约定

对于 100%100\% 的数据满足,1≤N≤5×1051 \le N \le 5 \times 10^5,操作次数不超过 2×1052 \times 10^5 个,每个查询的答案在有符号 32 位整数范围内。

题目来源