FZU2187 回家种地(矩形面积并)
2024-08-29 22:38:29
矩形面积并(只覆盖一次的面积)的裸题。好久没写代码debug了我太久,太辛酸了。
#pragma warning(disable:4996)
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std; #define ll long long
#define maxn 200005
#define y1 y111 int lf[maxn << 2], rf[maxn << 2];
int sum[maxn << 2];
int a[maxn];
int add[maxn << 2];
int mi[maxn << 2];
int ma[maxn << 2]; int n, nSize; void pushUp(int i)
{
mi[i] = min(mi[i << 1], mi[i << 1 | 1]);
ma[i] = max(ma[i << 1], ma[i << 1 | 1]);
} void pushDown(int i)
{
if (add[i] != 0){
if (lf[i] != rf[i]){
add[i << 1] += add[i];
add[i << 1 | 1] += add[i];
mi[i << 1] += add[i];
ma[i << 1] += add[i];
mi[i << 1 | 1] += add[i];
ma[i << 1 | 1] += add[i];
add[i] = 0;
}
}
} void build(int i, int L, int R)
{
lf[i] = L; rf[i] = R; add[i] = mi[i] = ma[i] = 0;
if (L == R){
sum[i] = a[L];
return;
}
int M = (L + R) >> 1;
build(i << 1, L, M);
build(i << 1 | 1, M + 1, R);
sum[i] = sum[i << 1] + sum[i << 1 | 1];
} void upd(int i, int L, int R,int v)
{
if (L == lf[i] && R == rf[i]){
add[i] += v;
mi[i] += v;
ma[i] += v;
return;
}
pushDown(i);
int M = (lf[i] + rf[i]) >> 1;
if (R <= M){
upd(i << 1, L, R,v);
}
else if (L > M){
upd(i << 1 | 1, L, R, v);
}
else{
upd(i << 1, L, M, v);
upd(i << 1 | 1, M + 1, R, v);
}
pushUp(i);
} ll query(int i)
{
if (ma[i] <= 0) return 0;
if (mi[i] > 1) return 0;
if (ma[i] == mi[i] && ma[i] == 1){
return sum[i];
}
pushDown(i);
return query(i << 1) + query(i << 1 | 1);
} struct Node
{
ll x;
ll bg, ed;
int v;
Node(ll xi, ll bgi, ll edi,int vi) :x(xi), bg(bgi), ed(edi),v(vi){}
bool operator < (const Node &b)const{
return x == b.x ? v>b.v : x < b.x;
}
};
vector<Node> vec;
vector<ll> dis; int main()
{
int T; cin >> T; int ca = 0;
while (T--)
{
scanf("%d", &n);
ll x1, x2, y1, y2;
vec.clear();
vec.reserve(2 * n + 100);
dis.clear();
for (int i = 0; i < n; ++i){
scanf("%I64d%I64d%I64d%I64d", &x1, &y1, &x2, &y2);
vec.push_back(Node(x1, y1, y2,1));
vec.push_back(Node(x2, y1, y2,-1));
dis.push_back(y1);
dis.push_back(y2);
}
sort(dis.begin(), dis.end());
nSize = unique(dis.begin(), dis.end()) - dis.begin();
for (int i = 1; i < nSize; ++i){
a[i] = dis[i] - dis[i - 1];
}
for (int i = 0; i < vec.size(); ++i){
int lid = lower_bound(dis.begin(), dis.begin()+nSize, vec[i].bg) - dis.begin();
int rid = lower_bound(dis.begin(), dis.begin()+nSize, vec[i].ed) - dis.begin();
vec[i].bg = lid + 1;
vec[i].ed = rid;
}
sort(vec.begin(), vec.end());
build(1, 1, nSize - 1); ll ans = 0;
ll preLen = 0;
ll prex = vec[0].x;
for (int i = 0; i < vec.size(); ++i){
ll val = vec[i].x;
while (i<vec.size()&&vec[i].x == val){
upd(1, vec[i].bg, vec[i].ed, vec[i].v);
++i;
}
--i;
ans += preLen*(vec[i].x - prex);
prex = vec[i].x;
preLen = query(1);
}
printf("Case %d: %I64d\n", ++ca, ans);
}
return 0;
}
最新文章
- Highchart插件下载与安装
- Delphi的分配及释放---New/Dispose, GetMem/FreeMem及其它函数的区别与相同
- Linux查看系统状态命令
- PetaPoco利用ODP.NET Managed Driver连接Oracle
- 《DSP using MATLAB》示例Example5.7
- 安卓中級教程(9):pathbutton中的animation.java研究(2)
- android studio 导入一个已有的android studio project作为lib使用
- Linux 下如何安装软件
- 尚学堂Spring视频教程(一):模拟Spring
- Scrum Meeting 9-20151211
- JQuery Jsonp 跨域
- Magicodes.WeiChat——多租户的设计与实现
- 千寻浏览器 1.0 Beta 1(524)(2014年5月27日)
- 深入理解ThreadLocal
- SQL备份表及相关笔记
- 数据库连接池 c3p0 demo 代码和分析
- Maven的生命周期
- 如何利用百度音乐播放器的API接口来获取高音质歌曲
- java Swing 如何添加点击可展开菜单控件( JMenuBar如何使用?)
- 初识Selenium(二)
热门文章
- Python的集合与字典练习
- pandas知识点(汇总和计算描述统计)
- System.AccessViolationException”类型的第一次机会异常在 System.Data.dll 中发生 其他信息: 尝试读取或写入受保护的内存。这通常指示其他内存已损坏。
- package.json文件特殊符号含义
- vim的常用操作
- JS空数组的判断
- [网站公告]11月26日00:00-04:00阿里云RDS升级
- java环境变量配置(Windows &; Linux)
- [转]/dev/null 命令用法
- jquery的html、text、val的用法