热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

二维树状数组+差分【p4514】上帝造题的七分钟

Description“第一分钟,X说,要有矩阵,于是便有了一个里面写满了\(0\)的\(n\timesm\)矩阵。第二分钟,L说,要能修改,于是便有了将左上角为\((a,b)\)




Description


“第一分钟,X说,要有矩阵,于是便有了一个里面写满了\(0\)\(n\times m\)矩阵。


第二分钟,L说,要能修改,于是便有了将左上角为\((a,b)\),右下角为\((c,d)\)的一个矩形区域内的全部数字加上一个值的操作。


第三分钟,k说,要能查询,于是便有了求给定矩形区域内的全部数字和的操作。


第四分钟,彩虹喵说,要基于二叉树的数据结构,于是便有了数据范围。


第五分钟,和雪说,要有耐心,于是便有了时间限制。


第六分钟,吃钢琴男说,要省点事,于是便有了保证运算过程中及最终结果均不超过32位有符号整数类型的表示范围的限制。


第七分钟,这道题终于造完了,然而,造题的神牛们再也不想写这道题的程序了。”


——《上帝造裸题的七分钟》 所以这个神圣的任务就交给你了。


Input


输入数据的第一行为X n m,代表矩阵大小为\(n \times m\)
从输入数据的第二行开始到文件尾的每一行会出现以下两种操作:



  • L a b c d delta —— 代表将\((a,b),(c,d)\)为顶点的矩形区域内的所有数字加上delta。

  • k a b c d —— 代表求\((a,b),(c,d)\)为顶点的矩形区域内所有数字的和。


请注意,\(k\)为小写。


Output


针对每个k操作,在单独的一行输出答案。



裸的二维树状数组问题.


二维前缀和:
\[ sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j] \]
考虑差分:
\[ d[i][j]表示a[i][j]与a[i-1][j]+a[i][j-1]-a[i-1][j-1]的差 \]
此时小推一下式子即可.


区间修改,区间查询
\[ \sum_{i=1}^{x}\sum_{j=1}^{y}\sum_{k=1}^{i}\sum_{h=1}^{j}d[h][k] \]
这个时候记录每个位置的\(d[h][k]\)出现了几次.


所以式子变形得到.
\[ \sum_{i=1}^{x}\sum_{j=1}^{y}d[i][j] \times (x-i+1) \times (y-j+1) \]
然后把式子展开.就变成这个
\[ (x+1)\times (y+1)\times \sum_{i=1}^{x}\sum_{j=1}^{y}d[i][j]-(y+1)\times\sum_{i=1}^{x}\sum_{j=1}^{y}d[i][j]\times i -(x+1)\sum_{i=1}^{x}\sum_{j=1}^{y}d[i][j]\times j + \sum_{i=1}^{x}\sum_{j=1}^{y}d[i][j] \times i \times j \]
然后四个树状数组数组分别维护这些东西:


\(d[i][j],d[i][j]\times i ,d[i][j] \times j,d[i][j] \times i\times j\)


代码


#include
#include
#define N 2050
#define R register
using namespace std;
inline void in(int &x)
{
int f=1;x=0;char s=getchar();
while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}
while(isdigit(s)){x=x*10+s-'0';s=getchar();}
x*=f;
}
int t1[N][N],t2[N][N],t3[N][N],t4[N][N],n,m;
#define lowbit(x) x&-x
inline void add(int x,int y,int del)
{
for(R int i=x;i<=n;i+=lowbit(i))
for(R int j=y;j<=m;j+=lowbit(j))
{
t1[i][j]+=del;
t2[i][j]+=del*x;
t3[i][j]+=del*y;
t4[i][j]+=del*x*y;
}
}
inline void ado(int xa,int ya,int xb,int yb,int z)
{add(xa,ya,z);add(xa,yb+1,-z);add(xb+1,ya,-z);add(xb+1,yb+1,z);}
inline int que(int x,int y)
{
R int res=0;
for(R int i=x;i;i-=lowbit(i))
for(R int j=y;j;j-=lowbit(j))
res+=(x+1)*(y+1)*t1[i][j]-(y+1)*t2[i][j]-(x+1)*t3[i][j]+t4[i][j];
return res;
}
inline int query(int xa,int ya,int xb,int yb)
{return que(xb,yb)-que(xb,ya-1)-que(xa-1,yb)+que(xa-1, ya-1);}
char s[6];
int main()
{
in(n),in(m);
for(R int a,b,c,d,x;~scanf("%s",s+1);)
{
in(a),in(b),in(c),in(d);
if(s[1]=='L')in(x),ado(a,b,c,d,x);
else printf("%d\n",query(a,b,c,d));
}
}




推荐阅读
  • UNP 第9章:主机名与地址转换
    本章探讨了用于在主机名和数值地址之间进行转换的函数,如gethostbyname和gethostbyaddr。此外,还介绍了getservbyname和getservbyport函数,用于在服务器名和端口号之间进行转换。 ... [详细]
  • 本文详细探讨了KMP算法中next数组的构建及其应用,重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现,帮助读者更好地理解KMP算法的核心原理。 ... [详细]
  • 本文将介绍如何编写一些有趣的VBScript脚本,这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例,帮助您了解VBScript的基本语法和功能。 ... [详细]
  • 本文详细介绍如何使用Python进行配置文件的读写操作,涵盖常见的配置文件格式(如INI、JSON、TOML和YAML),并提供具体的代码示例。 ... [详细]
  • 扫描线三巨头 hdu1928hdu 1255  hdu 1542 [POJ 1151]
    学习链接:http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想,后期可以求解很 ... [详细]
  • 从 .NET 转 Java 的自学之路:IO 流基础篇
    本文详细介绍了 Java 中的 IO 流,包括字节流和字符流的基本概念及其操作方式。探讨了如何处理不同类型的文件数据,并结合编码机制确保字符数据的正确读写。同时,文中还涵盖了装饰设计模式的应用,以及多种常见的 IO 操作实例。 ... [详细]
  • 题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅!-----&# ... [详细]
  • 本文介绍如何使用Objective-C结合dispatch库进行并发编程,以提高素数计数任务的效率。通过对比纯C代码与引入并发机制后的代码,展示dispatch库的强大功能。 ... [详细]
  • 本文详细介绍了如何在Linux系统上安装和配置Smokeping,以实现对网络链路质量的实时监控。通过详细的步骤和必要的依赖包安装,确保用户能够顺利完成部署并优化其网络性能监控。 ... [详细]
  • 在前两篇文章中,我们探讨了 ControllerDescriptor 和 ActionDescriptor 这两个描述对象,分别对应控制器和操作方法。本文将基于 MVC3 源码进一步分析 ParameterDescriptor,即用于描述 Action 方法参数的对象,并详细介绍其工作原理。 ... [详细]
  • 前言--页数多了以后需要指定到某一页(只做了功能,样式没有细调)html ... [详细]
  • 本文详细解析了Python中的os和sys模块,介绍了它们的功能、常用方法及其在实际编程中的应用。 ... [详细]
  • 本文详细介绍了C语言中链表的两种动态创建方法——头插法和尾插法,包括具体的实现代码和运行示例。通过这些内容,读者可以更好地理解和掌握链表的基本操作。 ... [详细]
  • 尽管使用TensorFlow和PyTorch等成熟框架可以显著降低实现递归神经网络(RNN)的门槛,但对于初学者来说,理解其底层原理至关重要。本文将引导您使用NumPy从头构建一个用于自然语言处理(NLP)的RNN模型。 ... [详细]
  • 本文详细介绍了Akka中的BackoffSupervisor机制,探讨其在处理持久化失败和Actor重启时的应用。通过具体示例,展示了如何配置和使用BackoffSupervisor以实现更细粒度的异常处理。 ... [详细]
author-avatar
手机用户2502914467
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有