[THUPC2017] 天天爱射击 (P7424)

题目链接

洛谷P7424

算法标签

整体二分、树状数组、离线处理

解题思路

1. 问题分析：给定n个点，m个矩形区域查询，每个查询要求统计矩形内的点数量。
2. 整体二分：将所有查询和点的y坐标一起二分，通过分治将问题转化为"小于等于mid的点是否满足条件"，利用树状数组高效维护点的信息。
3. 树状数组应用：对x坐标离散化，用树状数组维护前缀和，支持区间查询和单点更新。
4. 核心步骤：
   • 预处理：点按x排序，查询按y范围排序，x坐标离散化
   • 二分过程：mid为当前y值，将点分为y≤mid和y>mid两类
   • 对y≤mid的点插入树状数组，处理查询中y范围包含mid的情况
   • 递归处理左右子区间，分配答案

#include <bits/stdc++.h>
using namespace std;

struct Point {
    int x, y;
    Point(int x=0, int y=0) : x(x), y(y) {}
};

struct Query {
    int x1, x2, y1, y2, idx;
    Query(int x1=0, int x2=0, int y1=0, int y2=0, int idx=0) 
        : x1(x1), x2(x2), y1(y1), y2(y2), idx(idx) {}
};

int n, m;
vector<Point> points;
vector<Query> queries;
vector<int> ans;
vector<int> xs, ys;

struct FenwickTree {
    vector<int> tree;
    int size;
    FenwickTree(int n) : size(n), tree(n+1, 0) {}
    void update(int idx, int delta) {
        for (; idx <= size; idx += idx & -idx) tree[idx] += delta;
    }
    int query(int idx) {
        int res = 0;
        for (; idx > 0; idx -= idx & -idx) res += tree[idx];
        return res;
    }
    int range_query(int l, int r) {
        return l > r ? 0 : query(r) - query(l-1);
    }
};

void solve(int l, int r, int pl, int pr, vector<Point>& pts, vector<Query>& qs) {
    if (l > r || qs.empty()) return;
    int mid = (l + r) / 2;
    int x_size = xs.size();
    FenwickTree ft(x_size);
    vector<Point> left_pts, right_pts;
    vector<Query> left_qs, right_qs;
    int ptr = pl;
    
    // 插入y <= mid的点到树状数组
    for (int i = pl; i <= pr; ++i) {
        if (pts[i].y <= ys[mid]) {
            int x_idx = lower_bound(xs.begin(), xs.end(), pts[i].x) - xs.begin() + 1;
            ft.update(x_idx, 1);
            left_pts.push_back(pts[i]);
        } else {
            right_pts.push_back(pts[i]);
        }
    }
    
    // 处理查询
    for (auto& q : qs) {
        if (q.y1 <= mid && mid <= q.y2) {
            int lx = lower_bound(xs.begin(), xs.end(), q.x1) - xs.begin() + 1;
            int rx = lower_bound(xs.begin(), xs.end(), q.x2) - xs.begin() + 1;
            ans[q.idx] = ft.range_query(lx, rx);
        }
        if (q.y2 < mid) left_qs.push_back(q);
        else if (q.y1 > mid) right_qs.push_back(q);
    }
    
    // 递归处理左右区间
    solve(l, mid-1, pl, pl + left_pts.size() - 1, left_pts, left_qs);
    solve(mid+1, r, pl + left_pts.size(), pr, right_pts, right_qs);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> m;
    points.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> points[i].x >> points[i].y;
        xs.push_back(points[i].x);
        ys.push_back(points[i].y);
    }
    
    queries.resize(m);
    ans.resize(m);
    for (int i = 0; i < m; ++i) {
        cin >> queries[i].x1 >> queries[i].y1 >> queries[i].x2 >> queries[i].y2;
        queries[i].idx = i;
        ys.push_back(queries[i].y1);
        ys.push_back(queries[i].y2);
    }
    
    // 离散化x坐标
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    
    // 离散化y坐标
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    
    // 整体二分
    solve(0, ys.size()-1, 0, n-1, points, queries);
    
    for (int a : ans) cout << a << '\n';
    return 0;
}

C109 整体二分+树状数组 P7424 [THUPC2017] 天天爱射击