lightoj 1088【树状数组+离散化】

题意：

给你n个数，然后给你q个区间，然后问你这n个数有多少个在这个区间上；

思路：

树状数组搞搞，但是注意到数的范围很大，所以先离散化一下。

初始化初始化！！！卧槽，wa的我好郁闷。。。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=2e5+10;

int arr[N];

int c[N*4];

int n,Q;

void add(int i)

{

    while(i<=n+2*Q)

    {

        c[i]+=1;

        i+=i&(-i);

    }

}

int Sum(int i)

{

    int ans=0;

    while(i>0)

    {

        ans+=c[i];

        i-=i&(-i);

    }

    return ans;

}

vector<int>xs;

int main()

{

    int T,cas=1;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d",&n,&Q);

        xs.clear();

        for(int i=1;i<=n;i++)

        {

            scanf("%d",&arr[i]);

            xs.push_back(arr[i]);

        }

        for(int i=1;i<=2*Q;i+=2)

        {

            scanf("%d%d",&arr[n+i],&arr[n+i+1]);

            xs.push_back(arr[n+i]);

            xs.push_back(arr[n+i+1]);

        }

        sort(xs.begin(),xs.end());

        vector<int>::iterator e=unique(xs.begin(),xs.end());

        for(int i=1;i<=n+2*Q;i++)

            arr[i]=lower_bound(xs.begin(),e,arr[i])-xs.begin()+1;

        memset(c,0,sizeof(c));

        for(int i=1;i<=n;i++)

            add(arr[i]);

        printf("Case %d:\n",cas++);

        for(int i=1;i<=2*Q;i+=2)

            printf("%d\n",Sum(arr[n+i+1])-Sum(arr[n+i]-1));

    }

    return 0;

}

/*

10

5 3

0 0 0 0 0

1 2

1 3

1 2

*/

巴特西

lightoj 1088【树状数组+离散化】

最新文章

热门文章