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

jiayixuan1205 · 2024-07-29 11:46:14 · 题解

题意

在一段区间内查询小于等于 x 的元素数量。

分析

可以将每个点看作平面直角坐标系上以横坐标为下标，纵坐标为该点值的一个点，那么该问题就可以转化为一个在矩形中扫描寻找值小于等于 x 的点的问题（容易想到这个矩形横坐标是从 l 到 r，纵坐标是从 0 到 x），用树状数组维护即可。

代码展示

#include<bits/stdc++.h>

using namespace std;

const int N = 2e6+10;
int l,r,x,n,m;
int a[N],ans[N],tree[N];//ans用来存储每次询问的答案，a存储序列，tree用于树状数组的操作 

struct node{
    int id,x,v;
};

vector<node> c[N];//相当于差分处理的一个数组 

inline int lowbit(int x)
{
    return x&(-x);
}

inline void add(int x)
{
    for(int i=x;i<N;i+=lowbit(i))
    {
        tree[i]++;
    }
}

inline int ask(int x)
{
    int ans=0;
    for(int i=x;i>=1;i-=lowbit(i)) ans+=tree[i];//记录区间内的答案 
    return ans;
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++)
    {
        cin>>l>>r>>x;
        c[l-1].push_back({i,x,-1});
        c[r].push_back({i,x,1});//记录每个询问的左右端点差分 
    }
    for(int i=1;i<=n;i++)
    {
        add(a[i]);//计入树状数组 
        for(int j=0;j<c[i].size();j++)
        {
            ans[c[i][j].id]+=c[i][j].v*(ask(c[i][j].x));//记录答案 
        }
    }
    for(int i=1;i<=m;i++) cout<<ans[i]<<endl;
    return 0;
}