ACM-ICPC 2018 徐州赛区网络预赛-G Trace 题解 树状数组
- 1000ms
- 262144K
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 xxyy ,( 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
题意:每次给出一个点(x,y)表示与(0,0)连成一个矩形;如果后面的矩形覆盖了前面的边,那么这条边就消失了, 最后求剩下的边是多少
思路:分别处理x轴,y轴,然后排序,离散化,然后从最后往前更新处理扫过去,用树状数组维护x y 的最大值。每次加上自己的边长以及减去标号比自己小的并且长度比自己高的个数乘自己的边长
代码:
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=500005;
int x[N],y[N],n;
int xt[N],yt[N];
int treex[N],treey[N];
int sum(int i,int op)//往下搜索最大值
{
int res=0;
while(i)
{
if(op==1) res=max(res,treex[i]);
else res=max(res,treey[i]);
i -= (-i&i);
}
return res;
}
void add(int i,int id,int op)//往上更新树状数组最大值
{
while(i<=N)
{
if(op==1) treex[i]=max(treex[i],id);
else treey[i]=max(treey[i],id);
i += (-i&i);
}
}
int main()
{
scanf("%d",&n);
for(int i=0; i<n; i++)
{
scanf("%d%d",&x[i],&y[i]);
xt[i]=x[i], yt[i]=y[i];
}
sort(xt,xt+n);//分别按x y排序
sort(yt,yt+n);
ll ans=0;
for(int i=n-1; i>=0; i--)//离散化 从最后往前更新处理
{
int xi=lower_bound(xt,xt+n,x[i])-xt+1;
int yi=lower_bound(yt,yt+n,y[i])-yt+1;
ans+=(x[i]-sum(xi,1));//x计算增加的线段
ans+=(y[i]-sum(yi,0));//y
add(xi,x[i],1);//加入数组
add(yi,y[i],0);
}
printf("%lld\n",ans);
return 0;
}
推荐阅读
-
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
-
ACM-ICPC 2018 徐州赛区网络预赛-G Trace 题解 树状数组
-
ACM-ICPC 2018 徐州赛区网络预赛 - G Trace - 思维
-
ACM-ICPC 2018 徐州赛区网络预赛 G. Trace(set,模拟)
-
ACM-ICPC 2018 徐州赛区网络预赛 G. Trace —— 想法+upper_bound
-
ACM-ICPC 2018 徐州赛区网络预赛 G. Trace
-
ACM-ICPC 2018 徐州赛区网络预赛-G. Trace