FZU 1656 How many different numbers

FZU_1656
    이 제목 과 HDU3333 거의 똑 같 습 니 다. 구체 적 인 사 고 는 제 HDU 를 참고 할 수 있 습 니 다.3333 의 문제 풀이: http://www.cnblogs.com/staginner/archive/2012/04/13/2445104.html.

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#define MAXD 100010

#define MAXQ 1010

int sum[4 * MAXD], N, Q, a[MAXD], tx[MAXD], X, where[MAXD], r[MAXQ];

struct Question

{

    int x, y, ans;

}question[MAXQ];

int cmpint(const void *_p, const void *_q)

{

    int *p = (int *)_p, *q = (int *)_q;

    return *p < *q ? -1 : 1;

}

int cmpq(const void *_p, const void *_q)

{

    int *p = (int *)_p, *q = (int *)_q;

    return question[*p].y < question[*q].y ? -1 : 1;

}

void update(int cur)

{

    int ls = cur << 1, rs = (cur << 1) | 1;

    sum[cur] = sum[ls] + sum[rs];

}

void build(int cur, int x, int y)

{

    int mid = (x + y) >> 1, ls = cur << 1, rs = (cur << 1) | 1;

    sum[cur] = 0;

    if(x == y)

        return ;

    build(ls, x, mid);

    build(rs, mid + 1, y);

}

void init()

{

    int i, j, k;

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

    {

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

        tx[i] = a[i];

    }

    qsort(tx, N, sizeof(tx[0]), cmpint);

    X = 0;

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

        if(i == 0 || tx[i] != tx[i - 1])

        {

            where[X] = -1;

            tx[X ++] = tx[i];

        }

    build(1, 0, N - 1);

    scanf("%d", &Q);

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

    {

        scanf("%d%d", &question[i].x, &question[i].y);

        -- question[i].x, -- question[i].y;

        r[i] = i;

    }

    qsort(r, Q, sizeof(r[0]), cmpq);

}

int BS(int x)

{

    int min = 0, max = X, mid;

    for(;;)

    {

        mid = (min + max) >> 1;

        if(mid == min)

            break;

        if(tx[mid] <= x)

            min = mid;

        else

            max = mid;

    }

    return mid;

}

void refresh(int cur, int x, int y, int k, int c)

{

    int mid = (x + y) >> 1, ls = cur << 1, rs = (cur << 1) | 1;

    if(x == y)

    {

        sum[cur] = c ? 1 : 0;

        return ;

    }

    if(k <= mid)

        refresh(ls, x, mid, k, c);

    else

        refresh(rs, mid + 1, y, k, c);

    update(cur);

}

int query(int cur, int x, int y, int s, int t)

{

    int mid = (x + y) >> 1, ls = cur << 1, rs = (cur << 1) | 1;

    if(x >= s && y <= t)

        return sum[cur];

    if(mid >= t)

        return query(ls, x, mid, s, t);

    else if(mid + 1 <= s)

        return query(rs, mid + 1, y, s, t);

    else

        return query(ls, x, mid, s, t) + query(rs, mid + 1, y, s, t);

}

void solve()

{

    int i, j, k;

    for(i = j = 0; i < N; i ++)

    {

        k = BS(a[i]);

        if(where[k] != -1)

            refresh(1, 0, N - 1, where[k], 0);

        where[k] = i;

        refresh(1, 0, N - 1, i, 1);

        while(j < Q && question[r[j]].y == i)

        {

            question[r[j]].ans = query(1, 0, N - 1, question[r[j]].x, i);

            ++ j;

        }

    }

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

        printf("%d
", question[i].ans);

}

int main()

{

    while(scanf("%d", &N) == 1)

    {

        init();

        solve();

    }

    return 0;

}