欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

ACM-ICPC 2018 徐州赛区网络预赛-G. Trace

程序员文章站 2022-06-04 15:04:57
...

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

ACM-ICPC 2018 徐州赛区网络预赛-G. Trace

样例输入复制

3
1 4
4 1
3 3

样例输出复制

10

题目来源

ACM-ICPC 2018 徐州赛区网络预赛

思路:对于每个矩阵按照输入顺序分析,先分析矩阵 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);
}

 

相关标签: 算法