作者： chenchen

Farmer John has a binary string of length N (1≤N≤10⁹), initially all zeros.

He will first perform M(1≤M≤2⋅10⁵) updates on the string, in order. Each update flips every character from l to r. Specifically, flipping a character changes it from 0 to 1, or vice versa.

Then, he asks you Q (1≤Q≤2⋅10⁵) queries. For each query, he asks you to output the lexicographically greatest subsequence of length k comprised of characters from the substring from l to r. If your answer is a binary string s₁s₂…s_k, then output (that is, its value when interpreted as a binary number) modulo 10⁹+7.

A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.

Recall that string A is lexicographically greater than string B of equal length if and only if at the first position i, if it exists, where A_i≠B_i, we have A_i>B_i.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains N, M, and Q.

The next M lines contain two integers, l and r (1≤l≤r≤N) — the endpoints of each update.

The next Q lines contain three integers, l, r, and k (1≤l≤r≤N,1≤k≤r−l+1) — the endpoints of each query and the length of the subsequence.

OUTPUT FORMAT (print output to the terminal / stdout):

Output Q lines. The ith line should contain the answer for the ith query.

SAMPLE INPUT:

5 3 9
1 5
2 4
3 3
1 5 5
1 5 4
1 5 3
1 5 2
1 5 1
2 5 4
2 5 3
2 5 2
2 5 1

SAMPLE OUTPUT:

21
13
7
3
1
5
5
3
1

After performing the M operations, the string is 10101.

For the first query, there is only one subsequence of length 5, 10101, which is interpreted as 1⋅2⁴+0⋅2³+1⋅2²+0⋅2¹+1⋅2⁰=21.

For the second query, there are 5 unique subsequences of length 4: 0101, 1101, 1001, 1011, 1010. The lexicographically largest subsequence is 1101, which is interpreted as 1⋅2³+1⋅2²+0⋅2¹+1⋅2⁰=13.

For the third query, the lexicographically largest sequence is 111, which is interpreted as 7.

SAMPLE INPUT:

9 1 1
7 9
1 8 8

SAMPLE OUTPUT:

3

SAMPLE INPUT:

30 1 1
1 30
1 30 30

SAMPLE OUTPUT:

73741816

Make sure to output the answer modulo 10⁹ +7.

SCORING:

Input 4: N≤10,Q≤1000
Input 5: M≤10
Inputs 6-7: N,Q≤1000
Inputs 8-12: N≤2⋅10⁵ 
Inputs 13-20: No additional constraints.

Problem credits: Chongtian Ma

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

Bessie has a special function f(x) that takes as input an integer in [1,N]
and returns an integer in [1,N] (1≤N≤2⋅10⁵). Her function f(x) is defined by N
integers a₁…a_N where f(x)=a_x (1≤a_i≤N).

Bessie wants this function to be idempotent. In other words, it should satisfy f(f(x))=f(x)for all integers x∈[1,N].

For a cost of c_i, Bessie can change the value of a_i to any integer in [1,N] (1≤c_i≤10⁹). Determine the minimum total cost Bessie needs to make f(x)
idempotent.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains N.

The second line contains N

space-separated integers a₁,a₂,…,a_N.

The third line contains N space-separated integers c₁,c₂,…,c_N.

OUTPUT FORMAT (print output to the terminal / stdout):

Output the minimum total cost Bessie needs to make f(x) idempotent.

SAMPLE INPUT:

5
2 4 4 5 3
1 1 1 1 1

SAMPLE OUTPUT:

3

We can change a₁=4, a₄=4, a₅=4. Since all c_i equal one, the total cost is equal to 3
, the number of changes. It can be shown that there is no solution with only 2
or fewer changes.

SAMPLE INPUT:

8
1 2 5 5 3 3 4 4
9 9 2 5 9 9 9 9

SAMPLE OUTPUT:

7

We change a₃=3 and a₄=4. The total cost is 2+5=7.

SCORING:

Subtasks:

Input 3: N≤20
Inputs 4-9:a_i≥i
Inputs 10-15: All a_iare distinct.
Inputs 16-21: No additional constraints.
Additionally, in each of the last three subtasks, the first half of tests will satisfy c_i=1 for all i.

Problem credits: Avnith Vijayram

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

Bessie is taking an N-question true or false test (1≤N≤2⋅10⁵). For the i-th question, she will gain a_i  points if she gets it correct, lose b_i points if she gets it incorrect, or remain even if she does not answer it (0<a_i,b_i ≤10⁹).

Bessie knows all the answers because she is a smart cow, but worries that Elsie (who is administering the test) will retroactively change up to k of the questions after the test such that Bessie does not get those questions correct.

Given Q (1≤Q≤N+1) candidate values of k (0≤k≤N), determine the number of points Bessie can guarantee for each k, given that she must answer at least k questions.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains N and Q.

The next N lines each contain a_i and b_i.

The next Q lines each contain a value of k. No value of k appears more than once.

OUTPUT FORMAT (print output to the terminal / stdout):

The answer for each k on a separate line.

SAMPLE INPUT:

2 3
3 1
4 2
2
1
0

SAMPLE OUTPUT:

-3
1
7

For each value of k, it is optimal for Bessie to answer all of the questions.

SCORING:

Inputs 2-4: N≤100
Inputs 5-7: Q≤10, N≤2⋅10⁵ 
Inputs 7-20: No additional constraints.

Problem credits: Benjamin Qi

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

Answer Q(1≤Q≤10⁵) independent queries each of the following form:

You are given four integers a,b,c,d(−1018≤a,b,c,d≤10¹⁸). In one operation you can either do a+=b, or b+=a. Determine the minimum number of operations to transform (a,b) into (c,d), or if it is impossible to do so, output −1.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains Q.

The next Q lines each contain four integers a,b,c,d.

OUTPUT FORMAT (print output to the terminal / stdout):

The answer for each query on a separate line.

SAMPLE INPUT:

4
5 -3 -1 -3
5 3 5 2
5 3 8 19
5 3 5 3

SAMPLE OUTPUT:

2
-1
3
0

First query: (5,−3)→(2,−3)→(−1,−3)

Second query: Impossible.

Third query: (5,3)→(8,3)→(8,11)→(8,19)

Fourth query: No operations necessary.

SCORING:

Input 2: |a|,|b|,|c|,|d|≤10
Input 3: a,b≥0
Input 4: a≥0≥b
Input 5: a≤0≤b
Input 6: a,b≤0
Input 7: c,d≥0
Input 8: c≥0≥d
Input 9: c≤0≤d
Input 10: c,d≤0
Inputs 11-14: Q≤10³
Inputs 15-19: No additional constraints.

Problem credits: Benjamin Qi

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

注意：此问题的时限为 3 秒，是默认值的 1.5 倍。

You are given a length-N integer array a₁,a₂,…,a_N (2≤N≤10⁶,1≤a_i≤N
). Output the sum of the answers for the subproblem below over all N(N+1)/2
contiguous subarrays of a.

Given a nonempty list of integers, alternate the following operations (starting with the first operation) until the list has size exactly one.

1.Replace two consecutive integers in the list with their minimum.
2.Replace two consecutive integers in the list with their maximum.

Determine the maximum possible value of the final remaining integer.

For example,

[4, 10, 3] -> [4, 3] -> [4]
[3, 4, 10] -> [3, 10] -> [10]

In the first array, (10,3) is replaced by min(10,3)=3 and (4,3) is replaced by max(4,3)=4.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains N.

The second line contains a₁,a₂,…,a_N.

OUTPUT FORMAT (print output to the terminal / stdout):

The sum of the answer to the subproblem over all subarrays.

SAMPLE INPUT:

2
2 1

SAMPLE OUTPUT:

4

The answer for [2] is 2, the answer for [1] is 1, and the answer for [2,1] is 1.

Thus, our output should be 2+1+1=4.

SAMPLE INPUT:

3
3 1 3

SAMPLE OUTPUT:

12

SAMPLE INPUT:

4
2 4 1 3

SAMPLE OUTPUT:

22

Consider the subarray [2,4,1,3].

1.Applying the first operation on (1, 3), our new array is [2,4,1].
2.Applying the second operation on (4, 1), our new array is [2,4].
3.Applying the third operation on (2, 4), our final number is 2.

It can be proven that 2 is the maximum possible value of the final number.

SCORING:

Inputs 4-5: N≤100
Inputs 6-7: N≤5000
Inputs 8-9: max(a)≤10
Inputs 10-13: No additional constraints.

Problem credits: Benjamin Qi

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划