#P12998. [GCJ 2022 #3] Duck, Duck, Geese

    ID: 12797 Type: RemoteJudge 20000ms 1024MiB Tried: 0 Accepted: 0 Difficulty: 5 Uploaded By: Tags>线段树2022Google Code Jam

[GCJ 2022 #3] Duck, Duck, Geese

题目描述

In the game "Duck, Duck, Goose", all players but one sit on the floor and form a circle. The remaining player walks around the circle calling each player "duck" until they select one sitting player and, while touching their head, call them "goose" instead. At that point, the goose chases the selecting player and our interest in the game fades.

In the new game "Duck, Duck, Geese", the walking player instead chooses a contiguous subset of at least two (but not all) sitting players to be "geese"! Furthermore, each sitting player is wearing a hat. Each hat is one of C\mathbf{C} possible colors, numbered 1 through C\mathbf{C}.

For each color ii, the quantity of selected geese wearing a hat of color ii must be either 0 or between Ai\mathbf{A}_i and Bi\mathbf{B}_i, inclusive.

Can you help count the number of choices that fulfill these requirements? Two choices are considered different if there is some player that is included in one choice but not the other.

输入格式

The first line of the input gives the number of test cases, T\mathbf{T}. T\mathbf{T} test cases follow. Each test case starts with a line containing two integers N\mathbf{N} and C\mathbf{C}: the number of sitting players and hat colors, respectively. Then, C\mathbf{C} lines follow. The ii-th of these lines contains two integers Ai\mathbf{A}_i and Bi\mathbf{B}_i, as explained above. The last line of a test case contains N\mathbf{N} integers $\mathbf{P}_1, \mathbf{P}_2, \ldots, \mathbf{P}_\mathbf{N}$ representing that the jj-th sitting player in clockwise order (starting from an arbitrary one) is wearing a hat of color Pj\mathbf{P}_j.

输出格式

For each test case, output one line containing Case #x: y, where xx is the test case number (starting from 1) and yy is the number of sets of at least 2 and at most N1\mathbf{N} - 1 contiguously sitting players that fulfill all the color requirements.

3
3 2
1 1
1 1
1 1 2
5 2
1 1
1 2
1 2 1 2 2
3 3
1 2
1 2
2 2
1 1 3
Case #1: 2
Case #2: 9
Case #3: 1

提示

Sample Explanation

In Sample Case #1, the total number of players chosen as geese must be 2. There are only three possible ways to select 2 players. The following color configurations are possible: [1,1][1, 1], [1,2][1, 2], and [2,1][2, 1]. The first one has two players wearing hats of color 1, so it is not valid, but the other two are valid. Therefore the answer is 2.

Sample Case #2 is the one illustrated in the statement, with color 1 being yellow and color 2 being blue. The total number of players chosen as geese in this case must be between 2 and 3, because selecting 4 geese would require at least one color to be out of bounds. For cases with 2 geese, the only requirement is that we do not select 2 geese both wearing hats of color 1; all 5 such selections are valid. If choosing 3 geese, the options are [1,2,1][1, 2, 1], [2,1,2][2, 1, 2], [1,2,2][1, 2, 2], [2,2,1][2, 2, 1], or [2,1,2][2, 1, 2]. All but the first one are valid, adding another 4 valid options, for a total of 9.

In Sample Case #3, notice that there can be hat colors that nobody is wearing. In this case, since there is only 1 player wearing hat color 3 and 1 is not in range, the only valid way is to pick 0 players wearing that hat color.

Limits

  • 1T1001 \leq \mathbf{T} \leq 100.
  • 2CN2 \leq \mathbf{C} \leq \mathbf{N}.
  • $0 \leq \mathbf{A}_i \leq \mathbf{B}_i \leq \mathbf{N}$, for all ii.
  • 1PjC1 \leq \mathbf{P}_j \leq \mathbf{C}, for all jj.

Test Set 1 (12 Pts, Visible Verdict)

  • 3N10003 \leq \mathbf{N} \leq 1000.

Test Set 2 (13 Pts, Hidden Verdict)

  • 3N1053 \leq \mathbf{N} \leq 10^5.