题解：P10814 【模板】离线二维数点

· · 题解

题意简述

给定长度为 n 的序列 a，有 m 次询问。

每次询问给定 l,r,x，求区间 [l,r] 中满足 a_i\le x 的元素数量。

解题思路

思想

每个元素 a_i 可以看作二维平面中的一个点 (i,a_i)。

每次询问 (l,r,x) 等价于统计矩形 [l,r]\times[1,x] 内点的数量。

直接二维数据结构会超时，考虑转化为可以 前缀查询 的一维问题。

差分

每次询问是可差分的，区间 [l,r] 可以拆分为 [1,r]-[1,l-1]。

这样每次询问转化为 2 个 前缀询问 (u,x)：统计区间 [1,u] 中满足 a_j\le x 的元素数量。

统计

将所有 2m 个前缀询问按第一维 u 排序。

用序列 b 维护值域，b_k 表示当前第二维为 k 的元素数量。

对于每个前缀询问 (u,x)，先将所有 j\le u 的 a_j 加入序列 b，得到前缀 [1,u] 的状态。

计算 s=\sum_{k=1}^x b_k 表示当前满足 a_j\le x 的元素数量，最后将 s 贡献到对应问题的答案。

使用 树状数组 维护序列 b，实现 O(\log n) 单点修改和区间查询。

参考代码

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

const int N=2000005;
int a[N],c[N],ans[N];
void add(int u){while(u<N){c[u]++;u+=u&-u;}}
int sum(int u){int res=0;while(u){res+=c[u];u-=u&-u;}return res;}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    vector<tuple<int,int,int,int>> s;
    for(int i=1;i<=m;i++)
    {
        int l,r,x;
        cin>>l>>r>>x;
        s.push_back({r,x,i,1});
        s.push_back({l-1,x,i,-1});
    }
    sort(s.begin(),s.end());
    int j=1;
    for(auto [u,x,i,f]:s)
    {
        while(j<=u)add(a[j++]);
        ans[i]+=sum(x)*f;
    }
    for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
    return 0;
}