傳送門

題意：給出平面上$N$個(gè)點(diǎn)，求滿足以下兩個(gè)條件的矩形：①左下角與右上角各有一個(gè)點(diǎn)；②矩形內(nèi)部沒(méi)有點(diǎn)。$N \leq 2 \times 10^5$，所有數(shù)字大于等于$0$，保證坐標(biāo)兩兩不同

---

?最開(kāi)始想到的是類似于樓房重建的算法，然后打炸了qwq

在多維問(wèn)題上考慮分治可以降低一維限制，很多時(shí)候都會(huì)用到（比如三維偏序）。

我們先對(duì)$y$值從小到大排序，在分治內(nèi)部對(duì)$x$值從小到大排序，然后考慮左邊一半對(duì)右邊的貢獻(xiàn)。

可以知道對(duì)于左邊一半的兩個(gè)點(diǎn)$a,b(a<b)$，如果$y_a<y_b$，那么$a$會(huì)被$b$阻擋，就不會(huì)對(duì)答案產(chǎn)生貢獻(xiàn)。所以我們可以維護(hù)一個(gè)$y$值遞減的單調(diào)棧來(lái)保存可能對(duì)當(dāng)前詢問(wèn)的點(diǎn)產(chǎn)生貢獻(xiàn)的左邊的點(diǎn)的集合，每一次詢問(wèn)下一個(gè)點(diǎn)時(shí)，把$x$值小于它的其他點(diǎn)加入單調(diào)棧即可。

接下來(lái)我們考慮右邊的點(diǎn)對(duì)右邊產(chǎn)生的影響（右邊的某一些點(diǎn)阻擋了某一些左邊的點(diǎn)產(chǎn)生貢獻(xiàn)）。發(fā)現(xiàn)我們同樣可以維護(hù)一個(gè)$y$值遞增的單調(diào)棧來(lái)保存對(duì)當(dāng)前點(diǎn)有影響的點(diǎn)的集合。每一次我們就取出棧頂?shù)狞c(diǎn)，在左邊的點(diǎn)對(duì)應(yīng)的集合上二分，就可以得到它使多少個(gè)左邊的點(diǎn)不產(chǎn)生貢獻(xiàn)了。

1 //This code is written by Itst 2 #include<bits/stdc++.h> 3 #define BZ 4 #define mid ((l + r) >> 1) 5 using namespace std; 6 7 inline int read(){ 8 int a = 0; 9 bool f = 0; 10 char c = getchar(); 11 while(c != EOF && !isdigit(c)){ 12 if(c == '-') 13 f = 1; 14 c = getchar(); 15 } 16 while(c != EOF && isdigit(c)){ 17 a = (a << 3) + (a << 1) + (c ^ '0'); 18 c = getchar(); 19 } 20 return f ? -a : a; 21 } 22 23 const int MAXN = 200010; 24 struct node{ 25 int x , y; 26 }now[MAXN]; 27 int N , hd , Stack[MAXN] , Stack2[MAXN] , top; 28 long long ans; 29 30 bool cmp1(node a , node b){ 31 return a.y < b.y; 32 } 33 34 bool cmp2(node a , node b){ 35 return a.x < b.x; 36 } 37 38 inline int bis(int x){ 39 int L = 0 , R = hd; 40 while(L < R){ 41 int m = L + R + 1 >> 1; 42 now[Stack[m]].x < x ? L = m : R = m - 1; 43 } 44 return L; 45 } 46 47 void solve(int l , int r){ 48 if(l == r) 49 return; 50 solve(l , mid); 51 solve(mid + 1 , r); 52 int p1 = l , p2 = mid + 1; 53 hd = top = 0; 54 while(p2 <= r){ 55 while(top && now[Stack2[top]].y > now[p2].y) 56 --top; 57 Stack2[++top] = p2; 58 while(p1 <= mid && now[p1].x < now[p2].x){ 59 while(hd && now[Stack[hd]].y < now[p1].y) 60 --hd; 61 Stack[++hd] = p1++; 62 } 63 ans += hd - (top == 1 ? 0 : bis(now[Stack2[top - 1]].x)); 64 p2++; 65 } 66 sort(now + l , now + r + 1 , cmp2); 67 } 68 69 int main(){ 70 #ifdef BZ 71 freopen("4237.in" , "r" , stdin); 72 freopen("4237.out" , "w" , stdout); 73 #endif 74 N = read(); 75 for(int i = 1 ; i <= N ; i++){ 76 now[i].x = read(); 77 now[i].y = read(); 78 } 79 sort(now + 1 , now + N + 1 , cmp1); 80 solve(1 , N); 81 cout << ans; 82 return 0; 83 }

轉(zhuǎn)載于:https://www.cnblogs.com/Itst/p/9873538.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ4237 JOISC2014 稻草人 CDQ分治、单调栈的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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