学步园

HH的项链
问题描述：
HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运，所以每次
散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH 不断地收集新的贝壳，
因此，他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多
少种不同的贝壳？这个问题很难回答……因为项链实在是太长了。于是，他只好求助睿智的
你，来解决这个问题。
输入格式：
第一行：一个整数N，表示项链的长度。
第二行：N 个整数，表示依次表示项链中贝壳的编号（编号为0 到1000000 之间的整数）。
第三行：一个整数M，表示HH 询问的个数。
接下来M 行：每行两个整数，L 和R（1 ≤ L ≤ R ≤ N），表示询问的区间。
输出格式：

M 行，每行一个整数，依次表示询问对应的答案。

样例输入：
6
1 2 3 4 3 5
3
1 2
3 5
2 6
样例输出：
2
2
4
数据范围：
对于20%的数据，N ≤ 100，M ≤ 1000；
对于40%的数据，N ≤ 3000，M ≤ 200000；
对于100%的数据，N ≤ 50000，M ≤ 200000。

先预处理每个点上一个颜色相同的位置

然后进行一遍归并排序（merge）

之后每次查询即可

因为是静态算法不需要修改所以归并即可，若要支持修改需要平衡树

program diff;
var
  mid,q,n,m,i,j,k,l,r,s,e,ans,x,y:longint;
  temp:array [0..1000001] of longint;
  last:array [0..50001] of longint;
  cop:array [0..20,0..50001] of longint;

procedure merge (s,e,now:longint);
var
  mid,i,j,k:longint;
begin
  if s=e then
    begin
      cop[now,s]:=last[s];
      exit;
    end;
  mid:=(s+e) div 2;
  merge(s,mid,now+1);
  merge(mid+1,e,now+1);
  i:=s;
  j:=mid+1;
  k:=s-1;
  while (i<=mid)or(j<=e) do
    begin
      inc(k);
      if (i<=mid)and((j>e)or(cop[now+1,i]<cop[now+1,j])) then
        begin
          cop[now,k]:=cop[now+1,i];
          inc(i);
        end
                                                         else
        begin
          cop[now,k]:=cop[now+1,j];
          inc(j);
        end;
    end;
end;

function find (s,e,p,l,r,now:longint):longint;
var
  ans,mid:longint;
begin
  if cop[now,l]>=p then exit(0);
  if (s=l)and(e=r) then
    begin
      while s<>e do
        begin
          mid:=s+e-(s+e) div 2;
          if cop[now,mid]<p then s:=mid
                            else e:=mid-1;
        end;
      exit(s-l+1);
    end;
  ans:=0;
  mid:=(l+r) div 2;
  if e<=mid then exit(find(s,e,p,l,mid,now+1))
            else
  if s>=mid+1 then exit(find(s,e,p,mid+1,r,now+1))
              else
  exit(find(s,mid,p,l,mid,now+1)+find(mid+1,e,p,mid+1,r,now+1));
end;

begin
  assign(input,'diff.in');
  reset(input);
  assign(output,'diff.out');
  rewrite(output);
  read(n);
  for i:=1 to n do
    begin
      read(k);
      last[i]:=temp[k];
      temp[k]:=i;
    end;
  merge(1,n,0);
  read(m);
  for i:=1 to m do
    begin
      read(l,r);
      writeln(find(l,r,l,1,n,0));
    end;
  close(input);
  close(output);
end.