[题目链接]

https://www.lydsy.com/JudgeOnline/problem.php?id=3132

[算法]

二维树状数组

[代码]

#include<bits/stdc++.h>
using namespace std;
#define MAXN 2050 int n,m,a,b,c,d;
int delta;
int bit[][MAXN][MAXN];
char op[]; inline int lowbit(int x)
{
return x & (-x);
}
inline void modify1(int x,int y,int val)
{
for (register int i = x; i <= n; i += lowbit(i))
{
for (register int j = y; j <= m; j += lowbit(j))
{
bit[][i][j] += val;
}
}
}
inline void modify2(int x,int y,int val)
{
for (register int i = x; i <= n; i += lowbit(i))
{
for (register int j = y; j <= m; j += lowbit(j))
{
bit[][i][j] += val;
}
}
}
inline void modify3(int x,int y,int val)
{
for (register int i = x; i <= n; i += lowbit(i))
{
for (register int j = y; j <= m; j += lowbit(j))
{
bit[][i][j] += val;
}
}
}
inline void modify4(int x,int y,int val)
{
for (register int i = x; i <= n; i += lowbit(i))
{
for (register int j = y; j <= m; j += lowbit(j))
{
bit[][i][j] += val;
}
}
}
inline int query1(int x,int y)
{
int ret = ;
for (register int i = x; i >= ; i -= lowbit(i))
{
for (register int j = y; j >= ; j -= lowbit(j))
{
ret += bit[][i][j];
}
}
return ret;
}
inline int query2(int x,int y)
{
int ret = ;
for (register int i = x; i >= ; i -= lowbit(i))
{
for (register int j = y; j >= ; j -= lowbit(j))
{
ret += bit[][i][j];
}
}
return ret;
}
inline int query3(int x,int y)
{
int ret = ;
for (register int i = x; i >= ; i -= lowbit(i))
{
for (register int j = y; j >= ; j -= lowbit(j))
{
ret += bit[][i][j];
}
}
return ret;
}
inline int query4(int x,int y)
{
int ret = ;
for (register int i = x; i >= ; i -= lowbit(i))
{
for (register int j = y; j >= ; j -= lowbit(j))
{
ret += bit[][i][j];
}
}
return ret;
}
inline void Modify(int x,int y,int delta)
{
modify1(x,y,delta);
modify2(x,y,x * delta);
modify3(x,y,y * delta);
modify4(x,y,x * y * delta);
}
inline int Query(int x,int y)
{
int v1 = query1(x,y),v2 = query2(x,y),v3 = query3(x,y),v4 = query4(x,y);
int ans1 = x * (v1 * y - v3 + v1);
int ans2 = v2 * y - v4 + v2;
int ans3 = v1 * y - v3 + v1;
return ans1 - ans2 + ans3;
} int main()
{ scanf("%s%d%d",&op,&n,&m);
while (scanf("%s",&op) != EOF)
{
if (op[] == 'L')
{
scanf("%d%d%d%d%d",&a,&b,&c,&d,&delta);
Modify(a,b,delta);
Modify(a,d + ,-delta);
Modify(c + ,b,-delta);
Modify(c + ,d + ,delta);
} else
{
scanf("%d%d%d%d",&a,&b,&c,&d);
printf("%d\n",Query(c,d) - Query(a - ,d) - Query(c,b - ) + Query(a - ,b - ));
}
} return ; }

最新文章

  1. yum使用点滴
  2. python之递归实现
  3. window.location.href = window.location.href 跳转无反应 a 超链接 onclick 点击跳转无反应
  4. 二叉堆(二)之 C++的实现
  5. js 在myeclipse中报错
  6. DataTable 筛选数据
  7. 相对URL拼接为绝对URL的过程
  8. JS闭包的概念
  9. linux 安装 Chrome
  10. HDU-1020-Encoding(水题,但题目意思容易搞错,英语的问题)
  11. STL的空间配置器std_alloc 笔记
  12. SICIP-1.3-Defining a new function
  13. uva 10118(DP)
  14. 基于角色的访问控制 (RBAC)权限管理
  15. Kali学习笔记22:缓冲区溢出漏洞利用实验
  16. VS中项目的循环引用的问题
  17. POJ 3264 RMQ水题
  18. 75. ID重新走过,备份表
  19. Falsk的模板分配和蓝图、定制错误信息、 和补充
  20. Windows下安装mysql cluster

热门文章

  1. Java集合(一)--Comparable和Comparator
  2. iOS-关于一些手势冲突问题(scrollView 嵌套 tableView)
  3. MySQL4
  4. Linux配置网卡、网卡会话、网卡bonding
  5. Python反射、异常处理
  6. selenium的调用
  7. A + B Problem Too
  8. 洛谷—— P1657 选书
  9. JavaSE部分之(1)Java基础
  10. Bootstrap基础教程:tutorialspoint-bootstrap