UPC 2224 / “浪潮杯”山东省第四届ACM大学生程序设计竞赛 1008 Boring Counting 主席树

Problem H:Boring Counting

Time Limit : 6000/3000ms (Java/Other)   Memory Limit : 65535/32768K (Java/Other)

Problem Description

In this problem you are given a number sequence P consisting of N integer and P_i is the i^th 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 P_i is not less than A and not greater than B( L<= i <= R). In other words, your task is to count the number of P_i (L <= i <= R,  A <= P_i <= B).

Input

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 P_i(1 <= P_i <= 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)

Output

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.

Sample Input

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

Sample Output

Case #1:

13

7

3

6

9

 

给你n个数和m条询问，每次查询区间[l,r]中满足A<=x<=B的x的个数。

感觉很不错的一道题，考察主席树的应用。

关于主席树，请参考：http://seter.is-programmer.com/posts/31907.html

建立n棵线段树，线段树root[i]代表区间[1,i]之间一段数字区间出现的次数。

对于每一棵线段树，每个节点表示一个区间[a,b]，记录满足a<=x<=b的x的个数。

因为线段树root[i]是在线段树root[i-1]的基础上增加了一个数得到的，所以可以由root[i-1]得到root[i]。

由于每棵线段树的大小形态都是一样的，而且初始值全都是0，那每个线段树都初始化不是太浪费了？所以一开始只要建一棵空树即可。

然后是在某棵树上修改一个数字，由于和其他树相关联，所以不能在原来的树上改，必须弄个新的出来。难道要弄一棵新树？不是的，由于一个数字的更改只影响了一条从这个叶子节点到根的路径，所以只要只有这条路径是新的，另外都没有改变。比如对于某个节点，要往右边走，那么左边那些就不用新建，只要用个指针链到原树的此节点左边就可以了，这个步骤的前提也是线段树的形态一样。

n是数字个数，这个步骤的空间复杂度显然是O(logn)。

所有树节点的空间消耗为：O(n*4+nlogn)

预处理得到所有的root[i]。

查询时在两棵线段树root[R]和root[L-1]中分别查询区间[A,B]中数的个数，相减即是结果。

本题的时间复杂度：建树：O(n)+预处理O(nlogn)+查询O(logn)

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>

using namespace std;

#define lson l, m, rt->left
#define rson m + 1, r, rt->right

const int MAXN = 52222;
const int INF = (1e9)+10;

struct Node
{
    int sum;   //存储区间[A, B]之间一共有多少个数
    Node *left, *right;
};

Node *root[MAXN];
Node ChairTree[ MAXN * 40 ];
Node *idx;

int pos[MAXN];  //处于位置i的数排第几
int num[MAXN];  //排好序并去重的原始数，相当于把所有数离散化之后的结果
int p[MAXN];    //排第i的是哪个数
int cnt, n, Q;

bool cmp( int a, int b )
{
    return pos[a] < pos[b];
}

Node *nextNode()
{
    idx->sum = 0;
    idx->left = idx->right = NULL;
    return idx++;
}

Node *copyNode( Node *ori )
{
    idx->sum = ori->sum;
    idx->left = ori->left;
    idx->right = ori->right;
    return idx++;
}

void PushUp( Node *rt )
{
    rt->sum = rt->left->sum + rt->right->sum;
    return;
}

void build( int l, int r, Node* rt )   //建立一个空树
{
    if ( l == r ) return;

    int m = ( l + r ) >> 1;

    rt->left = nextNode();
    rt->right = nextNode();

    build( lson );
    build( rson );

    return;
}

void init()
{
    scanf( "%d%d", &n, &Q );

    for ( int i = 1; i <= n; ++i )
    {
        scanf( "%d", &pos[i] );
        p[i] = i;
    }
    sort( p + 1, p + 1 + n, cmp );

    int pre = -INF;
    cnt = 0;
    for ( int i = 1; i <= n; ++i )  //离散化+去重
    {
        if ( pos[ p[i] ] == pre )
            pos[ p[i] ] = cnt;
        else
        {
            pre = pos[ p[i] ];
            num[ ++cnt ] = pos[ p[i] ];
            pos[ p[i] ] = cnt;
        }
    }
    return;
}

Node *add( int val, int l, int r, Node* rt )  //根据上一棵树构造下一棵树
{
    Node *temp = copyNode( rt );

    if ( l == r )
    {
        temp->sum += 1;
        return temp;
    }
    int m = ( l + r ) >> 1;
    if ( val <= m ) temp->left = add( val, lson );
    else temp->right = add( val, rson );
    PushUp( temp );

    return temp;
}

int Query( int L, int R, int l, int r, Node* treeL, Node* treeR )
{
    if ( L <= l && r <= R )
    {
        return treeR->sum - treeL->sum;
    }
    int res = 0;

    int m = ( l + r ) >> 1;
    if ( L <= m ) res += Query( L, R, l, m, treeL->left, treeR->left );
    if ( R > m ) res += Query( L, R, m + 1, r, treeL->right, treeR->right );
    return res;
}

void chuli()
{
    idx = ChairTree;
    root[0] = nextNode();
    build( 1, cnt, root[0] );   //建立一颗空树

    for ( int i = 1; i <= n; ++i )
        root[i] = add( pos[i], 1, cnt, root[i - 1] );   //根据第i-1棵树构造第i棵树
    return;
}

int BiSearch1( int tar )   //查询最左边的 >= x 的数
{
    int low = 1, high = cnt;
    int mid, ans = -1;
    while ( low <= high )
    {
        mid = ( low + high ) >> 1;
        if ( num[mid] >= tar )
        {
            ans = mid;
            high = mid - 1;
        }
        else low = mid + 1;
    }
    return ans;
}

int BiSearch2( int tar )   //查询最右边的 <= x 的数
{
    int low = 1, high = cnt;
    int mid, ans = -1;
    while ( low <= high )
    {
        mid = ( low + high ) >> 1;
        if ( num[mid] <= tar )
        {
            ans = mid;
            low = mid + 1;
        }
        else high = mid - 1;
    }
    return ans;
}

int main()
{
    int T, cas = 0;
    scanf( "%d", &T );
    while ( T-- )
    {
        init();
        chuli();

        printf( "Case #%d:
", ++cas );
        while ( Q-- )
        {
            int l, r, a, b;
            scanf("%d%d%d%d", &l, &r, &a, &b );
            int u = BiSearch1( a );
            int v = BiSearch2( b );
            if ( u == -1 || v == -1 )
            {
                puts("0");
                continue;
            }
            printf( "%d
", Query( u, v, 1, cnt, root[l - 1], root[r] ) );
        }
    }
    return 0;
}