codeforces 368B B. Sereja and Suffixes(树状数组)

题目链接：

codeforces 368B

题目大意：

给出一个长度为n的序列a,给出m个查询l,对于每个查询输出[l,n]的区间内不同数的个数。

题目分析：

• 将查询按照l的大小排序，从大到小的遍历，每次将>=当前l的位置的a[i]全部加入树状数组，树状数组记录每个数是否出现过。
• 每次结果就是查询树状数组的总和，要保证每个特异的数只加一次。

AC代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define MAX 100007

using namespace std;

typedef pair<int,int> PII;

int n,m;
int ans[MAX];
int a[MAX];
int c[MAX];
PII l[MAX];
const int lim=1e5+1;

int lowbit ( int x )
{
    return x&-x;
}

void add ( int x )
{
    while ( x <= lim )
    {
        c[x]++;
        x += lowbit ( x );
    }
}

int sum ( int x )
{
    int ret = 0;
    while ( x )
    {
        ret += c[x];
        x -= lowbit ( x );
    }
    return ret;
}

int main ( )
{
    while ( ~scanf ( "%d%d" , &n , &m ) )
    {
        for ( int i = 0 ; i < n ; i++ )
            scanf ( "%d" , &a[i] );
        for ( int i = 0 ; i < m ; i++ )
        {
            scanf ( "%d" , &l[i].first );
            l[i].first--;
            l[i].second = i;
        }
        sort ( l , l+m );
        int j = n-1;
        for ( int i = m-1 ; i >= 0 ; i-- )
        {
            //cout << "YES : " << j << " " << a[j] << " " << l[i].first << endl;
            while ( j >= l[i].first )
            {
                if ( sum ( a[j] ) - sum ( a[j]-1 ) == 0 )
                    add ( a[j] );
                j--;
            }
            ans[l[i].second] = sum ( 1e5 );
        }   
        for ( int i = 0 ; i < m ; i++ )
            printf ( "%d\n" , ans[i] );
    }
}