A simple Blog for wyx I've been down the bottle hoping.
BZOJ4237 cdq分治 单调栈
发表于: | 分类: Oi | 评论:0 | 阅读:57

给定平面内一坨点,求有多少个矩形,满足矩形内部没有给定的其他的点

讲道理如果不是$cdq$习题我肯定就往什么奇怪的容斥上去想了
但是既然已经说是$cdq$的题了这题就比较好做了
我们可以先按照x排序,然后分成左右两个部分,然后分治这两个部分,分治的含义就是处理一下这坨点能构成的所有的矩形
接下来我们只要考虑左面的那坨点对右面造成的影响

我们可以枚举左面的点计算一下有多少个右面的点是满足条件的
按照题目要求左面的点是左下角
所以我们可以按照$y$降序排序
然后维护对于左右两坨点维护两个单调栈,左面一坨$x$单调不增右面一坨$x$单调不降
每次把右面比左面大的部分加上
然后算一下两个中间一共有多少个合法点加到答案里
~~为啥……自己画画就知道了~~
举个右面单调不降的栗子,左面同理
错了一遍……因为爆$int$醉了……

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5+5;
const int inf = 0x7fffffff;
inline int read(){
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

struct Poi{
    int x,y;
}a[N],stack1[N],stack2[N];

bool cmp1(const Poi &a,const Poi &b){
    return a.x < b.x;
}

bool cmp2(const Poi &a,const Poi &b){
    return a.y > b.y;
}

long long ans = 0;

void solve(int l,int r){
    if(l==r)return;
    register int i,j;
    int top1=0,top2=0;
    int mid = (l+r) >> 1;
    solve(l,mid); 
    solve(mid+1,r);
    sort(a+l,a+mid+1,cmp2);
    sort(a+mid+1,a+r+1,cmp2);
    for(i=l,j=mid+1;i<=mid;++i){
        while(a[i].y <= a[j].y && j <= r){
            while(a[j].x < stack2[top2].x) top2--;
            stack2[++top2] = a[j]; j ++;
        }
        while(a[i].x > stack1[top1].x) top1--;
        stack1[++top1] = a[i];
        int L,R,tmp1 = stack1[top1-1].y;
        {
            int l = 1, r = top2;
            while(l<=r){
                int mid = (l+r) >> 1;
                if(stack2[mid].y <= tmp1) r = mid - 1;
                else l = mid + 1;
            }
            L = r+1;
        }
        tmp1 = stack1[top1].y;
        {
            int l = 1, r = top2;
            while(l<=r){
                int mid = (l+r) >> 1;
                if(stack2[mid].y <= tmp1) r = mid - 1;
                else l = mid + 1;
            }
            R = r;
        }
        ans += (long long)(R - L + 1);
    }
}

int main(){ //freopen("09.in","r",stdin);
    int n = read();
    stack1[0].x = inf ,stack1[0].y = inf; stack2[0].x = -1,stack2[0].y = inf;
    for(int i=1;i<=n;++i) a[i].x = read(), a[i].y = read();
    sort(a+1,a+n+1,cmp1);
    solve(1,n);
    cout << ans << endl;
}
    
Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP