嘟嘟嘟

首先人人都能想到是线段树,不过二维线段树肯定会MLE+TLE的。

我们换一种想法,不去修改整个区间,而是修改一个点:开横竖两个线段树,分别记录哪些行和列被修改了。因为如果两阵红雾碰撞,则会因为密度过大而沉降消失,所以自然想到亦或。

统计的时候求出这个矩形内有哪些行和列被修改了,接着把这些行和列的长度累加到答案中,但这样的话交点处不仅会重加,而实际上应该是0,所以在减去两倍的被修改的行,列数。

综上:单点亦或修改,区间查询。

 #include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define rg register
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-;
const int maxn = 1e5 + ;
inline ll read()
{
ll ans = ;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) {last = ch; ch = getchar();}
while(isdigit(ch)) {ans = ans * + ch - ''; ch = getchar();}
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < ) x = -x, putchar('-');
if(x >= ) write(x / );
putchar(x % + '');
} int n, m, q;
struct Tree
{
int l[maxn << ], r[maxn << ], sum[maxn << ];
Tree()
{
Mem(l, ); Mem(r, );
Mem(sum, );
}
void build(int L, int R, int now)
{
l[now] = L; r[now] = R;
if(L == R) return;
int mid = (L + R) >> ;
build(L, mid, now << );
build(mid + , R, now << | );
}
void update(int idx, int now)
{
if(l[now] == r[now]) {sum[now] ^= ; return;}
int mid = (l[now] + r[now]) >> ;
if(idx <= mid) update(idx, now << );
else update(idx, now << | );
sum[now] = sum[now << ] + sum[now << | ];
}
int query(int L, int R, int now)
{
if(L == l[now] && R == r[now]) return sum[now];
int mid = (l[now] + r[now]) >> ;
if(R <= mid) return query(L, R, now << );
else if(L > mid) return query(L, R, now << | );
else return query(L, mid, now << ) + query(mid + , R, now << | );
}
}X, Y; int main()
{
n = read(); m = read(); q = read();
X.build(, n, ); Y.build(, m, );
for(int i = ; i <= q; ++i)
{
int d = read();
if(d == )
{
int x = read(), y = read();
X.update(x, ); Y.update(y, );
}
else
{
int xa = read(), ya = read(), xb = read(), yb = read();
int a = X.query(xa, xb, ), b = Y.query(ya, yb, );
write((ll)a * (ll)(yb - ya + ) + (ll)b * (ll)(xb - xa + ) - (ll)a * b * );
enter;
}
}
return ;
}

最新文章

  1. TFS 掩蔽或取消掩蔽工作区中的文件夹
  2. actionlib的身世之谜
  3. Java 接口中常量的思考
  4. iOS中图片动画的三种模式及基本的代码实现
  5. 在python中使用图形库matplotlib
  6. iOS开发UI篇—Quartz2D使用(矩阵操作)
  7. 20145120 《Java程序设计》第8周学习总结
  8. WPF串口通信数据采集
  9. windows8 认识及使用
  10. Python随机生成验证码的两种方法
  11. 2017-1-15-libubox analysis
  12. js内置构造函数属性修改问题
  13. [51nod1232]完美数
  14. SUN平台服务器光纤共享存储互斥失败如何恢复数据?
  15. BFC知识点概括与总结
  16. Mac homebrew-1.5以后安装php扩展的方法
  17. Tomcat 控制台UTF-8乱码问题
  18. 网络工具之chisel + openvpn混合
  19. SQL Server函数之空值处理
  20. Python 实例方法、类方法、静态方法的区别与作用

热门文章

  1. [转载]ZendStudio格式化html错位问题修正
  2. 游标的小知识(转载and整理)
  3. css三栏布局方案整理
  4. springboot mybatis 使用多数据源
  5. Python基础学习总结(七)
  6. C Primer Plus note4
  7. struts2 国际化语言转换
  8. 修改phpmyadmin不能导入大文件的限制
  9. mui.ajax()和asp.net sql服务器数据交互【1】
  10. response.setHeader()下载的用法