hdu 4417 树状数组离线处理

分手后的思念是犯贱 2022-07-28 01:04 174阅读 0赞

[点击打开链接][Link 1]

题意: 给定n个数, 有m个查询, 每次查询要求输出l~r之间小于val的数的个数 n,m<=100000;

分析: 可以先将查询排序, 再将n个数排序, 排序之前分别记录下他们的位置, 然后对于每次查询, 把n个数中所有的小于val的数的位置的地方在树状数组中加一,

然后查询l和r之间的数的数量就是这次查询的答案;

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    #define F first
    #define S second
    using namespace std;
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;int f=1;
        while((c=getchar())<'0' || c>'9')if(c=='-')f=-1;
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res*f;
    }
    const int N=100010,MOD=1e9+7;
    struct st
    {
        int l,r,val,id;
    }b[N];
    int ans[N],bit[N];
    
    void add(int i)
    {
        for(;i<N;i+=i&-i) bit[i]++;
    }
    
    int sum(int i)
    {
        int s=0;
        for(;i;i-=i&-i) s+=bit[i];
        return s;
    }
    
    bool cmp(st a, st b)
    {
        return a.val < b.val;
    }
    pii a[N];
    int main()
    {
        int T=in(),ca=1;
        while(T--)
        {
            int n=in(),m=in();
            for(int i=0;i<n;i++) scanf("%d",&a[i].F),a[i].S=i+1;
            mem(bit,0);
            for(int i=0;i<m;i++)
            {
                b[i].l=in()+1,b[i].r=in()+1;
                b[i].val=in(),b[i].id=i;
            }
            sort(b,b+m,cmp);
            sort(a,a+n);
            int j=0;
            for(int i=0;i<m;i++)
            {
                for(;j<n && a[j].F<=b[i].val;j++)
                {
                    add(a[j].S);
                }
                ans[b[i].id]=sum(b[i].r)-sum(b[i].l-1);
            }
            printf("Case %d:\n",ca++);
            for(int i=0;i<m;i++)
            {
                printf("%d\n",ans[i]);
            }
        }
        return 0;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=4417