[INFOR] 考幹題PE 機械工敵

題目連結：https://oj.infor.org/contests/13/problems/73
　　這題剛開始看到的時候完全沒有頭緒，後來某個晚上我被Andrew Yang嗆了之後感到很不爽，然後就四處亂逛發現了莫隊算法並寫到隔天早上終於AC，不過由於不是最佳解所以被rejudge了QQ，之後要了看不懂的提示之後，再次亂逛發現了BIT解，然後終於AC了。
　　掃過去遇到一個數字a，將a的上次的位置的值歸零並將這次的位置+1，由於要取區間總和所以用BIT維護舊好，然後要使歸零的地方不會影響到就必須離線作，將所有詢問依照右界排序；若不用離散化而用unordered_map來記錄位置的話會TLE。
　　有空再把莫隊的解丟上來吧ＸＤ

#include<bits/stdc++.h>
#define pi pair<pair<int,int>,int>
using namespace std;
int bit[2000009];
int n,m;
int id[2000009],ss[2000009];
pi q[2000009];
int ans[2000009];
inline void add(int x,int i)
{
    while(i <= n)
    {
        bit[i] += x;
        i += i&-i;
    }
}
inline int sum(int i)
{
    int res = 0;
    while(i > 0)
    {
        res += bit[i];
        i -= i&-i;
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> id[i], ss[i-1] = id[i];
    sort(ss,ss+n); int dis = unique(ss,ss+n)-ss;
    for(int i = 1; i <= n; i++) id[i] = lower_bound(ss,ss+dis,id[i])-ss;
    memset(ss,-1,sizeof(ss));
    for(int i = 0; i < m; i++) cin >> q[i].first.second >> q[i].first.first, q[i].second = i;
    sort(q,q+m);
    int cnt = 0;
    for(int i = 1; i <= n; i++)
    {
        if(ss[id[i]] != -1) add(-1,ss[id[i]]);
        ss[id[i]] = i;
        add(1,i);
        while(cnt < m && q[cnt].first.first == i)
        {
            ans[q[cnt].second] = sum(q[cnt].first.first)-sum(q[cnt].first.second-1);
            cnt++;
        }
    }
    for(int i = 0; i < m; i++) cout << ans[i] << endl;
}