The Best Subsequence

题目描述

农夫约翰有一个长度为 $N$ $(1 \leq N \leq 10^9)$ 的二进制字符串，初始时全为 0。 他将首先按顺序对该字符串执行 $M$ 次 $(1 \leq M \leq 2 \cdot 10^5)$ 更新。每次更新会将区间 $l$ 到 $r$ 内的每个字符翻转。具体来说，翻转会把字符从 $0$ 变为 $1$，或从 $1$ 变为 $0$。 随后，他会向你提出 $Q$ 次 $(1 \leq Q \leq 2 \cdot 10^5)$ 询问。对于每个询问，他要求你在子串从 $l$ 到 $r$ 中选取字符，输出长度为 $k$ 的字典序最大的子序列。若你的答案是二进制串 $s_1s_2 \dots s_k$，则输出 $\sum_{i=0}^{k-1} 2^i \cdot s_{k-i}$（即将其视为二进制数时的数值）对 $10^9+7$ 取模的结果。 子序列是指可以通过删除原字符串中的若干个字符（也可以一个不删），且不改变剩余字符相对顺序而得到的字符串。 回顾：对于等长字符串 $A$ 与 $B$，当且仅当存在第一个位置 $i$（若存在）使得 $A_i \neq B_i$，并且 $A_i > B_i$ 时，称 $A$ 的字典序大于 $B$。

输入格式

第一行包含 $N$、$M$ 和 $Q$。 接下来 $M$ 行，每行包含两个整数 $l$ 和 $r$ ($1 \leq l \leq r \leq N$) —— 每次更新的端点。 接下来 $Q$ 行，每行包含三个整数 $l$、$r$ 和 $k$ ($1 \leq l \leq r \leq N, 1 \leq k \leq r - l + 1$) —— 每次询问的端点以及子序列长度。

输出格式

输出 $Q$ 行。第 $i$ 行应包含第 $i$ 个询问的答案。

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

9 1 1
7 9
1 8 8

3

30 1 1
1 30
1 30 30

73741816

提示

执行完这 $M$ 次操作后，字符串为 $10101$。 对于第一个询问，长度为 $5$ 的子序列只有一个，即 $10101$，其含义为 $1 \cdot 2^4 + 0 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 = 21$。 对于第二个询问，长度为 $4$ 的不同子序列有 $5$ 个：$0101$、$1101$、$1001$、$1011$、$1010$。字典序最大的子序列为 $1101$，其含义为 $1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1\cdot 2^0 = 13$。 对于第三个询问，字典序最大的序列为 $111$，其含义为 $7$。 请确保输出对 $10^9+7$ 取模后的答案。 评分： Input 4: $N \leq 10, Q \leq 1000$ Input 5: $M \leq 10$ Inputs 6-7: $N, Q \leq 1000$ Inputs 8-12: $N \leq 2 \cdot 10^5$ Inputs 13-20: 无额外限制。 题目贡献者：Chongtian Ma

标签: USACO|2025|Gold

来源

USACO|2025|Gold