正題

題目鏈接:https://loj.ac/problem/2880

---

題目大意

給出平面上的$n$個點，然后求有多少個矩形滿足

左下角和右上角各有一個點

矩形之間沒有其他點

$1\le n\le 2\times 10^5,1\le x_i,y_i\le 10^9,$保證$x_i,y_i$分別不重復出現。

---

解題思路

按照$x$排序，考慮$CDQ$分治后左邊對右邊的影響，對$y$從大到小排序然后左右各自維護一個單調棧，左邊考慮每個點第一個右上角的點，右邊維護一個$y$軸遞減，$x$軸遞增的單調棧，然后再右邊的單調棧上二分出左邊的合法位置即可。

時間復雜度$O(n{\log }^{2}n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=2e5+10; struct node{int x,y; }p[N]; int n,s[N],t[N]; long long ans; bool cmp(node x,node y){return x.x<y.x;} bool cMp(node x,node y){return x.y>y.y;} void CDQ(int l,int r){if(l==r)return;int mid=(l+r)>>1;CDQ(l,mid);CDQ(mid+1,r);sort(p+l,p+mid+1,cMp);sort(p+mid+1,p+r+1,cMp);int z=mid+1,top=0,toq=0;for(int i=l;i<=mid;i++){while(z<=r&&p[z].y>=p[i].y){while(top>0&&p[z].x<p[s[top]].x)top--;s[++top]=z;z++;}while(toq>0&&p[i].x>p[t[toq]].x)toq--;if(toq){int L=1,R=top;while(L<=R){int mid=(L+R)>>1;if(p[s[mid]].y>p[t[toq]].y)L=mid+1;else R=mid-1;}ans+=top-L+1;}else ans+=top;t[++toq]=i;}return; } int main() {scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d%d",&p[i].x,&p[i].y);sort(p+1,p+1+n,cmp);CDQ(1,n);printf("%lld\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的Loj#2880-「JOISC 2014 Day3」稻草人【CDQ分治,单调栈,二分】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。