代码源每日一题div1【离线+树状数组】数数

本是古典何须时尚 2024-03-16 16:37 48阅读 0赞

[数数 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge]

题意：

![b71933aea11146bba5ec614449dee2f6.png][]

思路：

考虑离线，然后用DS维护序列

将询问离线后把询问按h从小到大排序，把a数组也从小到大排序，可以发现在遍历询问的时候答案就很好维护了

具体地说，遍历询问的时候，可以用一个指针维护val<q\[i\].h的所有值，指针idx左边的元素都是满足条件的元素，但是它们的位置需要在q\[i\].L,q\[i\].R之间，也就是说，我们需要找到idx已经遍历过的元素中位置在q\[i\].L，q\[i\].R之间的元素个数

这个可以用线段树/树状数组来维护，这两个都是序列DS，可以维护位置序列，也可以维护权值序列

**关于离线问题，可以先给询问和序列按关键字排序，然后遍历询问时用序列DS维护**

Code：

#include <bits/stdc++.h>
    
    #define low(x) (x&(-x))
    #define int long long
    
    using namespace std;
    
    const int mxn=1e5+10;
    
    struct ty{
        int pos,val;
    }a[mxn];
    
    struct ty2{
        int id,L,R,h;
    }q[mxn];
    
    int N,Q;
    int tr[mxn],ans[mxn];
    
    bool cmp(ty x,ty y){
        return x.val<y.val;
    }
    
    bool cmp2(ty2 x,ty2 y){
        return x.h<y.h;
    }
    
    void add(int pos,int k){
        for(int i=pos;i<=N;i+=low(i)) tr[i]+=k;
    }
    
    int sum(int pos){
        int res=0;
        for(int i=pos;i;i-=low(i)) res+=tr[i];
        return res;
    }
    
    void init(){
        for(int i=0;i<=N;i++){
            tr[i]=0;
        }
    }
    void solve(){
        cin>>N>>Q;
        init();
        for(int i=1;i<=N;i++){
            cin>>a[i].val;
            a[i].pos=i;
        }
        sort(a+1,a+1+N,cmp);
        for(int i=1;i<=Q;i++){
            cin>>q[i].L>>q[i].R>>q[i].h;
            q[i].id=i;
        }
        sort(q+1,q+1+Q,cmp2);
        int idx=1;
        for(int i=1;i<=Q;i++){
            while(a[idx].val<=q[i].h&&idx<=N){
                add(a[idx].pos,1);
                idx++;
            }
            ans[q[i].id]=sum(q[i].R)-sum(q[i].L-1);
        }
        for(int i=1;i<=Q;i++) cout<<ans[i]<<" \n"[i==N];
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

[- _ - Daimayuan Online Judge]: http://oj.daimayuan.top/problem/464
[b71933aea11146bba5ec614449dee2f6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/6d72ae757d514d56bdedcd7558586d7c.png