Thứ Sáu, 14 tháng 9, 2018
[BIT cây] BIT vs skill ac bài HSPC14K(Spoj)
link bài : HSPC14K
Input
Output
Example
Cho một bảng hình chữ nhật kích thước N×M, ban đầu các phần tử trên bảng bằng 0. Có Q thao tác trên bảng như sau:
"1 a b x y w": tăng giá trị mỗi phần tử trong hình chữ nhật có góc trái dưới (a,b), góc phải trên (x,y) lên w đơn vị.
"2 a b x y": in ra tổng các phần tử trong hình chữ nhật có góc trái dưới (a,b), góc phải trên (x,y).
Input
Dòng đầu gồm 3 số N, M và Q. 1 ≤ N, M ≤ 1000. 1 ≤ Q ≤ 100000. Sau đó là Q dòng, mỗi dòng là 1 thao tác theo định dạng trên.
Output
Lần lượt với mỗi thao tác loại 2, in ra trên một dòng giá trị tính toán được.
Example
Input:
2 3 8
1 1 1 1 1 5
1 1 1 1 2 5
2 1 2 1 3
1 1 1 2 1 4
2 2 1 2 2
2 1 2 1 3
1 2 1 2 2 5
2 1 1 1 1
Output:
5
4
5
14
Ngày xưa hồi còn thơ bé ( hồi mới học BIT) mình từng nghĩ “bài nào giải được bằng BIT thì đều giải được bằng IT nhưng chưa chắc giải được bằng IT đã giải được bằng BIT”, đây là 1 bài toán điển hình để chứng minh câu nói đó false :)) .Là 1 bài toán cập nhật trên 1 đoạn, chúng ta không thể dùng BIT để giải.Nhưng “không thể” chỉ là với BIT “thông thường” còn với BIT “khác thường” thì ta hoàn toàn có thể AC được bài này bằng BIT. Trước tiên, ta xét bài toán 1 chiều :
Cho dãy A n phần tử, với Q truy vấn:
1. Tăng mỗi giá trị trong đoạn [u…v] trong mảng A lên X đơn vị.
2. Tính tổng các phần tử trong đoạn [a..b].
“ Dễ làm trước” , với truy vấn 2 ta có kết quả= SUM(1..b)-SUM(1..a-1).Trở lại công việc khó khăn nhất của bài toán, truy vấn 1, tăng mỗi giá trị trong đoạn [u..v] lên X. Xét I (1<=i<=n) , với mỗi truy vấn có 3 trường hợp( giả sử có 2 số A,B)
-1<=i
-u<=i<=v: tăng sum[i] X*(i-(u-1))=X*i+X*(1-u) ( A=X , B=X*(1-u) )
-v
Như vậy ta có thể thấy được sum[i] được tính bằng công thức : sum[i]:=A*i+B, đến đây ta sẽ nghĩ ngay đến việc dùng 2 cây BIT, cây T1 lưu A, cây T2 lưu B.
-Với cây T1, update(u,X); update(v+1,-X).
-Với cây T2, update(u,X*(1-u) ); update(v+1,X*v).
Procedure update(I,u,x:longint);
Begin
If (u>n) then exit;
Inc(T[I,u],x);
Update(I,u+u and(-u),x);
End;
Function tong(I,u:longint):longint;
Begin
If(u<=0) then exit(0);
Tong:=T[I,x]+tong(I,u-u and(-u) );
End;
Function Sum(u:longint):longint;
Begin
sum:=tong(1,u)*u+tong(2,u);
End;
Function get(u,v:longint):longint;
Begin
Get:=sum(v)-sum(u-1);
End;
Với truy vấn 1: update(1,u,x) ; update(1,v+1,-x); update(2,u,x*(1-u)); update(2,v+1,x*v).
Với truy vấn 2: kết quả = get(u,v).
Vậy là xong 1D, trở lại với bài toán 2 chiều. Cũng tương tự, bây giờ ta dùng 4 mảng BIT lưu lần lượt A,B,C,D; với sum[I,j]:=A*i*j+B*i+C*j+D.
[BIT cây] Rời Rạc Hóa với bài NTSEQ(Spoj)
uses math;
const fi = '';
fo = '';
base = 1000000007;
maxn = 100000;
type matrix = record
num,len:int64;
end;
var f,g : text;
kq : qword;
A : array[1..100001] of int64;
B,cs : array[1..100001] of int64;
T : array[1..100001] of matrix;
i,j,k,n,key : longint;
procedure update(x:longint;tmp:matrix);
Begin
If (x>maxn) then exit;
If (T[x].num
|
if (T[x].num=tmp.num) then
T[x].len:=(T[x].len + tmp.len mod base ) mod base;
x:=x+x and (-x);
update(x,tmp);
end;
function find(x:longint):matrix;
var res:matrix;
Begin
res.num:=0;
res.len:=0;
While (x>0) do
Begin
If (res.num
res:=T[x]
else
If (res.num=T[x].num) then
res.len:=(res.len +T[x].len) mod base;
x:=x-x and (-x);
end;
inc(res.num);
If (res.len=0) then res.len:=1;
exit(res);
end;
procedure QS(l,h:longint);
var x,tg,i,j : longint;
begin
i:=l;
j:=h;
x:=a[(l+h) div 2];
repeat
while a[i]
while a[j]>x do dec(j);
if i<=j then
begin
tg:=a[i];
a[i]:=a[j];
a[j]:=tg;
tg:=cs[i];
cs[i]:=cs[j];
cs[j]:=tg;
inc(i);
dec(j);
end;
until i>j;
if i
if j>L then QS(l,j);
end;
procedure doc;
Begin
assign(f,fi); assign(g,fo);
reset(f); rewrite(g);
readln(f,n);
for i:=1 to n do
read(f,A[i]);
for i:=1 to n do cs[i]:=i;
QS(1,n);
end;
procedure cbi;
Begin
fillchar(t,sizeof(t),0);
key:=1; B[cs[1]]:=1;
for i:=2 to n do
Begin
If (A[i]<>A[i-1]) then inc(key);
B[cs[i]]:=key;
end;
end;
procedure enter;
var tmp:matrix;
Begin
for i:=1 to n do
Begin
tmp:=find(B[i]-1);
update(B[i],tmp);
end;
tmp:=find(n);
writeln(g,tmp.len);
close(g);
end;
Begin
doc;
cbi;
enter;
end.
Đăng ký:
Bài đăng (Atom)