矩形面积并(只覆盖一次的面积)的裸题。好久没写代码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;
}

最新文章

  1. Highchart插件下载与安装
  2. Delphi的分配及释放---New/Dispose, GetMem/FreeMem及其它函数的区别与相同
  3. Linux查看系统状态命令
  4. PetaPoco利用ODP.NET Managed Driver连接Oracle
  5. 《DSP using MATLAB》示例Example5.7
  6. 安卓中級教程(9):pathbutton中的animation.java研究(2)
  7. android studio 导入一个已有的android studio project作为lib使用
  8. Linux 下如何安装软件
  9. 尚学堂Spring视频教程(一):模拟Spring
  10. Scrum Meeting 9-20151211
  11. JQuery Jsonp 跨域
  12. Magicodes.WeiChat——多租户的设计与实现
  13. 千寻浏览器 1.0 Beta 1(524)(2014年5月27日)
  14. 深入理解ThreadLocal
  15. SQL备份表及相关笔记
  16. 数据库连接池 c3p0 demo 代码和分析
  17. Maven的生命周期
  18. 如何利用百度音乐播放器的API接口来获取高音质歌曲
  19. java Swing 如何添加点击可展开菜单控件( JMenuBar如何使用?)
  20. 初识Selenium(二)

热门文章

  1. Python的集合与字典练习
  2. pandas知识点(汇总和计算描述统计)
  3. System.AccessViolationException”类型的第一次机会异常在 System.Data.dll 中发生 其他信息: 尝试读取或写入受保护的内存。这通常指示其他内存已损坏。
  4. package.json文件特殊符号含义
  5. vim的常用操作
  6. JS空数组的判断
  7. [网站公告]11月26日00:00-04:00阿里云RDS升级
  8. java环境变量配置(Windows &amp; Linux)
  9. [转]/dev/null 命令用法
  10. jquery的html、text、val的用法