Nhận xét 1: Dãy f là cách chèn các chỉ số

Thay vì nhìn trực tiếp vào hoán vị p, ta xét danh sách các chỉ số được sắp theo thứ tự tăng dần của giá trị p_i.

Gọi danh sách đó là ord. Nếu chỉ số i đứng ở vị trí thứ x trong ord, thì:

p_i = x

Với một chỉ số i, giá trị f_i là số lượng chỉ số j < i sao cho p_j < p_i. Nói theo danh sách ord, đó chính là số lượng chỉ số nhỏ hơn i đứng trước i trong ord.

Vì vậy, nếu xét các chỉ số theo thứ tự 1, 2, ..., n, thì khi thêm chỉ số i vào danh sách hiện tại, nó phải được chèn vào sau đúng f_i chỉ số đã có.

Nói cách khác:

Ban đầu ord rỗng.
Với i = 1..n:
    chèn i vào vị trí f_i + 1 trong ord.

Sau khi chèn xong, nếu i đứng ở vị trí x trong ord, thì p_i = x.

Điều này cũng giải thích vì sao với mọi dãy f thỏa mãn 0 <= f_i < i, luôn tồn tại duy nhất một hoán vị p.

Subtask 1: n, q <= 5000

Ta có thể duy trì trực tiếp:

p[i]      = giá trị hiện tại của phần tử ở vị trí i
ord[pos]  = chỉ số đang có giá trị p = pos

Khi có truy vấn ? l r, chỉ cần duyệt thẳng:

answer = p[l] + p[l + 1] + ... + p[r]

Khi có cập nhật + i hoặc - i, ta xử lý bằng nhận xét ở phần tiếp theo, nhưng tìm kiếm tuyến tính trong ord.

Mỗi thao tác tốn O(n), đủ cho n, q <= 5000.

Nhận xét 2: Một cập nhật chỉ hoán đổi hai chỉ số trong ord

Giả sử ta đang có danh sách ord, tức là các chỉ số được sắp theo thứ tự tăng dần của giá trị p_i.

Cập nhật + i

Thao tác này tăng f_i lên 1.

Điều đó có nghĩa là trong danh sách các chỉ số <= i, chỉ số i cần đi sang phải đúng một bước.

Trong danh sách ord, ta cần tìm chỉ số đầu tiên nằm bên phải i mà có giá trị không vượt quá i.

Gọi chỉ số đó là x.

Khi đó thao tác + i tương ứng với việc hoán đổi vị trí của i và x trong ord.

Cập nhật - i

Tương tự, thao tác này giảm f_i đi 1.

Ta cần tìm chỉ số đầu tiên nằm bên trái i mà có giá trị không vượt quá i.

Gọi chỉ số đó là x.

Khi đó thao tác - i tương ứng với việc hoán đổi vị trí của i và x trong ord.

Vì sao chỉ cần hoán đổi như vậy?

Xét thao tác + i.

Gọi x là chỉ số đầu tiên bên phải i trong ord sao cho x <= i.

Khi đó, tất cả chỉ số nằm giữa i và x trong ord đều lớn hơn i.

Sau khi hoán đổi i và x:

• Với f_i, chỉ số i đã đi qua đúng một chỉ số <= i, nên f_i tăng đúng 1.
• Với các chỉ số nhỏ hơn i, không có quan hệ thứ tự nào giữa các chỉ số liên quan bị thay đổi.
• Với một chỉ số k > i, nếu k nằm giữa i và x trong ord, thì trước khi hoán đổi, trong hai chỉ số i và x, chỉ có i đứng trước k; sau khi hoán đổi, chỉ có x đứng trước k. Vì cả i và x đều nhỏ hơn k, tổng số chỉ số nhỏ hơn k đứng trước k không đổi.
• Nếu k không nằm giữa i và x, thì cả i và x vẫn cùng nằm về một phía so với k, nên f_k cũng không đổi.

Do đó, chỉ có f_i thay đổi đúng như yêu cầu.

Trường hợp - i chứng minh tương tự.

Cấu trúc dữ liệu cho lời giải đầy đủ

Ta duy trì:

p[i]      = vị trí của chỉ số i trong ord
ord[pos]  = chỉ số đang đứng ở vị trí pos trong ord

Như vậy p[i] cũng chính là giá trị của phần tử thứ i trong hoán vị cần xét.

Ta cần hỗ trợ ba việc:

1. Tìm chỉ số đầu tiên bên phải p[i] sao cho ord[pos] <= i.
2. Tìm chỉ số đầu tiên bên trái p[i] sao cho ord[pos] <= i.
3. Tính tổng p[l] + ... + p[r].

Segment tree trên ord

Xây một segment tree theo vị trí trong ord.

Mỗi node lưu:

min(ord[pos]) trên đoạn đó

Khi cần tìm bên phải p[i], ta tìm vị trí nhỏ nhất pos trong đoạn [p[i] + 1, n] sao cho:

ord[pos] <= i

Vì segment tree lưu min, nếu một đoạn có min > i, đoạn đó chắc chắn không chứa vị trí cần tìm. Ngược lại, ta đi xuống cây để tìm vị trí đầu tiên thỏa mãn.

Tương tự, khi cần tìm bên trái, ta tìm vị trí lớn nhất pos trong đoạn [1, p[i] - 1] sao cho:

ord[pos] <= i

Cả hai thao tác đều làm được trong O(log n) bằng cách đi trên segment tree.

Fenwick tree trên chỉ số ban đầu

Để trả lời truy vấn ? l r, ta cần tổng:

p[l] + p[l + 1] + ... + p[r]

Ta dùng Fenwick tree theo chỉ số i, trong đó tại vị trí i lưu giá trị p[i].

Khi hoán đổi hai chỉ số a và b trong ord, chỉ có p[a] và p[b] thay đổi, nên cập nhật Fenwick bằng hai point update.

Khởi tạo ban đầu

Ta cần dựng ord từ dãy f.

Cách đơn giản là mô phỏng chèn từ 1 đến n, nhưng sẽ tốn O(n^2) nếu dùng mảng thường.

Để dựng trong O(n log n), ta làm ngược từ n về 1.

Ban đầu có n vị trí trống trong ord.

Với i từ n giảm về 1, vị trí của i trong số các chỉ số 1..i phải là f_i + 1. Do đó, ta đặt i vào vị trí trống thứ f_i + 1 từ trái sang phải.

Ta dùng Fenwick tree lưu các vị trí còn trống:

• Ban đầu mỗi vị trí có giá trị 1.
• Tìm vị trí trống thứ f_i + 1 bằng thao tác k-th trên Fenwick.
• Đặt ord[pos] = i.
• Đánh dấu vị trí đó không còn trống.

Sau khi dựng được ord, ta suy ra:

p[ord[pos]] = pos

Xử lý thao tác

Truy vấn ? l r

Trả lời bằng Fenwick tree:

sum(l, r)

Cập nhật + i

cur = p[i]
nxt = vị trí đầu tiên trong [cur + 1, n] có ord[nxt] <= i

Hoán đổi ord[cur] và ord[nxt].
Cập nhật p của hai chỉ số bị hoán đổi.
Cập nhật Fenwick tổng.
Cập nhật segment tree tại hai vị trí cur và nxt.

Cập nhật - i

cur = p[i]
prv = vị trí cuối cùng trong [1, cur - 1] có ord[prv] <= i

Hoán đổi ord[cur] và ord[prv].
Cập nhật p của hai chỉ số bị hoán đổi.
Cập nhật Fenwick tổng.
Cập nhật segment tree tại hai vị trí cur và prv.

Do đề đảm bảo mọi cập nhật hợp lệ, vị trí cần tìm luôn tồn tại.

Độ phức tạp

Khởi tạo:

O(n log n)

Mỗi thao tác:

O(log n)

Tổng độ phức tạp:

O((n + q) log n)

Bộ nhớ:

O(n)