06766. USACO·最佳子序列 未做

Farmer John 有一个长为 $N$ 的位串（$1\le N\le 10^9$），初始时全部为零。

他将首先按顺序对字符串执行 $M$ 次更新（$1\le M\le 2\cdot 10^5$）。每次更新会翻转从 $l$ 到 $r$ 的每个字符。具体地说，翻转一个字符会将其从 $0$ 变为 $1$，或反之。

然后，他会进行 $Q$ 次查询（$1\le Q\le 2\cdot 10^5$）。对于每个查询，他要求你输出由从 $l$ 到 $r$ 的子串中的字符组成的长为 $k$ 的字典序最大子序列。如果你的答案是一个位串 $s_1{s}_2\dots s_k$，则输出 ${\sum }_{i=0}^{k-1}{2}^i\cdot s_{k-i}$（即将其解释为二进制数时的值）模 $10^9+7$ 的余数。

一个字符串的子序列是可以从中通过删除一些或不删除字符而不改变余下字符的顺序得到的字符串。

我们知道，字符串 $A$ 的字典序大于长度相等的字符串 $B$，当且仅当在第一个 $A_i\ne B_i$ 的位置 $i$ 上（如果存在），我们有 $A_i>B_i$。

输入的第一行包含 $N$，$M$ 和 $Q$。

以下 $M$ 行，每行包含两个整数 $l$ 和 $r$（$1\le l\le r\le N$），为每次更新的端点。

以下 $Q$ 行，每行包含三个整数 $l$，$r$ 和 $k$（$1\le l\le r\le N$，$1\le k\le r-l+1$），为每个查询的端点和子序列的长度。

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

【样例解释】

确保输出答案对 $10^9+7$ 取模。

• 测试点 5：$M\le 10$。

• 测试点 6-7：$N,Q\le 1000$。

• 测试点 8-12：$N\le 2\cdot 10^5$。

• 测试点 13-20：没有额外限制。

【数据规模与约定】

• 测试点 4：$N\le 10$，$Q\le 1000$。

• 测试点 5：$M\le 10$。

• 测试点 6-7：$N,Q\le 1000$。

• 测试点 8-12：$N\le 2\cdot 10^5$。

• 测试点 13-20：没有额外限制。

供题：Chongtian Ma