Power oj 2459 Submissions of online judge---(树状数组)

Time Limit: 3000 MS Memory Limit: 65536 KB

树状数组 STL

Description

An online judge is a system to test programs in programming contests. The system can compile and execute codes, and test them with pre-constructed data. Submitted code may be run with restrictions, including time limit, memory limit, security restriction and so on. The output of the code will be captured by the system, and compared with the standard output. The system will then return the result. 
Always, Online Judge systems also have a status page where a list of these results is shown. For example, http://acm.swust.edu.cn/ is an Online Judge of SWUST. A following list can be found in the system. As it shows, every submission has a Run ID and User ID. The Run ID is an incrementing sequence from 1 to N, with which a User ID is associated.


Mr. Yang wants to know, from Run ID L to R, how many different Users there are?

Input

The first line is an integer T (1 ≤ T ≤ 10), which stands for the number of test cases you need to solve. For each case, the input format will be like this:
Line 1: N (1 ≤ N ≤ 100,000) indicating the number of submissions.
Line 2: N integers U1, U2…UN (0 ≤ Ui ≤ 1000,000,000). Ui indicates the User ID of the i-th (Run ID) submission.( For the sake of simplicity, User ID is digital)
Line 3: Q (1 ≤ Q ≤ 100,000), the number of Queries.
Next Q lines: each line contains 2 integers L, R representing a Query (1 ≤ L ≤ R ≤ N). Interval contains the endpoint

Output

For each Query, print the number of different Users from L to R in one line.

Sample Input

2
3
1 1 4
2
1 2
2 3
5
1 1 2 1 3
3
1 5
2 4
3 5

Sample Output

1
2
3
2
3

题意：

给你一串数字，问你在一个区间内有多少个不同的数字

解题思路

解题思路是个好东西~ 希望我也能有
     开n个vector来存询问区间的最左端和对应询问的次数（存询问次数是因为方便在最后的时候输出ans[i]）;
     利用树状数组求和；
     将所求a[i]的前一个位置用map来存，（为什么不用数组呢？：是因为开不了那么大！！！哈哈哈哈哈哈哈！！！！zz）

完整代码：

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n;
int a[N];
int c[N];///树状数组
int ans[N];
vector<pair<int,int> >v[N];///开n个vector来存区间起点li,因为是离线的，所以还要存对应的位置
///树状数组的一系列东西:
int lowerbit(int x)
{
    return x&-x;
}
void add(int i,int x)
{
    while(i<=n)
    {
        c[i]+=x;
        i+=lowerbit(i);
    }
}
int SUM(int i)
{
    int sum=0;
    while(i>0)
    {
        sum+=c[i];
        i-=lowerbit(i);
    }
    return sum;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        memset(c,0,sizeof(c));
        for(int i=0;i<=n;i++)
            v[i].clear();
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        int q,l,r;
        scanf("%d",&q);
        for(int i=0;i<q;i++)
        {
            scanf("%d%d",&l,&r);
            v[r].push_back(make_pair(l,i));///v[r]
        }
        map<int,int>lastpose;///lastpose:指的是它的前一位置
        ///为什么要用map:因为数组装不下...太大了1e9!
        //unordered_map<int,int>lastpose;///其实还可以用unordered_map的，而且还要快一点，但是我的CB用不了！！！啊啊啊
        for(int i=1;i<=n;i++)
        {
            if(lastpose[a[i]]!=0)///map初始化的时候是为0的，只要它不为0,就减1;
                add(lastpose[a[i]],-1);
            lastpose[a[i]]=i;
            add(lastpose[a[i]],1);///+1;
            for(int j=0;j<v[i].size();j++)
            {
                int rr=i;
                int ll=v[i][j].first;
                int id=v[i][j].second;
                ans[id]=SUM(rr)-SUM(ll-1);///ans
            }
        }
        for(int i=0;i<q;i++)
            printf("%d\n",ans[i]);
    }
    return 0;
}