DQUERY - D-query
Tác giả: ll931110
Ngôn ngữ: Pascal
{$MODE DELPHI}
program DQUERY;
const
input = '';
output = '';
maxn = 30010;
maxk = 200010;
maxv = 1000000;
type
pnode = ^tnode;
tnode = record
val: integer;
next: pnode;
end;
var
p,res: array[1..2 * maxk] of integer;
v: array[1..maxv] of integer;
a,t: array[1..maxn] of integer;
link: array[1..maxn] of pnode;
n,k: integer;
fi,fo: text;
// Analyze: Create new array {s} satisfying
// s[i] = max j | (j < i) and (s[j] = s[i]). s[i] = 0 if there doesn't exist j
// Using KQUERY: query(i,j) equals to the number of integers in the subsequence [i,j] which is less than i
procedure openfile;
begin
assign(fi, input);
reset(fi);
assign(fo, output);
rewrite(fo);
end;
procedure add(i,x: integer);
var
q: pnode;
begin
if i = 0 then exit;
new(q);
q^.val := x;
q^.next := link[i];
link[i] := q;
end;
procedure init;
var
i,num: integer;
begin
readln(fi, n);
fillchar(v, sizeof(v), 0);
for i := 1 to n do
begin
read(fi, num);
a[i] := v[num];
v[num] := i;
end;
readln(fi, k);
for i := 1 to k do
begin
read(fi, p[2 * i]);
add(p[2 * i] - 1,2 * i);
read(fi, p[2 * i + 1]);
add(p[2 * i + 1],2 * i + 1);
v[i] := p[2 * i];
end;
end;
// BIT operations
procedure update(x: integer);
begin
while x <= maxn do
begin
inc(t[x]);
x := x + (x and -x);
end;
end;
function calc(x: integer): integer;
var
r: integer;
begin
r := 0;
while x > 0 do
begin
r := r + t[x];
x := x - (x and -x);
end;
calc := r;
end;
// End of BIT operations
procedure solve;
var
i,tmp: integer;
s: pnode;
begin
fillchar(t, sizeof(t), 0);
fillchar(res, sizeof(res), 0);
for i := 1 to n do
begin
update(a[i] + 1);
s := link[i];
while s <> nil do
begin
tmp := s^.val;
res[tmp] := calc(v[tmp div 2]);
s := s^.next;
end;
end;
for i := 1 to k do writeln(fo, res[2 * i + 1] - res[2 * i]);
end;
procedure closefile;
begin
close(fo);
close(fi);
end;
begin
openfile;
init;
solve;
closefile;
end.