codeforces 869 E. The Untended Antiquity(树状数组)
2024-08-29 08:59:41
题目链接:http://codeforces.com/contest/869/problem/E
题解:这题是挺好想到solution的但是不太好写,由于题目的特殊要求每个矩形不会重贴所以只要这两个点最内抱着他们的是同一个矩形就行了。就是最近抱汉她们的矩形是同一个就行了。有一种方法挺好的主要是数据是大多数随机的,所以可以考虑hash一下rand一下每个点的赋值然后求前缀和相同就是满足条件的,这里可以用一下2维德树状数组做一下。seed尽量大点这样失败的概率也就小点官方题解有详细的概率数据可以参考一下。然后就这样了........
#include <iostream>
#include <cstring>
#include <cstdio>
#include <map>
using namespace std;
const int M = + ;
typedef unsigned long long ll;
pair<ll , ll> mmp[M][M];
pair<ll , ll> nub[M][M];
void add(int x , int y , pair<int , int> num) {
for(int i = x ; i <= ; i += (i & (-i))) {
for(int j = y ; j <= ; j += (j & (-j))) {
nub[i][j].first += num.first;
nub[i][j].second += num.second;
}
}
}
pair<ll , ll> query(int x , int y) {
pair<ll , ll> res;
for(int i = x ; i ; i -= (i & (-i))) {
for(int j = y ; j ; j -= (j & (-j))) {
res.first += nub[i][j].first;
res.second += nub[i][j].second;
}
}
return res;
}
int main() {
int n , m , q;
int t , r1 , c1 , r2 , c2;
scanf("%d%d%d" , &n , &m , &q);
srand(( << ));
pair<ll , ll> ad , rd;
while(q--) {
scanf("%d%d%d%d%d" , &t , &r1 , &c1 , &r2 , &c2);
if(t == ) {
ad.first = mmp[r1][c1].first = rand();
ad.second = mmp[r1][c1].second = rand();
rd.first = -ad.first;
rd.second = -ad.second;
add(r1 , c1 , ad);
add(r2 + , c1 , rd);
add(r1 , c2 + , rd);
add(r2 + , c2 + , ad);
}
if(t == ) {
rd = mmp[r1][c1];
ad.first = -rd.first;
ad.second = -rd.second;
add(r1 , c1 , ad);
add(r2 + , c1 , rd);
add(r1 , c2 + , rd);
add(r2 + , c2 + , ad);
mmp[r1][c1] = make_pair( , );
}
if(t == ) {
ad = query(r1 , c1);
rd = query(r2 , c2);
if(ad == rd) printf("Yes\n");
else printf("No\n");
}
}
return ;
}
最新文章
- 使用IHTMLDocument2解决弹出";为了让该网站给你提供个人化信息,是否允许在你计算机放置cookie?";
- 在c#中使用指针
- 浅谈AngularJS中的$parse和$eval
- [转]安装和使用JD-Eclipse插件
- 学号20145220 《Java程序设计》第5周学习总结
- VS集成Qt环境搭建
- CSS3实现自定义Checkbox和Radiobox
- bnuoj 16493 Just Pour the Water(矩阵快速幂)
- servlet下载,解决文件名中有中文下载路径出现乱码不能正常下载问题
- 多个Activity和Intent(转)
- DECLARE CONTINUE HANDLER FOR NOT FOUND
- 记vue API 知识点
- visual studio 2010 Error: IntelliSense: identifier ";DWORD"; is undefined
- ftp爆破(python脚本)
- 如何下载西门子产品CAD、3D和EPLAN文件
- Vue中scoped css和css module比较
- ES6-map、filter、find、findIndex讲解
- input file图片上传
- 教你如何用Meterpreter渗透Win系统
- 使用 systemctl 创建 ss 开机
热门文章
- Spring Boot @Condition 注解,组合条件你知道吗
- Tomcat发布War包或者Maven项目
- java并发程序和共享对象实用策略
- 微服务SpringCloud之Spring Cloud Config配置中心Git
- Canvas动画(PC端 移动端)
- 8.9 day30 并发编程 进程理论 进程方法 守护进程 互斥锁
- 实测总结 挂载远程文件夹方案 smb ftp sftp nfs webdav
- Yii 三表关联 角色表、角色权限连接表、权限表
- 动图+源码,演示Java中常用数据结构执行过程及原理
- Python 竟能绘制如此酷炫的三维图