BZOJ3289 Mato文件管理

program bzoj3289;
 
type tquery=record
        l,r,b,p:longint;
     end;
     tnode=record
        v,l,r:longint;
     end;
 
const maxn=50017;
      maxalloc=8000017;
 
var q:array[0..maxn] of tquery;
    a,node,val:array[0..maxn] of longint;
    ans:array[0..maxn] of dword;
    mem:array[0..maxalloc] of tnode;
    n,m,bs,vc,memsize:longint;
    curans:dword;
 
procedure chair_init;                               begin
memsize:=0; mem[0].v:=0; mem[0].l:=0; mem[0].r:=0;  end;
 
function insert(i,j,d:longint):longint;
var k,l,r,mid:longint;
begin
inc(memsize); insert:=memsize; k:=memsize; l:=1; r:=vc;
while l<>r do begin
        mem[k].v:=mem[i].v+1; mid:=(l+r)>>1;
        if j<=mid then begin
                mem[k].r:=mem[i].r; i:=mem[i].l; inc(memsize); mem[k].l:=memsize; k:=memsize; r:=mid;
        end else begin
                mem[k].l:=mem[i].l; i:=mem[i].r; inc(memsize); mem[k].r:=memsize; k:=memsize; l:=mid+1;
        end;
end; mem[k].v:=mem[i].v+1; mem[k].l:=0; mem[k].r:=0;
end;
 
function intrank(l,r,i:longint):longint;
var mid,u,v:longint;
begin
if l>r then exit(0); intrank:=0; u:=node[l-1]; v:=node[r]; l:=1; r:=vc; while l<>r do begin
        mid:=(l+r)>>1; if i<=mid then begin
                u:=mem[u].l; v:=mem[v].l; r:=mid;
        end else begin inc(intrank,mem[mem[v].l].v-mem[mem[u].l].v);
                u:=mem[u].r; v:=mem[v].r; l:=mid+1;
        end;
end;
end;
 
function inttank(l,r,i:longint):longint;
var mid,u,v:longint;
begin
if l>r then exit(0); inttank:=0; u:=node[l-1]; v:=node[r]; l:=1; r:=vc; while l<>r do begin
        mid:=(l+r)>>1; if i>mid then begin
                u:=mem[u].r; v:=mem[v].r; l:=mid+1;
        end else begin inc(inttank,mem[mem[v].r].v-mem[mem[u].r].v);
                u:=mem[u].l; v:=mem[v].l; r:=mid;
        end;
end;
end;
 
procedure qsort2(l,r:longint);
var i,j,k1,k2:longint;
        o:tquery;
begin
i:=l; j:=r; with q[l+random(r-l+1)] do begin k1:=b; k2:=r; end;
repeat
        while (q[i].b<k1)or((q[i].b=k1)and(q[i].r<k2)) do inc(i);
        while (q[j].b>k1)or((q[j].b=k1)and(q[j].r>k2)) do dec(j);
        if i<=j then begin
                o:=q[i]; q[i]:=q[j]; q[j]:=o;
                inc(i); dec(j);
        end;
until i>j;
if i<r then qsort2(i,r);
if j>l then qsort2(l,j);
end;
 
procedure qsort1(l,r:longint);
var i,j,k,o:longint;
begin
i:=l; j:=r; k:=val[l+random(r-l+1)];
repeat
        while val[i]<k do inc(i);
        while val[j]>k do dec(j);
        if i<=j then begin
                o:=val[i]; val[i]:=val[j]; val[j]:=o;
                inc(i); dec(j);
        end;
until i>j;
if i<r then qsort1(i,r);
if j>l then qsort1(l,j);
end;
 
function binfind(i:longint):longint;
var l,r,mid:longint;
begin
l:=1; r:=vc; while l<>r do begin
        mid:=(l+r)>>1; if val[mid]<i then l:=mid+1 else r:=mid;
end; exit(l);
end;
 
procedure discret;
var i,j:longint;
begin
qsort1(1,vc); j:=1; for i:=2 to vc do if val[i]<>val[j] then begin
        inc(j); val[j]:=val[i];
end; vc:=j; for i:=1 to n do a[i]:=binfind(a[i]);
end;
 
procedure init;
var i,j,k:longint;
begin
readln(n); for i:=1 to n do begin
        read(a[i]); inc(vc); val[vc]:=a[i];
end; readln; discret; for i:=1 to n do node[i]:=insert(node[i-1],a[i],1);  bs:=trunc(sqrt(n));
readln(m); for i:=1 to m do begin readln(q[i].l,q[i].r); q[i].p:=i; q[i].b:=q[i].l div bs; end;
qsort2(1,m);
end;
 
procedure moteam;
var i,j,l,r:longint;
begin
l:=1; r:=1; curans:=0; for i:=1 to m do begin
        while l<q[i].l do begin dec(curans,intrank(l,r,a[l])); inc(l); end;
        while r>q[i].r do begin dec(curans,inttank(l,r,a[r])); dec(r); end;
        while l>q[i].l do begin dec(l); inc(curans,intrank(l,r,a[l])); end;
        while r<q[i].r do begin inc(r); inc(curans,inttank(l,r,a[r])); end;
        ans[q[i].p]:=curans;
end;
end;
 
procedure answer;
var i:longint;
begin
for i:=1 to m do writeln(ans[i]);
end;
 
begin
init;
moteam;
answer;
end.