trang chủ / đề bài / icpc21_reg_k

Truy vấn K

Đề bài

Mô tả

Cho dãy số nguyên (a1,a2,…,an). Với mỗi cặp chỉ số (i,j) thỏa mãn 1≤i≤j≤n, ta định nghĩa f(i,j) như sau: xét mọi cặp phần tử au và av với i≤u≤v≤j, f(i,j) là tổng giá trị tuyệt đối của hiệu trên tất cả các cặp đó.

Ví dụ, với dãy (1,1,2,3):

  • f(1,1)=|1−1|=0.
  • f(1,2)=|1−1|+|1−1|+|1−1|=0.
  • f(2,4)=|1−1|+|1−2|+|1−3|+|2−2|+|2−3|+|3−3|=4.

Bạn được cho q truy vấn. Mỗi truy vấn gồm ba số nguyên x, y và k. Hãy đếm số cặp chỉ số (i,j) thỏa mãn:

  • x≤i≤j≤y,
  • f(i,j)≤k.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên n, độ dài của dãy.
  • Dòng thứ hai chứa n số nguyên a1,a2,…,an.
  • Dòng thứ ba chứa số nguyên q, số truy vấn.
  • q dòng tiếp theo, mỗi dòng chứa ba số nguyên x, y và k mô tả một truy vấn.

Dữ liệu ra

Với mỗi truy vấn, in ra đáp án trên một dòng.

Ràng buộc

  • 1≤n≤2000.
  • −109≤ai≤109.
  • 1≤q≤2·105.
  • 1≤x≤y≤n, 0≤k≤1018.

Ví dụ

Input Output Giải thích
4
1 1 2 3
3
1 1 0
1 2 0
2 4 2
1
3
5
Truy vấn thứ ba: các cặp (2,2), (3,3), (4,4) có f=0, các cặp (2,3) và (3,4) có f=1; cặp (2,4) có f=4>2.
3
3 1 4
3
1 3 2
1 3 5
2 3 10
4
5
3
Ví dụ bổ sung (không có trong đề gốc). f(1,2)=2, f(2,3)=3, f(1,3)=6, các đoạn một phần tử có f=0.

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0