trang chủ / đề bài / icpc23_nat_d

Bộ bài rực rỡ

Đề bài

Mô tả

Slay the Spire là một trò chơi điện tử nổi tiếng kết hợp giữa thể loại roguelike và xây dựng bộ bài. Đây là một trò chơi chiến thuật trong đó người chơi vượt qua một chuỗi màn chơi, chiến đấu với kẻ địch và thu thập các lá bài để xây dựng bộ bài của mình. Mục tiêu là leo lên đỉnh tháp bằng cách đánh bại những con trùm mạnh trên đường đi. Mỗi lượt chơi đều độc nhất vì người chơi gặp các lá bài, bảo vật và sự kiện khác nhau định hình chiến thuật của họ. Slay the Spire được khen ngợi nhờ lối chơi thử thách, chiến thuật sâu sắc và khả năng chơi lại cao.

Trong lượt chơi hiện tại, Lokk có trên tay n lá bài tấn công. Lá bài thứ i có sát thương ai. Lokk đang chơi phiên bản mới nhất của Slay the Spire và vừa nhận được một bảo vật mới tên là Radiance. Radiance có hiệu ứng sau: nếu trong lượt này các lá bài được đánh ra là Rực rỡ, thì sau lượt này trạng thái Dễ tổn thương sẽ được áp lên tất cả kẻ địch.

Các lá bài được đánh ra gọi là Rực rỡ nếu chúng nằm liền nhau trên tay và không có hai lá nào có cùng sát thương. Nói cách khác, tồn tại hai chỉ số l và r (1≤l≤r≤n) sao cho:

  • mọi lá bài từ vị trí l đến r đều được đánh ra trong lượt này,
  • không có lá bài nào khác được đánh ra, và
  • ai≠aj với mọi l≤i<j≤r.

Có Radiance trong tay, Lokk muốn tận dụng bảo vật này hiệu quả nhất có thể. Cho dãy sát thương của các lá bài trên tay Lokk theo thứ tự xuất hiện, hãy giúp Lokk đếm số cách đánh bài trong lượt này để Radiance phát huy hiệu ứng. Hai cách đánh được coi là khác nhau nếu tồn tại chỉ số i sao cho lá bài i được đánh ra ở cách này nhưng không được đánh ra ở cách kia.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên dương t, số bộ dữ liệu. Tiếp theo là mô tả các bộ dữ liệu.

Dòng đầu tiên của mỗi bộ dữ liệu chứa số nguyên n (1≤n≤200000), số lá bài trên tay Lokk.

Dòng thứ hai của mỗi bộ dữ liệu chứa n số nguyên a1,a2,…,an (1≤ai≤n), sát thương của các lá bài trên tay Lokk.

Dữ liệu bảo đảm tổng n của tất cả các bộ dữ liệu không vượt quá 500000.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số nguyên là số cách đánh bài để Radiance phát huy hiệu ứng sau lượt này.

Ràng buộc

  • 1≤n≤200000
  • 1≤ai≤n
  • Tổng n của tất cả các bộ dữ liệu không vượt quá 500000.

Ví dụ

Input Output Giải thích
3
6
4 1 1 6 2 2
3
2 2 2
9
6 9 6 9 6 9 6 9 6
10
3
17
Bộ thứ nhất: có 10 cách, gồm 6 cách đánh một lá và các đoạn [4,1], [1,6], [6,2], [1,6,2]. Đoạn [1,1,6] không Rực rỡ vì có hai lá sát thương 1. Bộ thứ hai: không thể đánh nhiều hơn một lá. Bộ thứ ba: ngoài 9 cách đánh một lá, cả 8 cặp hai lá liền nhau cũng Rực rỡ.
3
1
1
4
1 2 3 4
5
3 1 2 3 1
1
10
12
Ví dụ bổ sung. Bộ thứ hai: mọi đoạn đều Rực rỡ, có 4·5/2=10 đoạn.

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