题解：P14426 [JOISC 2014] 稻草人 / Scarecrows

· · 题解

千古神犇大 Toorean 给我看的题目。因为我是感冒期间口胡的，然后好像看错图了，接下来我们认为枚举的点对是左上角和右下角的点对，而并不是题目中左下角和右上角的点对。

注意到产生贡献的点对形式很怪，于是绝大部分情况下可以直接考虑分治。考虑一下按照 x 轴分治，然后划分为 x \le mid 和 x > mid 的两部分。

若 P, Q 跨过 mid 产生贡献当且仅当：

为了刻画中间没有任何点，提前与处理小于等于 mid 部分且横坐标大于等于 P_x 的点中，纵坐标小于等于 P_y 的最大纵坐标 ty，同理预处理横坐标小于等于 Q_x 的点中，纵坐标大于等于 Q_y 的最小纵坐标 sy，那么中间没有点就等价于 sy > P_y \ge Q_y > ty，这本质上是一个二维数点。这个限制比较强，我的处理方式是：将 Q_y \le P_y < sy 的点对减去 Q_y \le ty,P_y < sy 的点对，这样约束就从三个变成两个了。

有用的 x 轴只有 O(n) 个，于是最后就是 O(n\log ^2 n) 的。

代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5;
namespace bit {
    int sum[N + 10], lim;
    int lowbit(int x) {
        return x & (-x);
    }
    void upd(int x, int y) {
        x++;
        while(x <= lim + 1) sum[x] += y, x += lowbit(x);
    }
    int qry(int x) {
        x++; int rest = 0;
        while(x)
            rest += sum[x], x -= lowbit(x);
        return rest;
    }
}

struct node {
    int x, y;
} D[N + 10], P[N + 10];
bool cmp(node &a, node &b) {
    return a.x < b.x;
}
bool cmpp(node &a, node &b) {
    return a.y < b.y;
}
int n, cpx[N + 10], cpy[N + 10];

ll ans = 0;
int ty[N + 10], sy[N + 10];
void solve(int l, int r) {
    if(l >= r) return ;
    int mid = (l + r) >> 1;
    solve(l, mid);
    solve(mid + 1, r);
    set <int> st;
    for(int i = mid; i >= l; i--) {
        if(st.empty()) ty[i] = 0;
        else {
            set <int>::iterator it = st.upper_bound(D[i].y);
            if(it == st.begin()) ty[i] = 0;
            else {
                it--;
                ty[i] = (*it);
            }
        }
        st.insert(D[i].y);
        P[i] = (node){ty[i], D[i].y};
    }
    st.clear();
    for(int i = mid + 1; i <= r; i++) {
        if(st.empty()) sy[i] = n + 1;
        else {
            set <int>::iterator it = st.upper_bound(D[i].y);
            if(it == st.end()) sy[i] = n + 1;
            else sy[i] = (*it);
        }
        st.insert(D[i].y);
        P[i] = (node){D[i].y, sy[i]};
    }

    for(int i = mid + 1; i <= r; i++) {
        bit::upd(D[i].y, 1);
        bit::upd(sy[i], -1);
    }
    for(int i = l; i <= mid; i++)
        ans += (bit::qry(D[i].y));
    for(int i = mid + 1; i <= r; i++)
        bit::upd(D[i].y, -1),
        bit::upd(sy[i], 1);
    sort(P + mid + 1, P + r + 1, cmp);
    sort(P + l, P + mid + 1, cmp);
    int j = mid + 1;
    for(int i = l; i <= mid; i++) {
        while(j <= r && P[j].x <= P[i].x)
            bit::upd(P[j].y, 1), j++;
        ans -= (bit::qry(bit::lim) - bit::qry(P[i].y));
    }
    for(int i = mid + 1; i < j; i++) bit::upd(P[i].y, -1);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    bit::lim = n + 5;
    for(int i = 1; i <= n; i++)
        cin >> D[i].x >> D[i].y, D[i].y = 1000000000 - D[i].y,
        cpx[i] = D[i].x, cpy[i] = D[i].y;

    int len;
    sort(cpx + 1, cpx + n + 1);
    len = unique(cpx + 1, cpx + n + 1) - cpx - 1;
    for(int i = 1; i <= n; i++) D[i].x = lower_bound(cpx + 1, cpx + len + 1, D[i].x) - cpx;
    sort(cpy + 1, cpy + n + 1);
    len = unique(cpy + 1, cpy + n + 1) - cpy - 1;
    for(int i = 1; i <= n; i++) D[i].y = lower_bound(cpy + 1, cpy + len + 1, D[i].y) - cpy;

    sort(D + 1, D + n + 1, cmp);
    solve(1, n);

    cout << ans << '\n';
}