Editorial for Bedao Regular Contest 09 - SAUSAGE


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Ta cần chuẩn bị các mảng như sau:

  • ~pre[i][j]~ là số ~a_i = j~ nằm trong đoạn từ ~[1..i]~
  • ~suf[i][j]~ là số ~a_i = j~ nằm trong đoạn từ ~[i..n]~
  • ~cnt[x][y]~ là số cặp ~(x, y)~ nằm trong prefix ~[1..i-1]~ đang xét

Xét bài toán tổng quát thì ta cần đếm số bộ ~4~ có dạng ~x..y..y..x~. Nếu ta cố định ~y~ thứ ~2~, thì tại vị trí ~i~ duyệt qua toàn bộ số ~x~ ~(1 \le x \le 100)~, đáp án sẽ được cộng thêm một khoảng là ~suf[i + 1][x] \times cnt[x][a_i]~. Sau đó ta cập nhật ~pre[i - 1][x]~ tương ứng cho ~cnt[x][a_i]~

Độ phức tạp: ~O(N \times 100)~


Comments

Please read the guidelines before commenting.


There are no comments at the moment.