思路:

我们看到这道题,可以一眼想到一维差分

但这样的复杂度是O(nq)的,显然会T

那么怎么优化呢?

我们会发现,差分的时候,在r~r+l-1的范围内

差分增加的值横坐标相同,纵坐标递增

减小的值横坐标和纵坐标都以1为公差递增

那么,我们就可以将差分数组差分

每次标记(r,c)(r,c+1),(r+l,c)(r+l,c+l)即可

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rii register int i
#define rij register int j
#define int long long
using namespace std;
int cf1[][],cf2[][],x[][];
int n,q,r,c,l,s;
inline int rd(){
int y=,f=;char ch=getchar();
while(!isdigit(ch)) {f=ch=='-'?:;ch=getchar();}
while(isdigit(ch)) {y=(y<<)+(y<<)+ch-'';ch=getchar();}
return f?y:-y;
}
signed main()
{
freopen("u.in","r",stdin);
freopen("u.out","w",stdout);
n=rd(),q=rd();
for(rii=;i<=q;i++)
{
r=rd(),c=rd(),l=rd(),s=rd();
cf1[r][c]+=s;
cf1[r+l][c]-=s;
cf2[r][c+]+=s;
cf2[r+l][c+l+]-=s;
}
for(rij=;j<=n;j++)
{
for(rii=;i<=n;i++)
{
cf1[i][j]+=cf1[i-][j];
}
}
for(rii=;i<=n;i++)
{
for(rij=;j<=n;j++)
{
cf2[i][j]+=cf2[i-][j-];
}
}
for(rii=;i<=n;i++)
{
for(rij=;j<=n;j++)
{
x[i][j]+=x[i][j-]+cf1[i][j]-cf2[i][j];
}
}
int ans=;
for(rii=;i<=n;i++)
{
for(rij=;j<=n;j++)
{
ans^=x[i][j];
}
}
printf("%lld",ans);
return ;
}

最新文章

  1. zookeeper源码分析之一服务端启动过程
  2. 深入浅出NodeJS——数据通信,NET模块运行机制
  3. C和指针 第五章 习题
  4. 创建一个List获取数据的lookup
  5. C# JS 单例
  6. Web API应用架构设计分析(1)
  7. Java字节流:ByteArrayInputStream ByteArrayOutputStream
  8. SourceInsight
  9. D5转Xe点滴
  10. OC中实例变量可见度、setter、getter方法和自定义初始化方法
  11. acdream1116 Gao the string!(扩展KMP)
  12. Debug和Release之本质区别
  13. @Html.Partial,@Html.Action,@Html.RenderPartial,@Html.RenderAction
  14. C# 获得Excel工作簿Sheet页面(工作表)集合的名称
  15. XSS跨站脚步攻击及防范
  16. ThinkPHP中处理验证码不显示问题
  17. 【视频编解码&#183;学习笔记】7. 熵编码算法:基础知识 &amp; 哈夫曼编码
  18. Node入门教程(4)第三章:第一个 Nodejs 程序
  19. MVC4 中的Model显示设置(含显示Shared/DisplayTemplates和编辑Shared/EditorTemplates)
  20. Comet——反向Ajax (基础知识)

热门文章

  1. Modern Operating System
  2. Fragment 底部菜单栏
  3. (Stanford CS224d) Deep Learning and NLP课程笔记(一):Deep NLP
  4. Google 嘘! 嘘!
  5. MVC框架以及实例(补充)
  6. 使用Virtual Audio Cable软件实现电脑混音支持电脑录音
  7. December 21st 2016 Week 52nd Wednesday
  8. [EffectiveC++]item06:若不想使用编译器自动生成的函数,就该明确决绝
  9. Charles使用笔记
  10. 大屏FAQ