The Best Subsequence
Farmer John has a binary string of length N (1≤N≤109), initially all zeros.
He will first perform M (1≤M≤2⋅105) 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⋅105) 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 s1s2…sk, then output ∑i=0k−12i⋅sk−i (that is, its value when interpreted as a binary number) modulo 109+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 Ai=Bi, we have Ai>Bi.
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⋅24+0⋅23+1⋅22+0⋅21+1⋅20=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⋅23+1⋅22+0⋅21+1⋅20=13.
For the third query, the lexicographically largest sequence is 111, which is interpreted as 7.
Make sure to output the answer modulo 109+7.
SCORING:
- Input 4: N≤10,Q≤1000
- Input 5: M≤10
- Inputs 6-7: N,Q≤1000
- Inputs 8-12: N≤2⋅105
- Inputs 13-20: No additional constraints.
Problem credits: Chongtian Ma
Source: USA Computing Olympiad.
Input Format
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
Output Q lines. The ith line should contain the answer for the ith query.