BZOJ4237 稻草人

题面

$JOI$村有一片荒地,上面竖着$N$个稻草人,村民们每年多次在稻草人们的周围举行祭典。有一次,$JOI$村的村长听到了稻草人们的启示,计划在荒地中开垦一片田地。和启示中的一样,田地需要满足以下条件:田地的形状是边平行于坐标轴的长方形;左下角和右上角各有一个稻草人;田地的内部(不包括边界)没有稻草人。给出每个稻草人的坐标,请你求出有多少遵从启示的田地的个数.

简化题面

给出N个点,求使得两点为矩阵左下角右上角且形成矩阵内无点的点对数量。

思路

首先想到分治。(别问我为什么)

考虑一种类似于$CDQ$的分治。首先根据$x$排序,一个一个一个一个一个排序好。然后CDQ$(1,n)$每次用$mid$划分,我们把$y$大于$mid$的分到上方,小于的放到下方,那么答案一定是如图所示的这样。

一定是像这样的

考虑每次用右上角的点去找左下角的点对,发现可能的答案一定出现在下方$x$从小到大依次加入根据$y$维护的单调下降栈中。但是可能的答案一定全部可行吗?

如图加入了一个绿色点,红色的矩形 全 部 木 大

我们发现了还要维护在上方的该点左边第一个比它低的点,这个的话维护一个$y$单调上升的栈就可以了/kk。然后用这个点的$x$坐标在下方的单调下降栈里面二分。减去被遮挡住的点即可。

然后递归分治$[l,mid]$$[mid+1,r]$求解即可。

Ps.上方可能与左下角产生贡献的点定在上方根据$y$单调下降的栈中,但是我们对于每一个上方的点都操作下也是可以的,因为那些不在上面的点贡献会被挡掉减掉。

代码

#include<bits/stdc++.h>
#define MAXN 200005
using namespace std;
long long ans;
int N,up_top,down_top;
int Y[MAXN],up_stack[MAXN],down_stack[MAXN],lsh[MAXN];
struct node{int x,y;}P[MAXN];
bool cmp(node a,node b){return a.x<b.x;}
int Find(int l,int r,int v){
	int ret=r+1;
    while(l<=r)
	{
        int mid=(l+r)>>1;
        if(down_stack[mid]>v) ret=mid,r=mid-1;
        else l=mid+1;
    }
    return ret;
}
void CDQ(int l,int r){
    int LY[MAXN],RY[MAXN],up_top=0,down_top=0;
    if(l==r)return;
    int mid=(l+r)>>1,L=l,R=mid+1;
    for(int i=l;i<=r;i++){
        if(Y[i]>mid){
            while(up_top&&Y[up_stack[up_top]]>Y[i]) up_top--;
            up_stack[++up_top]=i; RY[R++]=Y[i];
            ans+=down_top-Find(1,down_top,up_stack[up_top-1])+1;
        }
        else{
            while(down_top&&Y[down_stack[down_top]]<Y[i]) down_top--;
            down_stack[++down_top]=i; LY[L++]=Y[i];
        }
    }
    for(int i=l;i<=mid;i++) Y[i]=LY[i];
    for(int i=mid+1;i<=r;i++) Y[i]=RY[i];
    CDQ(l,mid); CDQ(mid+1,r);
}
int main(){
    
    scanf("%d",&N);
    for(int i=1;i<=N;i++) scanf("%d%d",&P[i].x,&P[i].y),lsh[i]=P[i].y;
    sort(P+1,P+N+1,cmp); sort(lsh+1,lsh+N+1);
    for(int i=1;i<=N;i++) Y[i]=lower_bound(lsh+1,lsh+N+1,P[i].y)-lsh;
    CDQ(1,N);
    cout<<ans<<endl;
    return 0;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇