傳送門

題面：

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

樣例輸入復(fù)制

3 1 4 4 1 3 3

樣例輸出復(fù)制

10

題目來源

ACM-ICPC 2018 徐州賽區(qū)網(wǎng)絡(luò)預(yù)賽

題目描述：

? ??有nn次漲潮和退潮，每次的范圍是個(gè)x×yx×y的矩形，求n次漲退潮后，潮水痕跡的長度。?
?不存在此i,j∈[1,n],i≠j,xi≤xj且yi≤yji,j∈[1,n],i≠j,xi≤xj且yi≤yj?

題目分析：

? ? 題目中有一個(gè)很重要的條件，就是形成的兩個(gè)矩陣必定不能兩兩包含，這個(gè)條件就可以省去我們討論很多情況。

? ? 首先，我們將所有點(diǎn)根據(jù)x坐標(biāo)排序，并根據(jù)加入的時(shí)間分別給他們打上時(shí)間標(biāo)記，可以得到如下圖：

? ? 因?yàn)轭}目中的條件，倘若根據(jù)x進(jìn)行排序，對(duì)應(yīng)的也等價(jià)于對(duì)y坐標(biāo)進(jìn)行排序。我們根據(jù)x的大小遍歷所有的點(diǎn)，我們可以發(fā)現(xiàn)，當(dāng)前的點(diǎn)i的x坐標(biāo)對(duì)答案的貢獻(xiàn)為第1個(gè)點(diǎn)到第i個(gè)點(diǎn)中標(biāo)記單調(diào)遞增的個(gè)數(shù)size*(xi-xi-1)。y同理。

? ? 因此我們可以考慮用單調(diào)隊(duì)列去維護(hù)每一個(gè)點(diǎn)對(duì)答案答案的貢獻(xiàn)。而因?yàn)檎S護(hù)單調(diào)隊(duì)列比較麻煩，因此我們可以考慮倒著維護(hù)單調(diào)隊(duì)列，最后統(tǒng)計(jì)答案即可。時(shí)間復(fù)雜度O（n）。

代碼：

#include <bits/stdc++.h> #define maxn 50005 using namespace std; typedef long long ll; struct Node{ll x,y;int id,a,b;bool operator<(const Node &b){return x<b.x;} }q[maxn]; deque<int>que; int main() {int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%lld%lld",&q[i].x,&q[i].y);q[i].id=i;}sort(q+1,q+1+n);for(int i=1;i<=n;i++){//因?yàn)閥的答案是從n開始統(tǒng)計(jì)的故此要從1開始維護(hù)答案while(!que.empty()&&q[i].id>que.back()) que.pop_back();que.push_back(q[i].id);q[i].a=que.size();}que=deque<int>();for(int i=n;i>=1;i--){//倒著統(tǒng)計(jì)x的答案while(!que.empty()&&q[i].id>que.back()) que.pop_back();que.push_back(q[i].id);q[i].b=que.size();}ll res=0,xx=0,yy=0;for(int i=1;i<=n;i++){//統(tǒng)計(jì)x的答案res+=(q[i].x-xx)*q[i].b;xx=q[i].x;}for(int i=n;i>=1;i--){//統(tǒng)計(jì)y的答案res+=(q[i].y-yy)*q[i].a;yy=q[i].y;}printf("%lld\n",res);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Chen-Jr/p/11007196.html

總結(jié)

以上是生活随笔為你收集整理的ACM-ICPC 2018 徐州赛区网络预赛G （单调队列）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。