Bzoj4237 cdq分治+树状数组+单调栈

二维平面在某区域内点的问题，要么树套树，kdtree，要么就是cdq分治了。
然而这题树套树和kdtree都不是很好搞的样子，于是我们就只能cdq分治了。
首先把点按照横坐标x排序，在每一层我们需要算出右边的点和左边的点组成的点对的贡献。
我们先把这些点按照纵坐标降序排列。
考虑我们按照纵坐标从大到小扫描到的每一个点。
如果他是右边的点，需要横坐标比他上面的点大才能直接加入，否则他会挡住其右上方的点，使其无法成为答案。
于是单调栈维护一下就好了。
对于左边的点，他能构成答案的纵坐标区间，一定要在他本身纵坐标以上且其右上方的点的最低纵坐标以下才行。
所以这个，我们可以用树状数组以横坐标x为下标维护纵坐标y的后缀min(什么你说树状数组只能维护前缀？后缀坐标转化为n-x[i]+1不就成前缀了？)。
然后就是查询，由于我懒得考虑二分的细节了，所以又用另外一个树状数组维护右面的点在纵坐标y上的区间和。
详见下面的图。

注意这题保证横纵坐标没有重复，所以对拍写maker的时候注意不要出重复坐标，否则网上的代码谁跟谁跑的都不一样，别问我怎么知道的。
然后给一组数据：
5
3 1
1 3
2 5
4 2
5 4
答案是4。
最后上代码：

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #define lli long long int
  5 using namespace std;
  6 const int maxn=2e5+1e2;
  7 const int inf=0x3f3f3f3f;
  8 
  9 struct Node {
 10     int x,y;
 11     friend bool operator < (const Node &a,const Node &b) {
 12         return a.x < b.x;
 13     }
 14 }ns[maxn];
 15 
 16 int x[maxn],y[maxn];
 17 int id[maxn],stk[maxn],top;
 18 int n;
 19 lli ans;
 20 
 21 struct BinaryIndexTreeA {
 22     int dat[maxn];
 23     #define lowbit(x) (x&-x)
 24     BinaryIndexTreeA() { memset(dat,0x3f,sizeof(dat)); }
 25     inline void update(int pos,int x) {
 26         while( pos <= n ) dat[pos] = min( dat[pos] , x ) , pos += lowbit(pos);
 27     }
 28     inline int query(int pos) {
 29         int ret = inf;
 30         while( pos ) ret = min( ret , dat[pos] ) , pos -= lowbit(pos);
 31         return ret;
 32     }
 33     inline void reset(int pos) {
 34         while( pos <= n ) dat[pos] = inf , pos += lowbit(pos);
 35     }
 36 }bx;
 37 struct BinaryIndexTreeB {
 38     lli dat[maxn];
 39     #define lowbit(x) (x&-x)
 40     inline void update(int pos,int x) {
 41         while( pos <= n ) dat[pos] += x , pos += lowbit(pos);
 42     }
 43     inline lli query(int pos) {
 44         lli ret = 0;
 45         while( pos ) ret += dat[pos], pos -= lowbit(pos);
 46         return ret;
 47     }
 48     inline void reset(int pos) {
 49         while( pos <= n ) dat[pos] = 0 , pos += lowbit(pos);
 50     }
 51 }by;
 52 
 53 inline bool cmp(int a,int b) {
 54     return y[a] < y[b];
 55 }
 56 inline void solve(int l,int r) {
 57     if( l == r ) return;
 58     const int mid = ( l + r ) >> 1;
 59     for(int i=l;i<=r;i++) id[i] = i;
 60     sort(id+l,id+r+1,cmp);
 61     top = 0;
 62     for(int i=r;i>=l;i--) {
 63         const int p = id[i];
 64         if( p > mid ) {
 65             while( top && x[stk[top]] > x[p] ) by.update(y[stk[top--]],-1);
 66             stk[++top] = p;
 67             by.update(y[p],1);
 68         } else {
 69             int mxy = bx.query(n-x[p]+1);
 70             mxy = min( mxy , n );
 71             ans += by.query(mxy) - by.query(y[p]-1);
 72             bx.update(n-x[p]+1,y[p]);
 73         }
 74     }
 75     for(int i=r;i>=l;i--) {
 76         const int p = id[i];
 77         if( p > mid ) by.reset(y[p]);
 78         else bx.reset(n-x[p]+1);
 79     }
 80     solve(l,mid);
 81     solve(mid+1,r);
 82 }
 83 
 84 inline void refac(int* sou) {
 85     static int srt[maxn],len;
 86     memcpy(srt+1,sou+1,sizeof(int)*n);
 87     sort(srt+1,srt+1+n);
 88     len = unique(srt+1,srt+1+n) - srt - 1;
 89     for(int i=1;i<=n;i++) sou[i] = lower_bound(srt+1,srt+1+len,sou[i]) - srt;
 90 }
 91 inline void ncpy(int ope) {
 92     if( ope == 1 ) {
 93         for(int i=1;i<=n;i++)
 94             ns[i].x = x[i] , ns[i].y = y[i];
 95     } else if( !~ope ) {
 96         for(int i=1;i<=n;i++)
 97             x[i] = ns[i].x , y[i] = ns[i].y;
 98     }
 99 }
100 
101 int main() {
102     scanf("%d",&n);
103     for(int i=1;i<=n;i++)
104         scanf("%d%d",x+i,y+i);
105     
106     refac(x) , refac(y);
107     ncpy(1) , sort(ns+1,ns+1+n) , ncpy(-1);
108     solve(1,n);
109     
110     printf("%lld
",ans);
111     
112     return 0;
113 }

View Code