Time Limit: 3000MS Memory Limit: 65536KB

Submit Statistic Discuss

    In this problem you are given a number sequence P consisting of N integer and Pi is the ith element in the sequence. Now you task is to answer a list of queries, for each query, please tell us among [L, R], how many Pi is not less than A and not greater than B( L<= i <= R). In other words, your task is to count the number of Pi (L <= i <= R,  A <= Pi <= B).

     In the first line there is an integer T (1 < T <= 50), indicates the number of test cases. 
     For each case, the first line contains two numbers N and M (1 <= N, M <= 50000), the size of sequence P, the number of queries. The second line contains N numbers Pi(1 <= Pi <= 10^9), the number sequence P. Then there are M lines, each line contains four number L, R, A, B(1 <= L, R <= n, 1 <= A, B <= 10^9)

    For each case, at first output a line ‘Case #c:’, c is the case number start from 1. Then for each query output a line contains the answer.

1

13 5

6 9 5 2 3 6 8 7 3 2 5 1 4

1 13 1 10

1 13 3 6

3 6 3 6

2 8 2 8

1 9 1 9

Case #1:

13

7

3

6

9

#include <stdio.h>

#include <iostream>

#include <algorithm>

#include <cstdlib>

#include <sstream>

#include <cstring>

#include <bitset>

#include <string>

#include <deque>

#include <stack>

#include <cmath>

#include <queue>

#include <set>

#include <map>

using namespace std;

#define INF 0x3f3f3f3f

#define CLR(arr,val) memset(arr,val,sizeof(arr))

#define LC(x) (x<<1)

#define RC(x) ((x<<1)+1)

#define MID(x,y) ((x+y)>>1)

typedef pair<int,int> pii;

typedef long long LL;

const double PI=acos(-1.0);

const int N=50010;

struct seg

{

    int lson,rson;

    int cnt;

};

seg T[N*20];

int root[N],tot;

pii arr[N];

vector<int>pos;

void update(int &cur,int ori,int l,int r,int pos)

{

    cur=++tot;

    T[cur]=T[ori];

    ++T[cur].cnt;

    if(l==r)

        return ;

    int mid=MID(l,r);

    if(pos<=mid)

        update(T[cur].lson,T[ori].lson,l,mid,pos);

    else

        update(T[cur].rson,T[ori].rson,mid+1,r,pos);

}

int query(int S,int E,int l,int r,int L,int R)

{

    if(L<=l&&r<=R)

        return T[E].cnt-T[S].cnt;

    else

    {

        int mid=MID(l,r);

        if(R<=mid)

            return query(T[S].lson,T[E].lson,l,mid,L,R);

        else if(L>mid)

            return query(T[S].rson,T[E].rson,mid+1,r,L,R);

        else

            return query(T[S].lson,T[E].lson,l,mid,L,mid)+query(T[S].rson,T[E].rson,mid+1,r,mid+1,R);

    }

}

void init()

{

    CLR(root,0);

    tot=0;

    T[0].cnt=T[0].lson=T[0].rson=0;

    pos.clear();

}

int main(void)

{

    int tcase,n,m,l,r,a,b,i;

    scanf("%d",&tcase);

    for (int q=1; q<=tcase; ++q)

    {

        init();

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

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

        {

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

            pos.push_back(arr[i].first);

        }

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

        pos.erase(unique(pos.begin(),pos.end()),pos.end());

        int SZ=pos.size();

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

        {

            arr[i].second=lower_bound(pos.begin(),pos.end(),arr[i].first)-pos.begin()+1;

            update(root[i],root[i-1],0,SZ,arr[i].second);

        }

        printf("Case #%d:\n",q);

        for (i=0; i<m; ++i)

        {

            scanf("%d%d%d%d",&l,&r,&a,&b);

            int A,B;

            A=lower_bound(pos.begin(),pos.end(),a)-pos.begin()+1;

            B=lower_bound(pos.begin(),pos.end(),b)-pos.begin()+1;

            if(pos[B-1]!=b)//上限B的位置要特别计算一下

                --B;

            if(!B||A>B)//特判

                puts("0");

            else

                printf("%d\n",query(root[l-1],root[r],0,SZ,A,B));

        }

    }

    return 0;

}