传送门

CDQ分治

按$y$坐标分治。

先将$y$坐标排序，对于所选的一段区间$[L,R]$,其中点为$M$,$[L,M]$与$[M+1,R]$中$x$的值单调递增。然后对于左区间即$y$值较小的那一段维护一个$y$值单调递减栈，对于右区间即$y$值较大的维护一个$y$值单调递增的栈。如果抽象成图像也就是这样的：

图像中的那个矩形（画的不是很规范QAQ）就是所求矩形。在上区间最近的一个节点的$x$坐标之前的在下区间的点就是方案数。

//BZOJ 4237//by Cydiater//2016.10.12#include <iostream>#include <cstring>#include <algorithm>#include <queue>#include <map>#include <ctime>#include <cmath>#include <cstdlib>#include <iomanip>#include <algorithm>#include <cstdio>using namespace std;#define ll long long#define up(i,j,n)       for(int i=j;i<=n;i++)#define down(i,j,n)     for(int i=j;i>=n;i--)#define pii pair<int,int>#define mp make_pairconst int MAXN=1e6+5;const int oo=0x3f3f3f3f;inline int read(){    char ch=getchar();int x=0,f=1;    while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}    return x*f;}int N,q1[MAXN],q2[MAXN],head1,tail1,head2,tail2,point,j,k;pii m[MAXN],tmp[MAXN];ll ans;namespace solution{    inline bool cmp1(pii x,pii y){return x.second<y.second;}    void init(){        N=read();        up(i,1,N){            int x=read(),y=read();            m[i]=mp(x,y);        }        m[0].first=-oo;        sort(m+1,m+N+1,cmp1);    }    int get(int lim,int leftt,int rightt){        int mid;        while(leftt+1<rightt){            mid=(leftt+rightt)>>1;            if(m[q2[mid]].first<=lim)leftt=mid;            else                    rightt=mid;        }        if(m[q2[rightt]].first<=lim)return rightt;        return leftt;    }    void slove(int leftt,int rightt){        int mid=(leftt+rightt)>>1;        if(leftt==rightt)return;        slove(leftt,mid);slove(mid+1,rightt);        head1=head2=1;tail1=tail2=0;point=leftt;        up(i,mid+1,rightt){            while(head1<=tail1&&m[i].second<m[q1[tail1]].second)tail1--;            q1[++tail1]=i;            while(m[point].first<m[i].first&&point<=mid){                while(head2<=tail2&&m[point].second>m[q2[tail2]].second)tail2--;                q2[++tail2]=point++;            }            ans+=(ll)(tail2-get(m[q1[tail1-1]].first,0,tail2));        }        j=leftt;k=mid+1;        up(i,leftt,rightt)tmp[i]=((k<=rightt&&m[j].first>m[k].first)||j>mid)?m[k++]:m[j++];        up(i,leftt,rightt)m[i]=tmp[i];    }}int main(){    //freopen("input.in","r",stdin);    using namespace solution;    init();    slove(1,N);    cout<<ans<<endl;    return 0;}

BZOJ4237: 稻草人