trang chủ / đề bài / icpc19_reg_e

Truy vấn dễ

Đề bài

Mô tả

Cho mảng a gồm n số nguyên a1,a2,…,an.

Bạn cần trả lời q truy vấn. Mỗi truy vấn gồm 4 số nguyên ℓ,r,u,v (1≤ℓ≤r≤n, 1≤u≤v≤r−ℓ+1):

  • Xét mảng con của a từ chỉ số ℓ đến chỉ số r: aℓ,aℓ+1,…,ar.
  • Gọi s=[s1,s2,…,sr−ℓ+1] là mảng thu được khi sắp xếp mảng con trên theo thứ tự không giảm. Lưu ý rằng ta không thay đổi thứ tự các phần tử của mảng a, tức là mảng a giữ nguyên sau mỗi truy vấn.
  • Gọi t(i) là tập các giá trị xuất hiện ít nhất i lần trong su,su+1,…,sv.
  • Gọi f(t(i)) là phép OR theo bit của tất cả các phần tử trong t(i) (OR của tập rỗng bằng 0).
  • Kết quả của truy vấn là f(t(1))+f(t(2))+f(t(3)).

Ví dụ, với a=[123,3,2,2,7,2,1,5,5,7,456], xét truy vấn ℓ=2, r=10, u=2, v=8:

  • s=[1,2,2,2,3,5,5,7,7].
  • t(1)={2,3,5,7}.
  • t(2)={2,5}.
  • t(3)={2}.
  • f(t(1))=2∣3∣5∣7=7.
  • f(t(2))=2∣5=7.
  • f(t(3))=2.
  • Kết quả của truy vấn là 7+7+2=16.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên T (1≤T≤2·105) là số bộ dữ liệu. Tiếp theo là T bộ dữ liệu, mỗi bộ gồm:

  • Dòng đầu tiên chứa hai số nguyên n và q (1≤n,q≤2·105).
  • Dòng thứ hai chứa đúng n số nguyên là mảng a (1≤ai≤109).
  • q dòng tiếp theo, mỗi dòng chứa đúng 4 số nguyên ℓ,r,u,v (1≤ℓ≤r≤n, 1≤u≤v≤r−ℓ+1).

Tổng n của tất cả các bộ dữ liệu không vượt quá 2·105. Tổng q của tất cả các bộ dữ liệu không vượt quá 2·105.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra đúng q dòng, dòng thứ i chứa đúng một số nguyên là kết quả của truy vấn thứ i.

Ràng buộc

  • 1≤T≤2·105
  • 1≤n,q≤2·105, tổng n và tổng q không vượt quá 2·105
  • 1≤ai≤109
  • 1≤ℓ≤r≤n, 1≤u≤v≤r−ℓ+1

Ví dụ

Input Output Giải thích
1
11 3
123 3 2 2 7 2 1 5 5 7 456
2 10 2 8
1 1 1 1
1 4 1 3
16
123
5
Truy vấn thứ nhất được giải thích ở trên. Truy vấn thứ hai: s=[123], kết quả 123+0+0. Truy vấn thứ ba: s=[2,2,3,123], s1..s3=[2,2,3], kết quả 3+2+0=5.
1
6 3
4 1 4 2 4 1
1 6 1 6
1 6 2 5
2 5 2 3
16
11
6
Ví dụ bổ sung (không có trong đề gốc). Truy vấn thứ nhất: s=[1,1,2,4,4,4], kết quả 7+5+4. Truy vấn thứ hai: s2..s5=[1,2,4,4], kết quả 7+4+0. Truy vấn thứ ba: s=[1,2,4,4], s2..s3=[2,4], kết quả 6+0+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