DLUTOJ #1394 Magic Questions

Time Limit: 3 Sec Memory Limit: 128 MB

Description

Alice likes playing games. So she will take part in the movements of M within N days, and each game is represented in an integer between 1 and M. Roommates have Q magic questions: How many different kinds of games does Alice participate between Lth day and Rth day(including Lth day and Rth day)?

Input

You will be given a number of cases; each case contains blocks of several lines. The first line contains 2 numbers of N and M. The second line contains N numbers implying the game numbers that Alice take part in within N days. The third line contains a number of Q. Then Q lines is entered. Each line contain two numbers of L and R.

1≤N,M,Q≤100000

Output

There should be Q output lines per test case containing Q answers required.

Sample Input

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

Sample Output

3 2 3

HINT

这是今年校赛的K题，一道经典题目，但现场没A。

在线可以用主席树，目前还不会。有一个巧妙的利用数状数组的离线解法，比较好写。

要点是：

1.将查询按右端点从小到大排序。

2.将每个数上一次出现的位置记录下来。当这个数再次出现时，将它上次出现位置上的计数消除。

Implementation:

主体是个双指针。

#include <bits/stdc++.h>

using namespace std;

const int N(1e5+);

int n, m, q, a[N], pos[N], bit[N], ans[N];

void add(int x, int v){

    for(; x<=n; bit[x]+=v, x+=x&-x);

}

int sum(int x){

    int res=;

    for(; x; res+=bit[x], x-=x&-x);

    return res;

}

struct P{

    int l, r, id;

    P(int l, int r, int id):l(l),r(r),id(id){}

    P(){};

    bool operator<(const P&b)const{return r<b.r;}

}p[N];

int main(){

    // ios::sync_with_stdio(false);

    for(; ~scanf("%d%d", &n, &m); ){

        for(int i=; i<=n; i++) scanf("%d", a+i);

        scanf("%d", &q);

        for(int l, r, i=; i<q; i++) scanf("%d%d", &l, &r), p[i]={l, r, i};

        sort(p, p+q);   //error-prone

        memset(bit, , sizeof(bit));

        memset(pos, , sizeof(pos));

        for(int i=, j=, k; j<q&&i<=n; ){  //error-prone

            for(; i<=p[j].r; i++){

                if(pos[a[i]]) add(pos[a[i]], -);

                pos[a[i]]=i;

                add(i, );

            }

            for(k=j; k<q&&p[k].r==p[j].r; k++)  //error-prone

                ans[p[k].id]=sum(p[k].r)-sum(p[k].l-);

            j=k;

        }

        for(int i=; i<q; i++) printf("%d\n", ans[i]); //error-prone

    }

    return ;

}