BZOJ4237 稻草人

题意

给出 $n,(n\leq 2\times 10^5)$ 个点的坐标,求可以构成矩形左下角和右上角并且矩形中不包含任何其他点的点对个数

题解

分治+单调性
看题解都有点难看懂,但是看程序一下就看得懂
题解理性愉悦一下
首先按照 $x$ 坐标划分然后分治,考虑处理完两个子区间后怎么求当前区间答案
发现对于某个点 $(x,y)$ 我们找到最小的 $y_0$ 使得点 $(x_0,y_0)$ 满足 $x_0>x,y_0>y$ (对左边区间中的点考虑),那么该点在右边的合法配对点坐标只可能满足 $y< y_1< y_0$
那么我们将两个区间分别按照 $y$ 坐标排序,然后依次处理左边,对左边每个点计算右边有多少个点能和它配对
对左边在 $y$ 递减的基础上维护一个 $x$ 相对递增的单调栈,因为对于新加进的点,能限制它的点肯定两个坐标都比他大
然后考虑右边的点怎么算贡献
如果对于一个点 $(x_1,y_1)$ ,存在 $(x_2,y_2)$ 满足 $x_2<x_1,y_2<y_1$(对右边区间中的点考虑),那么 $(x_1,y_1)$ 肯定不会做出贡献
那么右边在 $y$ 单调递减的基础上维护一个 $x$ 相对递增的单调栈就行了
对于左边一个点查询右边有多少点$(x_1,y_1)$ 满足 $y<y_1<y_0$ ,这肯定是一个区间,我们二分一下左端点就行了

程序

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>

#define reg register
#define MAX_N 300007
typedef long long ll;

int N;
int s1[MAX_N], s2[MAX_N];
ll res;

struct point {
    int x, y;

    bool operator < (const point& rhs) const {
        return y > rhs.y;
    }
}p[MAX_N];

bool cmp (point x, point y) { return x.x < y.x; }

void solve (int l, int r) {
    if (l == r) return;
    int mid = l + r >> 1;
    solve(l, mid), solve(mid + 1, r);
    std::sort(p + l, p + mid + 1);
    std::sort(p + mid + 1, p + r + 1);
    int top1 = 0, top2 = 0;
    for (int i = l, j = mid + 1; i <= mid; ++i) {
        while (j <= r && p[j].y >= p[i].y) {
            while (top2 && p[s2[top2]].x > p[j].x)
                top2--;
            s2[++top2] = j++;
        }
        while (top1 && p[s1[top1]].x < p[i].x)
            top1--;
        int mx = p[s1[top1]].y; //[p[i].y,mx]
        s1[++top1] = i;
        int L = 1, R = top2, Mid = 0;
        int pos = top2 + 1;
        while (L <= R) {
            Mid = L + R >> 1;
            if (p[s2[Mid]].y < mx)
                R = Mid - 1, pos = Mid;
            else
                L = Mid + 1;
        }
        res += std::max(0, top2 - pos + 1);
    }
}

int main () {
    read(N);
    for (int i = 1; i <= N; ++i)
        read(p[i].x), read(p[i].y);
    std::sort(p + 1, p + N + 1, cmp);
    p[0].y = 1e9 + 9;
    solve(1, N);
    printf("%lld\n", res);
    return 0;
}

sys_con

OIer,常规 / 竞赛都渣得不行

发表评论

电子邮件地址不会被公开。 必填项已用*标注