[BZOJ 2743][HEOI 2012]採花

トランスファゲート
http://www.lydsy.com/JudgeOnline/problem.php?id=2743
テーマの大意
1つのシーケンスが与えられ,複数回の問合せ区間内に2回以上出現する数の数
問題解
HHのネックレスと同じで、オフラインで木の配列を処理してメンテナンスして、唯一の違いはHHがメンテナンス区間の1つ目で、これはメンテナンス区間の2つ目です.私たちはnext[I]でiの後ろの1つ目とiの色が同じ位置を表しています.私たちが左端のiを後ろに押すとき、私たちはnext[i]-1を修正して、next[next[i]+1

const
 maxn=1000000;
var
 ans,x,y,next,co,fi:array[0..maxn+100]of longint;
 z:array[0..maxn+100,1..3]of longint;
 i,j,k:longint;
 n,m,ma,a,len:longint;
procedure sort(l,r:longint);
var i,j,a,b,c,k:longint;
begin
 i:=l; j:=r; a:=z[(l+r) div 2,1]; c:=z[(l+r)div 2,2];
 repeat
  while (z[i,1]<a)or((z[i,1]=a)and(z[i,2]<c)) do inc(i);
  while (a<z[j,1])or((z[j,1]=a)and(z[j,2]>c)) do dec(j);
  if not(i>j) then
   begin
    for k:=1 to 3 do
     begin b:=z[i,k]; z[i,k]:=z[j,k]; z[j,k]:=b; end;
    inc(i); dec(j);
   end;
 until i>j;
 if l<j then sort(l,j);
 if i<r then sort(i,r);
end;

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

procedure update(a,b:longint);
begin
 while a<=n do
  begin
   inc(y[a],b);
   inc(a,lowbit(a));
  end;
end;

function query(a:longint):longint;
var tt:longint;
begin
 tt:=0;
 while a>0 do
  begin
   inc(tt,y[a]);
   dec(a,lowbit(a));
  end;
 exit(tt);
end;

begin
 readln(n,ma,m);
 for i:=1 to n do
  begin read(a); next[co[a]]:=i; if co[a]=0 then begin inc(len); fi[len]:=i; end; co[a]:=i; end;
 for i:=1 to len do
  begin
   if next[fi[i]]=0 then continue;
   x[next[fi[i]]]:=1; update(next[fi[i]],1);
  end;
 for i:=1 to m do
  begin readln(z[i,1],z[i,2]); z[i,3]:=i; end;
 next[0]:=0;
 sort(1,m);
 z[0,1]:=1;
 for i:=1 to m do
  begin
   if z[i,1]<>z[i-1,1] then
    for j:=z[i-1,1] to z[i,1]-1 do
     begin
      if next[j]<>0 then update(next[j],-1);
      if next[next[j]]<>0 then update(next[next[j]],1);
     end;
   ans[z[i,3]]:=query(z[i,2]);
  end;
 for i:=1 to m do
  writeln(ans[i]);
end.