[BIT cây] BIT vs skill ac bài HSPC14K(Spoj)

[BIT cây] BIT vs skill ac bài HSPC14K(Spoj)

link bài : HSPC14K

  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.