NOIP 模拟 $19\; \rm u$
2024-08-30 06:34:26
题解 \(by\;zj\varphi\)
二维差分的题目
维护两个标记,一个向下传,一个向右下传;
对于每次更新,我们可以直接更新 \((r,c)+s,(r+l,c)-s\) ; \((r,c+1)-s,(r+l,c+l+1)+s\),每组的后一个都是为了消除影响
Code
#include<bits/stdc++.h>
#define ri register signed
#define p(i) ++i
using namespace std;
namespace IO{
char buf[1<<21],*p1=buf,*p2=buf;
#define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++
template<typename T>inline void read(T &x) {
ri f=1;x=0;register char ch=gc();
while(ch<'0'||ch>'9') {if (ch=='-') f=0;ch=gc();}
while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
x=f?x:-x;
}
}
using IO::read;
namespace nanfeng{
#define FI FILE *IN
#define FO FILE *OUT
template<typename T>inline T cmax(T x,T y) {return x>y?x:y;}
template<typename T>inline T cmin(T x,T y) {return x>y?y:x;}
typedef long long ll;
static const int N=2e3+7;
int n,q,r,c,l,s;
ll fg1[N][N],fg2[N][N],res;
inline int main() {
// FI=freopen("nanfeng.in","r",stdin);
// FO=freopen("nanfeng.out","w",stdout);
read(n),read(q);
for (ri i(1);i<=q;p(i)) {
read(r),read(c),read(l),read(s);
fg1[r][c]+=s,fg2[r][c+1]-=s;
fg1[r+l][c]-=s,fg2[r+l][c+l+1]+=s;
}
for (ri i(1);i<=n;p(i)) {
register ll fg=0;
for (ri j(1);j<=n;p(j)) {
fg+=fg1[i][j]+fg2[i][j];
res^=fg;
fg1[i+1][j]+=fg1[i][j];
fg2[i+1][j+1]+=fg2[i][j];
}
}
printf("%lld\n",res);
return 0;
}
}
int main() {return nanfeng::main();}
最新文章
- calendar的一些操作
- 获取访问者的IP
- 总结Spring、Hibernate、Struts2官网下载jar文件
- python 取两数的百分比
- 解决img标签间距问题
- 【CodeForces 605A】BUPT 2015 newbie practice #2 div2-E - Sorting Railway Cars
- shiro连接数据库
- RelativeLayout相对布局中拖放控件的办法
- 黄聪:Mysql数据库还原备份提示MySQL server has gone away 的解决方法(备份文件数据过大)
- java开发--JavaScript
- 增加几个entity framework 的函数 (记录备忘)[转]
- VIPS:基于视觉的页面分割算法[微软下一代搜索引擎核心分页算法]
- Codeforces Helpful Maths
- js中的事件委托详解
- logback:用slf4j+logback实现多功能日志解决方案
- hibernate多表查询封装实体
- mybatis的foreach标签
- Silverlight设计器——Path
- doctype和Quirks模式
- ";No user exists for uid 501";