正解:$cdq$分治

解题报告:

传送门$QwQ$

$umm$总感觉做过这题的亚子,,,?

先把坐标离散化,然后把所有点先按$x$排序$QwQ$,然后用类似平面最近点对的方法,先分别解决$mid$两侧的,然后现在就只要考虑两个端点分别在两侧的点了$QwQ$

考虑枚举右上的点然后计算左下有多少个点满足条件?

首先对于左下的点,由条件二可得显然是要维护一个横坐标单增纵坐标单减的单调栈

然后对于右上的点$(x_i,y_i)$,发现就找到满足$y\leq y_i,x\leq x_i$的点的$y_{max}$,然后在左侧的单调栈中二分找到所有满足$y\geq y_{max}$的点,计入答案就成$QwQ$

然后发现这个找$y_max$的也可以用单调栈维护?就维护一个横坐标单增纵坐标单增的单调栈昂$QwQ$

然后就做完辣?$QwQ$

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define gc getchar()

#define ll long long

#define t(i) edge[i].to

#define w(i) edge[i].wei

#define fy(i) edge[i].fy

#define ri register int

#define rb register bool

#define rc register char

#define rp(i,x,y) for(ri i=x;i<=y;++i)

#define my(i,x,y) for(ri i=x;i>=y;--i)

#define lb(x) lower_bound(st+1,st+1+n,x)-st

#define e(i,x) for(ri i=head[x];i;i=edge[i].nxt)

const int N=2e5+;

int n,st[N];

ll as;

struct node{int x,y;}nod[N],t1[N],t2[N],stck1[N],stck2[N];

il int read()

{

    rc ch=gc;ri x=;rb y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

il bool cmp(node gd,node gs){return gd.x<gs.x;}

il int fd(ri dat,ri lim)

{

    ri l=,r=lim;

    while(l<r){ri mid=(l+r)>>;if(stck1[mid+].y>dat)r=mid;else l=mid+;}

    return r;

}

void solv(ri l,ri r)

{

    if(l==r)return;ri mid=(l+r)>>;solv(l,mid);solv(mid+,r);

    int num1=,num2=,top1=,top2=,i=l,j=mid+;

    for(j=mid+;j<=r;++j)

    {

        t2[++num2]=nod[j];

        while(i<=mid && nod[i].y<nod[j].y)

        {

            t1[++num1]=nod[i];

            while(top1 && stck1[top1].x<nod[i].x)--top1;

            stck1[++top1]=nod[i];++i;

        }

        while(top2 && stck2[top2].x>nod[j].x)--top2;

        stck2[++top2]=nod[j];

        as+=top1-fd(stck2[top2-].y,top1);

    }

    while(i<=mid)t1[++num1]=nod[i++];

    i=,j=;ri nw=l-;

    while(i<=num1 && j<=num2)if(t1[i].y<t2[j].y)nod[++nw]=t1[i++];else nod[++nw]=t2[j++];

    while(i<=num1)nod[++nw]=t1[i++];

    while(j<=num2)nod[++nw]=t2[j++];

}

int main()

{

    freopen("4237.in","r",stdin);freopen("4237.out","w",stdout);

    n=read();rp(i,,n)nod[i]=(node){read()+,st[i]=read()+};

    sort(st+,st++n);rp(i,,n)nod[i].y=lb(nod[i].y);sort(nod+,nod++n,cmp);rp(i,,n)nod[i].x=i;

    solv(,n);printf("%lld",as);

    return ;

}

巴特西

$bzoj4237$稻草人 $cdq$分治

正解:$cdq$分治

解题报告:

最新文章

热门文章