OI

【线段树】HH的项链

P1972
妙的，想不到正解。
乍一看就是区间维护查询的基本操作，然而这要求种类数并没有结合律，无法维护。必须要把区间的维护转化。

考虑一个空数组cnt，它的区间和是所要询问区间内的种类数。
如测试数据： 

1
2
a:  1 2 3 4 3 5
cnt:0 0 0 0 0 0

q(1,2)
在区间1,2上标记，查询区间和输出2，OK

1
2
a:  1 2 3 4 3 5
cnt:1 1 0 0 0 0

q(3,5)
如果照着标记，遇到了重复的就只能留一个，输出2

1
2
a:  1 2 3 4 3 5
cnt:1 1 1 1 0 0

q(2,6)
继续扫一遍、标记，输出4

1
2
a:  1 2 3 4 3 5
cnt:1 1 1 1 0 1

这是最朴素的在线做法，这样每次扫一遍复杂度一定是不行的。
注意到每次扫的时候要覆盖前面已处理的数据，所以再考虑离线做法：先把询问按区间右界（或左界）排序，从头更新至右界，这样对于相同右界的询问就无需更新了；而右界向右移动时就考虑只更新原右界至新右界的部分。方法是一张记录当前数字的前一个出现位置的数组，对于相同的数字只保留最右边的一个，更新时遇到相同的数字就记录并删除上一个，维护同一个数只出现一次。
此时的区间和维护，就可以用各类数据结构优化了。
另外离线之后，一定要按原来的询问顺序记录、输出，被这个坑了……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=500005,MAXM=200005,MAX=1000005;
struct node{
    int no,st,ed;
};

node q[MAXM];
int a,t[MAX]={0},pre[MAXN]={0},sgt[MAXN*4];
int ans[MAXM]={0};
bool cmp(node &a,node &b){
    return a.ed<b.ed;
}

int query(int rt,int nst,int ned,int qst,int qed){
    if(qst>ned||qed<nst)
        return 0;
    if(qst<=nst&&qed>=ned)
        return sgt[rt];
    int mid=(nst+ned)>>1;
    return query(rt<<1,nst,mid,qst,qed)+query(rt<<1|1,mid+1,ned,qst,qed);
}

void update(int rt,int nst,int ned,int idx,int val){
    if(nst==ned){
        if(nst==idx)
            sgt[rt]+=val;
        return;
    }
    int mid=(nst+ned)>>1;
    if(idx<=mid)
      update(rt<<1,nst,mid,idx,val);
    else update(rt<<1|1,mid+1,ned,idx,val);
    sgt[rt]=sgt[rt<<1]+sgt[rt<<1|1];
}

int main(){
    int n,m;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a);
        pre[i]=t[a];
        t[a]=i;
    }
    scanf("%d",&m);
    for(int i=0;i<m;i++){
        scanf("%d%d",&q[i].st,&q[i].ed);
        q[i].no=i;
    }
    
    sort(q,q+m,cmp);
    int tmp=1;
    for(int i=0;i<m;i++){
        while(tmp<=q[i].ed){
            update(1,1,n,tmp,1);
            update(1,1,n,pre[tmp],-1);
            tmp++;
        }
        ans[q[i].no]=query(1,1,n,q[i].st,q[i].ed);
    }
    
    for(int i=0;i<m;i++)
        printf("%d\n",ans[i]);
    
    return 0;
}