【题目链接】

点击打开链接

【算法】

线段树扫描线求周长并

【代码】

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cerrno>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <limits>
#include <list>
#include <map>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <utility>
#include <vector>
#include <cwchar>
#include <cwctype>
#include <stack>
#include <limits.h>
using namespace std;
#define MAXN 5010 int i,L,R,l1,l2,ans,last,n,xa,xb,ya,yb;
int x[MAXN*]; struct info {
int l,r,h,opt;
} y[MAXN*];
struct Node {
int l,r,sum,cnt,c;
bool lc,rc;
} Tree[MAXN*]; bool cmp(info a,info b) { return a.h > b.h; }
template <typename T> inline void read(T &x) {
int f = ; x = ;
char c = getchar();
for (; !isdigit(c); c = getchar()) { if (c == '-') f = -f; }
for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';
x *= f;
}
template <typename T> inline void write(T x) {
if (x < ) { putchar('-'); x = -x; }
if (x > ) write(x/);
putchar(x%+'');
}
template <typename T> inline void writeln(T x) {
write(x);
puts("");
}
inline void build(int index,int l,int r) {
int mid;
Tree[index].l = l;
Tree[index].r = r;
Tree[index].c = Tree[index].sum = Tree[index].cnt = ;
Tree[index].lc = Tree[index].rc = false;
if (l == r) return;
mid = (l + r) >> ;
build(index<<,l,mid);
build(index<<|,mid+,r);
}
inline void push_up(int index) {
if (Tree[index].c > ) {
Tree[index].sum = x[Tree[index].r+] - x[Tree[index].l];
Tree[index].cnt = ;
Tree[index].lc = Tree[index].rc = true;
} else if (Tree[index].l == Tree[index].r) {
Tree[index].sum = Tree[index].cnt = ;
Tree[index].lc = Tree[index].rc = false;
} else {
Tree[index].lc = Tree[index<<].lc;
Tree[index].rc = Tree[index<<|].rc;
Tree[index].sum = Tree[index<<].sum + Tree[index<<|].sum;
Tree[index].cnt = Tree[index<<].cnt + Tree[index<<|].cnt;
if (Tree[index<<].rc && Tree[index<<|].lc) Tree[index].cnt--;
}
}
inline void update(int index,int l,int r,int val) {
int mid;
if (Tree[index].l == l && Tree[index].r == r) {
Tree[index].c += val;
push_up(index);
return;
}
mid = (Tree[index].l + Tree[index].r) >> ;
if (mid >= r) update(index<<,l,r,val);
else if (mid + <= l) update(index<<|,l,r,val);
else {
update(index<<,l,mid,val);
update(index<<|,mid+,r,val);
}
push_up(index);
} int main() { scanf("%d",&n);
l1 = l2 = ;
for (i = ; i <= n; i++) {
read(xa); read(ya); read(xb); read(yb);
x[++l1] = xa;
x[++l1] = xb;
y[++l2] = (info){xa,xb,ya,-};
y[++l2] = (info){xa,xb,yb,};
}
l1 = unique(x+,x+l1+) - x;
sort(x+,x+l1+);
build(,,l1-);
sort(y+,y+l2+,cmp);
ans = last = ;
for (i = ; i < l2; i++) {
L = lower_bound(x+,x+l1+,y[i].l) - x;
R = lower_bound(x+,x+l1+,y[i].r) - x - ;
update(,L,R,y[i].opt);
ans += Tree[].cnt * * (y[i].h - y[i+].h);
ans += abs(Tree[].sum - last);
last = Tree[].sum;
}
L = lower_bound(x+,x+l1+,y[l2].l) - x;
R = lower_bound(x+,x+l1+,y[l2].r) - x - ;
update(,L,R,y[l2].opt);
ans += abs(Tree[].sum - last);
writeln(ans); return ; }

最新文章

  1. Jstat PID not found
  2. .net图片验证码生成、点击刷新及验证输入是否正确
  3. android倒计时(整理)
  4. HBase读写路径的工作机制
  5. PLSQL_性能优化工具系列05_SQL Trace/Event 10046 Trace
  6. cocos2d-x ClippingNode
  7. Logcat中报内存泄漏MemoryLeak的一次分析
  8. MongoDB 任意代码执行漏洞(CVE-2013-4142)
  9. 2015年6月股灾永远载入A股史册
  10. Spark函数详解系列之RDD基本转换
  11. Java虚拟机几个命令行参数说明
  12. 1067: spark.components:NavigatorContent 类型值的隐式强制指令的目标是非相关类型 String
  13. Java之初识
  14. SendMessageUpwards定义简单按钮(Unity3D开发之十)
  15. 积极参与开源项目,促进.NET Core生态社区发展
  16. LeetCode 929.Unique Email Addresses
  17. JAVA Bean和XML之间的相互转换 - XStream简单入门
  18. python之路(四)-set集合
  19. MONGODB数据基础与命令
  20. 液晶屏MIPI接口与LVDS接口区别(总结)

热门文章

  1. HA架构
  2. ***iOS学习之Table View的简单使用和DEMO示例(共Plain普通+Grouped分组两种)
  3. 洛谷——P2865 [USACO06NOV]路障Roadblocks
  4. python读取大文件的方法
  5. Linux中断处理驱动程序编写
  6. VS2012关于hash_map的使用简略
  7. 负载均衡之基于DNS负载
  8. Android 自己定义View须要重写ondraw()等方法
  9. iOS 获取手机 唯一标识
  10. 【转】Selenium2学习路线