#PU1498. USACO 2025 February Contest, Gold — Problem 2. The Best Subsequence

    ID: 1431 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:feb25来源:usaco.orgscoring:equal_test_cases线段树

USACO 2025 February Contest, Gold — Problem 2. The Best Subsequence

USACO 2025 February Contest, Gold — Problem 2. The Best Subsequence

题目描述

Farmer John has a binary string of length NN (1≤N≤109)(1 \leq N \leq 10^9), initially all zeros. He will first perform MM (1≤M≤2⋅1051 \leq M \leq 2 \cdot 10^5) updates on the string, in order. Each update flips every character from ll to rr. Specifically, flipping a character changes it from 00 to 11, or vice versa. Then, he asks you QQ (1≤Q≤2⋅1051 \leq Q \leq 2 \cdot 10^5) queries. For each query, he asks you to output the lexicographically greatest subsequence of length kk comprised of characters from the substring from ll to rr. If your answer is a binary string s1s2…sks_1s_2 \dots s_k, then output ∑i=0k−12i⋅sk−i\sum_{i=0}^{k-1} 2^i \cdot s_{k-i} (that is, its value when interpreted as a binary number) modulo 109+710^9+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 AA is lexicographically greater than string BB of equal length if and only if at the first position ii, if it exists, where Ai≠BiA_i \neq B_i, we have Ai>BiA_i > B_i.

输入格式

The first line contains NN, MM, and QQ. The next MM lines contain two integers, ll and rr (1≤l≤r≤N1 \leq l \leq r \leq N) — the endpoints of each update. The next QQ lines contain three integers, ll, rr, and kk (1≤l≤r≤N,1≤k≤r−l+11 \leq l \leq r \leq N, 1 \leq k \leq r - l + 1) — the endpoints of each query and the length of the subsequence.

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

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
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 \cdot 2^4 + 0 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 = 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 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1\cdot 2^0 = 13$.
For the third query, the lexicographically largest sequence is $111$, which is
interpreted as $7$.

样例 2

9 1 1
7 9
1 8 8
3

样例 3

30 1 1
1 30
1 30 30
73741816
Make sure to output the answer modulo $10^9+7$.