trang chủ / đề bài / dhbb23_cbh_11_a

Số huyền bí

Đề bài

Mô tả

Một số M được gọi là số huyền bí cơ số X nếu (M⊕X)>(M&X), trong đó ⊕ là phép XOR bit (toán tử ^ trong C++) và & là phép AND bit (toán tử & trong C++).

Bạn được cho một mảng gồm N số nguyên không âm a1,a2,…,aN và Q truy vấn. Mỗi truy vấn được cho bởi bộ ba số L, R và X.

Yêu cầu: Với mỗi truy vấn, đếm xem trong các phần tử aL,aL+1,…,aR có bao nhiêu số là số huyền bí cơ số X.

Dữ liệu vào

  • Dòng đầu chứa số nguyên N.
  • Dòng tiếp theo chứa N số nguyên a1,a2,…,aN là các phần tử của mảng.
  • Dòng thứ ba chứa số nguyên Q là số truy vấn.
  • Q dòng cuối cùng, mỗi dòng chứa ba số nguyên L, R và X biểu thị một truy vấn.

Dữ liệu ra

Gồm Q dòng, dòng thứ i là kết quả của truy vấn thứ i.

Ràng buộc

  • 1≤N,Q≤2·105.
  • 0≤ai≤109.
  • 1≤L≤R≤N, 0≤X≤109.

Subtasks

  • 50% số test: N,Q≤2000.
  • 50% số test còn lại: N,Q≤2·105.

Ví dụ

Input Output Giải thích
5
1 2 3 4 5
2
1 5 4
2 5 2		 3
2		 Truy vấn 1, X=4: các số 1,2,3 thỏa mãn (ví dụ 1⊕4=5>1&4=0), còn 4 và 5 thì không (5⊕4=1<5&4=4). Truy vấn 2, X=2: chỉ 4 và 5 thỏa mãn.
4
0 1 0 5
4
1 4 0
1 3 1
2 4 6
4 4 7		 2
2
2
0		 Truy vấn 1: với M=X=0 thì 0⊕0=0 không lớn hơn 0&0=0, nên chỉ 1 và 5 thỏa mãn. Truy vấn 2: hai số 0 thỏa mãn (0⊕1=1>0), số 1 thì không. Truy vấn 3: 1 và 0 thỏa mãn, 5 thì không (5⊕6=3<5&6=4). Truy vấn 4: 5⊕7=2<5&7=5.

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