$bzoj4237$稻草人 $cdq$分治

正解:$cdq$分治

解题报告:

传送门$QwQ$

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

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

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

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

然后对于右上的点$(x_i,y_i)$,发现就找到满足$yleq y_i,xleq x_i$的点的$y_{max}$,然后在左侧的单调栈中二分找到所有满足$ygeq 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+10;
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=0;rb y=1;
    while(ch!='-' && (ch>'9' || ch<'0'))ch=gc;
    if(ch=='-')ch=gc,y=0;
    while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),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=0,r=lim;
    while(l<r){ri mid=(l+r)>>1;if(stck1[mid+1].y>dat)r=mid;else l=mid+1;}
    return r;
}
void solv(ri l,ri r)
{
    if(l==r)return;ri mid=(l+r)>>1;solv(l,mid);solv(mid+1,r);
    int num1=0,num2=0,top1=0,top2=0,i=l,j=mid+1;
    for(j=mid+1;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-1].y,top1);
    }
    while(i<=mid)t1[++num1]=nod[i++];
    i=1,j=1;ri nw=l-1;
    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,1,n)nod[i]=(node){read()+1,st[i]=read()+1};
    sort(st+1,st+1+n);rp(i,1,n)nod[i].y=lb(nod[i].y);sort(nod+1,nod+1+n,cmp);rp(i,1,n)nod[i].x=i;
    solv(1,n);printf("%lld",as);
    return 0;
}