#P3132. 上帝造题的七分钟

    ID: 2284 传统题 2000ms 512MiB 尝试: 1222 已通过: 381 难度: 6 上传者: 标签>难度分类提高数据结构二维树状数组排序与序列处理二维差分二维前缀和组合数学贡献法CF2000tyvj

上帝造题的七分钟

上帝造题的七分钟

题目背景

第一分钟,X 想要一张填满 00 的 n×mn\times m 矩阵。第二分钟,L 加入了矩形加法。第三分钟,k 加入了矩形求和。

第四分钟,彩虹喵定下了数据范围。第五分钟,和雪定下了时间限制。第六分钟,吃钢琴男约定运算和结果在有符号 3232 位整数的范围内。第七分钟,题目造完了,写程序的任务交给了你。

题目描述

维护一个 nn 行 mm 列的矩阵,初始时所有元素都是 00。行和列分别从 11 编号。矩形用左上角 (a,b)(a,b) 和右下角 (c,d)(c,d) 给出,包含两端及边界上的所有单元。

输入格式

第一行是 X n m,其中 X 是大写字母。

随后每行是一项操作,读到文件结束。

  • L a b c d delta,给矩形内的每个元素加上 delta\mathit{delta}。
  • k a b c d,查询矩形内所有元素的和。k 是小写字母。

输出格式

每次查询输出一行一个整数,表示求得的和。

X 4 4
L 1 1 3 3 2
L 2 2 4 4 1
k 2 2 3 3
12

数据范围

  • 10%10\% 的数据满足 1≤n,m≤161\le n,m\le16,操作不超过 200200 次。
  • 60%60\% 的数据满足 1≤n,m≤5121\le n,m\le512。
  • 全部数据满足 1≤n,m≤20481\le n,m\le2048,1≤a≤c≤n1\le a\le c\le n,1≤b≤d≤m1\le b\le d\le m,−500≤delta≤500-500\le\mathit{delta}\le500,操作不超过 2×1052\times10^5 次。数据保证题目中的矩阵运算及其结果都在有符号 3232 位整数的范围内。