bzoj2743

其实和bzoj1878类似

只不过要求的是区间内数量多于1个的数字种数

其实还是按照bzoj1878做

只不过我们是把每一种数字下一个出现的位置+1，并把这个位置置为0

var x,y,ans,p,last,a,c,next:array[0..1000010] of longint;
    max,i,n,m,j:longint;

function lowbit(x:longint):longint;
  begin
    exit(x and(-x));
  end;

function sum(x:longint):longint;
  begin
    sum:=0;
    while x<>0 do
    begin
      sum:=sum+c[x];
      x:=x-lowbit(x);
    end;
  end;

procedure add(x,t:longint);
  begin
    while x<=n do
    begin
      inc(c[x],t);
      x:=x+lowbit(x);
    end;
  end;

procedure swap(var a,b:longint);
  var c:longint;
  begin
    c:=a;
    a:=b;
    b:=c;
  end;

procedure sort(l,r: longint);
  var i,j,z: longint;
  begin
    i:=l;
    j:=r;
    z:=x[(l+r) div 2];
    repeat
      while x[i]do inc(i);
      while zdo dec(j);
      if not(i>j) then
      begin
        swap(x[i],x[j]);
        swap(y[i],y[j]);
        swap(p[i],p[j]);
        inc(i);
        dec(j);
      end;
    until i>j;
    if lthen sort(l,j);
    if ithen sort(i,r);
  end;

begin
  readln(n,max,m);
  for i:=1 to n do
    read(a[i]);

  for i:=1 to m do
  begin
    readln(x[i],y[i]);
    p[i]:=i;
  end;
  sort(1,m);
  fillchar(last,sizeof(last),0);
  for i:=n downto 1 do
  begin
    next[i]:=last[a[i]];
    last[a[i]]:=i;
  end;
  for i:=1 to max do
    if next[last[i]]<>0 then add(next[last[i]],1);

  j:=1;
  for i:=1 to n do
  begin
    while x[j]=i do
    begin
      ans[p[j]]:=sum(y[j])-sum(x[j]-1);
      inc(j);
    end;
    if next[i]<>0 then add(next[i],-1);
    if next[next[i]]<>0 then add(next[next[i]],1);
  end;
  for i:=1 to m do
    writeln(ans[i]);
end.