ACM-ICPC 2018 徐州赛区网络预赛-G. Trace
There's a beach in the first quadrant. And from time to time, there are sea waves. A wave ( xx , yy ) means the wave is a rectangle whose vertexes are ( 00 , 00 ), ( xx , 00 ), ( 00 , yy ), ( xx , yy ). Every time the wave will wash out the trace of former wave in its range and remain its own trace of ( xx , 00 ) -> ( xx , yy ) and ( 00 , yy ) -> ( xx , yy ). Now the toad on the coast wants to know the total length of trace on the coast after n waves. It's guaranteed that a wave will not cover the other completely.
Input
The first line is the number of waves n(n \le 50000)n(n≤50000).
The next nn lines,each contains two numbers xx yy ,( 0 < x0<x , y \le 10000000y≤10000000 ),the ii-th line means the ii-th second there comes a wave of ( xx , yy ), it's guaranteed that when 1 \le i1≤i , j \le nj≤n ,x_i \le x_jxi≤xj and y_i \le y_jyi≤yj don't set up at the same time.
Output
An Integer stands for the answer.
Hint:
As for the sample input, the answer is 3+3+1+1+1+1=103+3+1+1+1+1=10
样例输入复制
3 1 4 4 1 3 3
样例输出复制
10
题目来源
思路:对于每个矩阵按照输入顺序分析,先分析矩阵 i 的长xi,求出它被覆盖的长度,即求出 大于矩阵i的高yi的矩阵的长的最大值MaxX,在判断MaxX与xi的大小, MaxX<xi则ans+=xi-MaxX;由于矩阵i对于后面的矩阵没有影响(即不会覆盖后面的矩阵),因此将矩阵i的长xi=0,依此遍历所有矩阵即可找到所有矩阵长的值,同理矩阵高也是如此即可。对于最大值的查找即单点修改可以用线段树来维护。同时xi,yi<1e9还需要对其离散化。
Code :
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
typedef long long LL;
struct node{
int x;
int y;
};
const int MAX_N=50005;
int n;
int a[MAX_N];
node d[MAX_N];
int tree[MAX_N*4];
void PushUp(int id);
void Build(int l,int r,int id);
void Update(int t,int x,int L,int R,int id);
int Query(int l,int r,int L,int R,int id);
int Lower_bound(int L,int R,int x);
int main()
{
map<int,int> mpx,mpy;
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%d%d",&d[i].x,&d[i].y);
mpx[d[i].x]=1; mpy[d[i].y]=1;
}
LL ans=0;
int t=1;
for(auto c:mpx)
mpx[c.first]=t++;
t=1;
for(auto c:mpy)
mpy[c.first]=t++;
memset(a,0,sizeof(a));
for(int i=1;i<=n;++i)
{
t=mpx[d[i].x];
a[t]=d[i].y;
}
Build(1,n,1);
for(int i=1;i<=n;++i)
{
int id=mpx[d[i].x];
t=Query(id+1,n,1,n,1);
if(t<d[i].y) ans+=d[i].y-t;
Update(id,0,1,n,1);
}
memset(a,0,sizeof(a));
for(int i=1;i<=n;++i)
{
t=mpy[d[i].y];
a[t]=d[i].x;
}
Build(1,n,1);
for(int i=1;i<=n;++i)
{
int id=mpy[d[i].y];
t=Query(id+1,n,1,n,1);
if(t<d[i].x) ans+=d[i].x-t;
Update(id,0,1,n,1);
}
printf("%lld\n",ans);
return 0;
}
void PushUp(int id)
{
tree[id]=max(tree[id<<1],tree[id<<1|1]);
}
void Build(int l,int r,int id)
{
if(l==r){
tree[id]=a[r];
return;
}
int h=(l+r)>>1;
Build(l,h,id<<1);
Build(h+1,r,id<<1|1);
PushUp(id);
}
void Update(int t,int x,int l,int r,int id)
{
if(l==r){
tree[id]=a[t]=x;
return;
}
int h=(l+r)>>1;
if(t<=h){
Update(t,x,l,h,id<<1);
}else Update(t,x,h+1,r,id<<1|1);
PushUp(id);
}
int Query(int l,int r,int L,int R,int id)
{
if(l>r) return 0;
if(l<=L&&r>=R){
return tree[id];
}
int h=(L+R)>>1;
int s1=0,s2=0;
if(h>=l) s1=Query(l,r,L,h,id<<1);
if(h+1<=r) s2=Query(l,r,h+1,R,id<<1|1);
return max(s1,s2);
}
上一篇: 数据结构和算法(十)冒泡排序
下一篇: 排序算法之快速排序
推荐阅读
-
ACM-ICPC 2018 徐州赛区网络预赛 H - Ryuji doesn't want to study
-
ACM-ICPC 2018 徐州赛区网络预赛 H. Ryuji doesn't want to study(线段树区间求和)
-
ACM-ICPC 2018 徐州赛区网络预赛 H. Ryuji doesn't want to study—— 树状数组
-
ACM-ICPC 2018 徐州赛区网络预赛 H Ryuji doesn't want to study(线段树 两种做法)
-
【ACM-ICPC 2018 徐州赛区网络预赛】H题 Features Track ---- 树状数组
-
ACM-ICPC 2018 徐州赛区网络预赛 G. Trace (线段树维护)
-
ACM-ICPC 2018 徐州赛区网络预赛 Trace
-
Trace-----ACM-ICPC 2018 徐州赛区网络预赛
-
ACM-ICPC 2018 沈阳赛区网络预赛 F题 Fantastic Graph
-
ACM-ICPC 2018 沈阳赛区网络预赛-Made In Heaven-K短路