trang chủ / đề bài / icpc25_mn_c

Truy vấn xâu con có trọng số

Đề bài

Mô tả

Cho N xâu đôi một khác nhau. Xâu thứ i là si và có trọng số ci. Cho thêm một xâu văn bản T.

Với mỗi truy vấn [L,R] (đánh số từ 1, tính cả hai đầu), xét xâu con

st=T[L]T[L+1]…T[R].

Giá trị của xâu con st được định nghĩa là

val(L,R)=∑i=1Nci·ki,

trong đó ki là số lần (có thể chồng lên nhau) si xuất hiện dưới dạng một xâu con liên tiếp của st. Với mỗi truy vấn, hãy in ra val(L,R).

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên N và Q (1≤N,Q≤105).
  • N dòng tiếp theo, mỗi dòng chứa một xâu si và một số nguyên ci (1≤ci≤109). Các xâu si đôi một khác nhau.
  • Dòng tiếp theo chứa xâu văn bản T.
  • Q dòng cuối cùng, mỗi dòng chứa hai số nguyên L và R mô tả một truy vấn.

Các đảm bảo thêm:

  • Tổng độ dài của tất cả các xâu trong dữ liệu vào (mọi si và T) không vượt quá 105.
  • Tổng số lần xuất hiện của tất cả các si trong T không vượt quá 105.

Dữ liệu ra

In ra Q dòng, dòng thứ j chứa một số nguyên là đáp án của truy vấn thứ j.

Ràng buộc

  • 1≤N,Q≤105, 1≤ci≤109.
  • 1≤L≤R≤|T|.
  • Các xâu si và T chỉ gồm chữ cái tiếng Anh in thường.
  • Tổng độ dài các xâu si và T không vượt quá 105; tổng số lần xuất hiện của các si trong T không vượt quá 105.

Ví dụ

Input Output Giải thích
6 3
she 3
he 2
her 5
sh 1
er 4
us 2
ushersheher
1 5
2 4
6 8
17
6
6
Truy vấn [1,5] là xâu usher: she, he, her, sh, er, us mỗi xâu xuất hiện 1 lần, tổng 3+2+5+1+4+2=17. Truy vấn [2,4] là she: 3+2+1=6. Truy vấn [6,8] là she: 6.
3 4
a 1
aa 10
aaa 100
aaaa
1 4
2 3
1 1
2 4
234
12
1
123
Ví dụ bổ sung (không có trong đề gốc). Trong aaaa: a xuất hiện 4 lần, aa 3 lần, aaa 2 lần (các lần xuất hiện được chồng lên nhau): 4+30+200=234.

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