trang chủ / đề bài / sufdistinct

Số giá trị phân biệt của hậu tố

Đề bài

Mô tả

Cho dãy số nguyên a1,a2,…,an và m truy vấn. Truy vấn thứ i cho một số li (1≤li≤n), hãy cho biết trong đoạn hậu tố ali,ali+1,…,an có bao nhiêu giá trị phân biệt.

Dữ liệu vào

  • Dòng đầu tiên gồm hai số nguyên n và m.
  • Dòng thứ hai gồm n số nguyên a1,a2,…,an.
  • m dòng tiếp theo, dòng thứ i chứa số nguyên li.

Dữ liệu ra

In ra m dòng, dòng thứ i là số giá trị phân biệt trong ali,ali+1,…,an.

Ràng buộc

  • 1≤n,m≤105
  • 1≤ai≤105
  • 1≤li≤n

Ví dụ

Input Output Giải thích
10 10
1 2 3 4 1 2 3 4 100000 99999
1
2
3
4
5
6
7
8
9
10		 6
6
6
6
6
5
4
3
2
1		 Hậu tố bắt đầu từ vị trí 5 là 1,2,3,4,100000,99999 gồm 6 giá trị phân biệt; bốn hậu tố dài hơn không thêm giá trị mới nào.
8 3
8 6 4 3 4 2 4 8
6
4
2		 3
4
5		 Hậu tố từ vị trí 6 là 2,4,8; từ vị trí 4 là 3,4,2,4,8 có 4 giá trị; từ vị trí 2 có thêm 6 nên là 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