Bedao Regular Contest 11 - SUPERQRY

Xem dạng PDF

Gửi bài giải


Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Ta xét hoán vị ~a~ của ~n~ phần tử ~1, 2, ..., n~.

Một dãy con của ~a~ là dãy thu được nếu xóa đi một số phần tử (có thể không xóa) từ ~a~ và giữ nguyên thứ tự các phần tử còn lại. Ví dụ: ~\{1, 3, 4\}~ là dãy con của ~\{1, 2, 3, 4, 5\}~, còn ~\{2, 1\}~ và ~\{1, 5, 2\}~ thì không.

Khi đó, ta định nghĩa ~LIS(a)~ là độ dài dãy con tăng dần dài nhất của dãy ~a~; tương tự với ~LDS(a)~ là độ dài dãy con giảm dần dài nhất của ~a~.

Gọi ~g(n) = min\{max\{LIS(a), LDS(a)\}\}~ với mọi hoán vị ~a~ độ dài ~n~.

Yêu cầu: Cho ~q~ truy vấn dạng ~l~ ~r~. Với mỗi truy vấn bạn hãy tính ~g(l)+g(l+1)+...+g(r)~.

Input

  • Dòng đầu chứa số nguyên dương ~q~ ~(q \le 10^5)~.

  • ~q~ dòng tiếp, mỗi dòng chứa hai số nguyên ~l,r~ ~(1\le l \le r \le 10^9)~.

Output

In ra ~q~ dòng, mỗi dòng là đáp án cho truy vấn tương ứng.

Subtask

  • Có ~25\%~ số test của bài với ~q,r \le 1000~.

  • Có ~25\%~ số test khác của bài với ~1\le l \le r \le 10^6~ trong mọi truy vấn.

  • Có ~25\%~ số test khác với ~q=1~.

  • Còn lại không có điều kiện gì thêm.

Sample Input

5
1 2
3 5
30 50
150 200
1 1000000000

Sample Output

3
7
141
698
21082351068005

Note

Các dãy có ~max\{LCS, LDS\}~ là nhỏ nhất trong một số trường hợp:

  • ~n = 1~: ~[1]~

  • ~n = 2~: ~[2, 1]~

  • ~n = 3~: ~[1, 3, 2]~

  • ~n = 4~: ~[2, 4, 1, 3]~

  • ~n = 5~: ~[5, 2, 4, 1, 3]~


Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.