题目
题目链接：https://loj.ac/problem/2880
JOI 村有一片荒地，上面竖着 \(n\) 个稻草人。任意两个稻草人的横坐标都不相同，任意两个稻草人的纵坐标都不相同。村民们每年多次在稻草人们的周围举行祭典。
有一次，JOI 村的村长听到了稻草人们的启示，计划在荒地中开垦一片田地。和启示中的一样，田地需要满足以下条件：
- 田地的形状是边平行于坐标轴的长方形；
- 左下角和右上角各有一个稻草人；
- 田地的内部（不包括边界）没有稻草人。
给出每个稻草人的坐标，请你求出有多少个满足条件的田地。
思路
网上的题解都是用\(cdq+\)单调栈的优秀算法，但这个\(\color{gray}{\texttt{菜鸡stoorz}}\)实在太菜了，看不懂这些高大尚的算法。所以就写了一个\(cdq+bit+\)线段树的一种常数超级超级超级大的垃圾算法\(qwq\)。然后再bzoj上T飞了，LOJ跑了倒数第一，33321 ms
首先我们发现这个题目所求其实很像三维偏序，所以考虑用\(cdq\)求解。
假设我们现在处理到的区间是\([l,r]\)，我们可以对每一个点求出一个贡献区间\([l_i,r_i]\)，比如说如果这个点\(i\)在左半边，那么列区间为\([l_i,r_i]\)，行区间为\([x_i,mid]\)的矩形内没有任何一个点。
举个栗子，如下图
红色点的贡献区间就是红色+紫色的矩形的列的区间，蓝色点的贡献区间就是蓝色+紫色的矩形的列的区间。黄色、绿色的点的贡献区间就是该颜色的矩形的列的区间。
也就是说，\(mid\)左边的点的贡献区间的下限是该点的纵坐标，右边的点的贡献区间的上限是该点的纵坐标。
为什么要处理出这个贡献区间呢？因为我们发现，如果\(mid\)左边的点\(a\)和\(mid\)右边的点\(b\)满足\(y_a\in [l_b,r_b]\)且\(y_b\in [l_a,r_a]\)，那么这两个点就可以构成一个矩形且这个矩形内没有其他点。例如上图，左边的蓝点和右边的黄点均满足自己的纵坐标在对方的贡献区间内，所以以蓝点为左下角，黄点为右上角的矩形就是一个合法的矩形。
那么我们现在有两个问题需要解决：
- 如何求出每一个点的贡献区间？
- 如何求出哪些点的贡献区间互相包含自己的纵坐标？
一步一步来解决。
1.如何求出每一个点的贡献区间？
按照\(cdq\)常规套路，我们把\(mid\)左右两边的点分别按纵坐标排序。
拿左边的点为例。一个点\(x\)会影响另一个点\(y\)的贡献区间，当且仅当\(x\)严格位于\(y\)的右下角。这样的话\(y\)的贡献区间的下限至少为\(x\)的纵坐标。
所以对于左边的点，我们建立一棵线段树，线段树的区间\([l,r]\)表示横坐标在\(l\sim r\)的点中，最大的纵坐标值。按纵坐标从小到大排完序后顺序枚举，如果现在枚举到点\(i\)，此时线段树内已经插入了\(1\sim i-1\)的点，那么就在线段树中查询\([x_i,mid]\)中的最大值，容易发现这个最大值就是这个点的贡献区间的下限。然后再将\(i\)插入，继续往下计算。
这样我们就在\(O(n\log n)\)的时间复杂度内求出了所有区间\([l,r]\)内的点的贡献区间。需要注意，上述例子是在\(mid\)左侧的点的处理方式，\(mid\)右侧的点需要进行一些改变，请自行思考（不想码了\(qwq\)）。
2.如何求出哪些点的贡献区间互相包含自己的纵坐标？
第一反应是莫队，但是莫队的复杂度是\(n\sqrt{n}\)级别的，这道题\(n\leq 2\times 10^5\)，再加上\(cdq\)的\(\log n\)和超级大常数，显然不行。
考虑枚举左边的点，依然按照纵坐标从小到大枚举，假设现在枚举到点\(k\)，我们不难用指针维护出右半部分包含点\(k\)的点。具体的，我们将右半部分的点以及它的贡献区间复制一份到新的数组，然后将原数组按照贡献区间下限\((l)\)从小到大排序，复制后的数组按照贡献区间上限\((r)\)从小到大排序，然后维护两个指针\(i,j\)分别扫描两个数组，对于按\(l\)排序的数组，如果\(a[i].l\leq a[k].y\)，那么我们就把树状数组中\(a[i].r\)的位置加一；对于按\(r\)排序的数组，如果\(b[j].r<a[k].y\)，那么我们就把树状数组中\(b[j].y\)减一；这样下来，树状数组内为1的点就是贡献区间下限在\(k\)的纵坐标下方，而上限不小于\(k\)的纵坐标的点，也就是为\(1\)的点的贡献区间都包含了\(k\)。
那么接下来只要满足\(k\)的贡献区间包含这些点就可以了，很简单，在树状数组中查询区间\([a[k].l,a[k].r]\)的和即可。
这样我们就在\(O(n\log n)\)的时间复杂度内求出了区间\([l,r]\)右半部分的点对左半部分的点的贡献。至此，区间\([l,r]\)的全部运算结束，接下来递归求解即可。
时间复杂度\(O(n\log^2 n)\)。常数极大。
注意要开\(\rm long\ long\)
码了这么多字累死我了qwqwq
代码
\(185\)行，约\(3.44KB\)。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll N=200010,Inf=1e9;
ll n,tot,ans,maxn,c[N*2];
struct node
{
ll x,y,l,r;
}a[N],b[N];
inline bool cmp1(node x,node y)
{
return x.x<y.x;
}
inline bool cmp2(node x,node y)
{
return x.y<y.y;
}
inline bool cmp3(node x,node y)
{
return x.l<y.l;
}
inline bool cmp4(node x,node y)
{
return x.r<y.r;
}
struct BIT
{
ll c[N];
inline void add(ll x,ll val)
{
for (;x<=maxn;x+=x&-x)
c[x]+=val;
}
inline ll ask(ll x)
{
ll ans=0;
for (;x;x-=x&-x)
ans+=c[x];
return ans;
}
inline void clear(ll x)
{
for (;x<=maxn && c[x];x+=x&-x)
c[x]=0;
}
}bit;
struct Treenode
{
ll l,r,minn,maxn;
};
struct Tree
{
Treenode tree[N*8];
inline void build(ll x,ll l,ll r)
{
tree[x].l=l; tree[x].r=r;
if (l==r)
{
tree[x].maxn=1; tree[x].minn=maxn;
return;
}
ll mid=(l+r)>>1;
build(x*2,l,mid); build(x*2+1,mid+1,r);
pushup(x);
}
inline void pushup(ll x)
{
tree[x].maxn=max(tree[x*2].maxn,tree[x*2+1].maxn);
tree[x].minn=min(tree[x*2].minn,tree[x*2+1].minn);
}
inline void update(ll x,ll k,ll val)
{
if (tree[x].l==k && tree[x].r==k)
{
tree[x].maxn=max(tree[x].maxn,val);
tree[x].minn=min(tree[x].minn,val);
return;
}
ll mid=(tree[x].l+tree[x].r)>>1;
if (k<=mid) update(x*2,k,val);
else update(x*2+1,k,val);
pushup(x);
}
inline ll ask(ll x,ll l,ll r,bool type)
{
if (tree[x].l==l && tree[x].r==r)
return type ? tree[x].maxn : tree[x].minn;
ll mid=(tree[x].l+tree[x].r)>>1;
if (r<=mid) return ask(x*2,l,r,type);
else if (l>mid) return ask(x*2+1,l,r,type);
else
{
if (type) return max(ask(x*2,l,mid,type),ask(x*2+1,mid+1,r,type));
else return min(ask(x*2,l,mid,type),ask(x*2+1,mid+1,r,type));
}
}
inline void clear(ll x,ll k)
{
tree[x].maxn=1; tree[x].minn=n;
if (tree[x].l==tree[x].r) return;
ll mid=(tree[x].l+tree[x].r)>>1;
if (k<=mid) clear(x*2,k);
else clear(x*2+1,k);
}
}Tree;
inline void cdq(ll l,ll r)
{
if (l==r) return;
ll mid=(l+r)>>1;
cdq(l,mid); sort(a+l,a+mid+1,cmp2);
cdq(mid+1,r); sort(a+mid+1,a+r+1,cmp2);
for (ll i=mid;i>=l;i--)
{
a[i].r=Tree.ask(1,a[i].x,maxn,0); a[i].l=a[i].y+1;
Tree.update(1,a[i].x,a[i].y);
}
for (ll i=mid;i>=l;i--) Tree.clear(1,a[i].x);
for (ll i=mid+1;i<=r;i++)
{
a[i].l=Tree.ask(1,1,a[i].x,1); a[i].r=a[i].y-1;
Tree.update(1,a[i].x,a[i].y);
b[i]=a[i];
}
for (ll i=mid+1;i<=r;i++) Tree.clear(1,a[i].x);
sort(a+mid+1,a+r+1,cmp3); sort(b+mid+1,b+r+1,cmp4);
for (ll i=mid+1,j=mid+1,k=l;k<=mid;k++)
{
for (;a[j].l<=a[k].y && j<=r;j++)
bit.add(a[j].y,1);
for (;b[i].r<a[k].y && i<=r;i++)
bit.add(b[i].y,-1);
ans+=bit.ask(a[k].r)-bit.ask(a[k].l-1);
}
for (ll i=l;i<=r;i++)
bit.clear(a[i].y);
}
int main()
{
scanf("%lld",&n);
for (ll i=1;i<=n;i++)
scanf("%lld%lld",&a[i].x,&a[i].y);
for (ll i=1;i<=n;i++) c[i]=a[i].x;
sort(c+1,c+1+n);
tot=unique(c+1,c+1+n)-c-1;
for (ll i=1;i<=n;i++)
{
a[i].x=lower_bound(c+1,c+1+tot,a[i].x)-c;
maxn=max(maxn,a[i].x);
}
for (ll i=1;i<=n;i++) c[i]=a[i].y;
sort(c+1,c+1+n);
tot=unique(c+1,c+1+n)-c-1;
for (ll i=1;i<=n;i++)
{
a[i].y=lower_bound(c+1,c+1+tot,a[i].y)-c;
maxn=max(maxn,a[i].y);
}
Tree.build(1,1,maxn);
sort(a+1,a+1+n,cmp1);
cdq(1,n);
printf("%lld",ans);
return 0;
}