VJudge的链接

题意就是问区间不同数的个数

解法1：

莫队，显然

解法2：

离线+树状数组

将询问按照右端点排序，树状数组中保证每一个数最后一次出现的位置为1，其余为0。

解法3：

将解法2中的树状数组可持久化，即得到可在线的主席树做法。

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
const int maxn=33333,maxvalue=1111111;
int n,m,a[maxn],q;
int last[maxvalue];
struct node
{
    node *l,*r;
    int value;
    node():l(0),r(0),value(0){}
    node(node *ll,node *rr):l(ll),r(rr),value((ll?ll->value:0)+(rr?rr->value:0)){}
    node(int vv):l(0),r(0),value(vv){}
};
node *root[maxn];
char memorypool[maxn*sizeof(node)*60];//1 char=1 byte
char *memorypoolptr=memorypool;
inline void* myalloc(size_t size)
{
    return (memorypoolptr+=size)-size;
}
#define newnode new (myalloc(sizeof(node))) node
node* insert(node *x,int k,int L=1,int R=maxn-1)
{
    if (L==R) return newnode(x?x->value+1:1);
    int mid=(L+R)>>1;
    if (k<=mid) return newnode(insert(x?x->l:0,k,L,mid),x?x->r:0);
    else return newnode(x?x->l:0,insert(x?x->r:0,k,mid+1,R));
}
node* erase(node *x,int k,int L=1,int R=maxn-1)
{
    if (x->value==1) return nullptr;
    int mid=(L+R)>>1;
    if (k<=mid) return newnode(erase(x->l,k,L,mid),x->r);
    else return newnode(x->l,erase(x->r,k,mid+1,R));
}
int query(node *x,int l,int L=1,int R=maxn-1)
{
    if (!x) return 0;
    if (l<=L) return x?x->value:0;
    int mid=(L+R)>>1;
    if (l>mid) return query(x->r,l,mid+1,R);
    else return query(x->l,l,L,mid)+query(x->r,l,mid+1,R);
}
int main()
{
    read(n);
    rep(i,1,n) read(a[i]);
    root[0]=newnode();
    rep(i,1,n)
    {
        if (last[a[i]]) root[i]=erase(root[i-1],last[a[i]]);
        else root[i]=root[i-1];
        root[i]=insert(root[i],i);
        last[a[i]]=i;
    }
    read(q);
    rep(i,1,q)
    {
        int x,y;
        read(x,y);
        printf("%d\n",query(root[y],x));
    }
    return 0;
}