Bài này mình ra đề cho VNOI Marathon 2013 :D. Hôm nay lục lại máy thấy solution mình viết nên đăng lại lên forum :D

Kiến thức cần biết:

• Các hàm lượng giác cơ bản

• Interval tree hoặc Splay tree

• Maclaurin series / Taylor expansion

Các cách giải:

• 20% test đầu tiên (N, Q <= 5000).

  • Với N và Q nhỏ, cách làm chỉ đơn giản là brute force.

  • Mỗi truy vấn Modify có thể thực hiện trong O(1).

  • Mul, Sin, Cos và Reverse có thể thực hiện trong O(N).

• 20% test tiếp theo: (ko có Mul & Reverse)

  • Nhận xét:

    • sin(a + b) = sina*cosb + cosa*sinb

  • Như vậy, việc tính tổng sin(Ai + x) có thể dễ dàng được thực hiện nếu ta tính nhanh được tổng sin(Ai). --> có thể dùng interval tree cơ bản để xử lý.

• 20% test tiếp theo: (ko có Reverse)

  • Để giải quyết được truy vấn dạng Mul, các bạn cần phải biết về Taylor Expansion, hoặc 1 trường hợp đơn giản hơn của nó là Maclaurin Series. https://en.wikipedia.org/wiki/Taylor_series#List_of_Maclaurin_series_of_some_common_functions

  • Từ đó có được công thức xấp xỉ để tính sin (tương tự cho cos) :

    • sin(x) = x - x^3/3! + x^5/5! - x^7/7! + …

  • Với sai số yêu cầu của bài toán, bạn chỉ cần tính khoảng 20 - 30 giá trị đầu.

  • Vì không có thao tác dạng Reverse, bạn chỉ cần một interval tree, lưu lại tổng x^k với mọi k <= 20. Từ đó có thể nhanh chóng tính được tổng trên.

• 20% test tiếp theo: (ko có Mul)

  • Cách làm giống như 20% thứ 2, nhưng bạn phải cài đặt Splay Tree cho thao tác Reverse.

• 20% cuối cùng:

  • Kết hợp Splay Tree & Maclaurin Series.