20181101noip模拟赛T1
2024-10-20 09:21:09
思路:
我们看到这道题,可以一眼想到一维差分
但这样的复杂度是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 ;
}
最新文章
- zookeeper源码分析之一服务端启动过程
- 深入浅出NodeJS——数据通信,NET模块运行机制
- C和指针 第五章 习题
- 创建一个List获取数据的lookup
- C# JS 单例
- Web API应用架构设计分析(1)
- Java字节流:ByteArrayInputStream ByteArrayOutputStream
- SourceInsight
- D5转Xe点滴
- OC中实例变量可见度、setter、getter方法和自定义初始化方法
- acdream1116 Gao the string!(扩展KMP)
- Debug和Release之本质区别
- @Html.Partial,@Html.Action,@Html.RenderPartial,@Html.RenderAction
- C# 获得Excel工作簿Sheet页面(工作表)集合的名称
- XSS跨站脚步攻击及防范
- ThinkPHP中处理验证码不显示问题
- 【视频编解码&#183;学习笔记】7. 熵编码算法:基础知识 &; 哈夫曼编码
- Node入门教程(4)第三章:第一个 Nodejs 程序
- MVC4 中的Model显示设置(含显示Shared/DisplayTemplates和编辑Shared/EditorTemplates)
- Comet——反向Ajax (基础知识)
热门文章
- Modern Operating System
- Fragment 底部菜单栏
- (Stanford CS224d) Deep Learning and NLP课程笔记(一):Deep NLP
- Google 嘘! 嘘!
- MVC框架以及实例(补充)
- 使用Virtual Audio Cable软件实现电脑混音支持电脑录音
- December 21st 2016 Week 52nd Wednesday
- [EffectiveC++]item06:若不想使用编译器自动生成的函数,就该明确决绝
- Charles使用笔记
- 大屏FAQ