P10814 【模板】离线二维数点

原题链接：P10814 【模板】离线二维数点

Tag：二维数点、

题目描述

给你一个长为 \(n\) 的序列 \(a\)，有 \(m\) 次询问，每次询问给定 \(l,r,x\)，求 \([l,r]\) 区间中小于等于 \(x\) 的元素个数。

数据说明：

\(1\le n,m,a_i,l,r,x\le 2\times10^6\)

分析

我们可以把题目中的 \(a_i\) 理解成二维平面上的点 \((i,a_i)\)。如下图所示：

之后反观题里我们要处理的查询， 在二维平面上的几何意义。

我们会发现当我们把数字放到二维平面上之后， 查询的本质就变成了在一个矩形中有多少点。 仔细观察发现我们要求的这个区间 \([l,r]\) 里有多少点， 实际上可以通过用区间 \([1,r]\) 的点减去区间 \([1,l-1]\) 的点来实现。

这启示我们可以把一个查询拆成如上的两部分，记录这个查询的 \(id\)， 以及这一部分是要加上的还是要减去的， 把全部查询离线下来进行求解。

具体求解过程是我们从左向右去做，维护之前有多少个比 \(x\) 小的数字， 这是一个类逆序对问题，我们可以使用 \(\text{Fenwick}\) 求解。

代码实现

struct Fenwick {
    static const int fenwickMax = 2e6 + 5;
    int n;
    int tree[fenwickMax];
    int lowBit(int x) { return -x & x; }
    void init(int x) { n = x; }
    void add(int x, int k) {
        while (x <= n) {
            tree[x] += k;
            x += lowBit(x);
        }
    }
    int query(int x) {
        int ans = 0;
        while (x) {
            ans += tree[x];
            x -= lowBit(x);
        }
        return ans;
    }
};
Fenwick fenwick;
void NeverSayNever() {
    struct query {
        int x, id, tag;
    };
    int n, m;
    cin >> n >> m;
    fenwick.init(n);
    vector<int> vec(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> vec[i];
    }
    vector<vector<query>> q(n + 1);
    vector<int> ans(m + 1);
    for (int i = 1; i <= m ; ++i) {
        int l,r,x; cin >> l >> r >> x;
        q[l-1].push_back({x, i, -1});
        q[r].push_back({x,i,1});
    }
    for (int i = 1; i <= n ; ++i) {
        fenwick.add(vec[i],1);
        for(auto &[x,id,tag] : q[i]){
            ans[id] += tag * fenwick.query(x);
        }
    }
    for (int i = 1; i <= m ; ++i) {
        cout << ans[i] << endl;
    }
}

额外思考

笑点解析： 写这个题解的当天是 \(\text{ICPC}\) 网络赛第一场当天， 但是我因为学校的逆天安排不能打， 报名费打水漂了， 而且法定节假日我还在上早八。

日志

本页面创建于 2024/09/15 09:22