문제
농부 John은 길이 N (1 ≤ N ≤ 10⁹)의 이진 문자열을 가지고 있으며, 처음에는 모두 0으로 채워져 있습니다.
먼저, John은 이 문자열에 대해 M (1 ≤ M ≤ 2⋅10⁵)번의 업데이트를 순서대로 수행합니다. 각 업데이트는 l부터 r까지의 모든 문자를 뒤집습니다. 즉, 0은 1로, 1은 0으로 바뀝니다.
그 후, John은 Q (1 ≤ Q ≤ 2⋅10⁵)개의 질의를 합니다. 각 질의에서, l과 r이 주어지는 구간의 부분 문자열 내에서 k (1 ≤ k ≤ r-l+1) 길이의 부분 수열 중 사전 순으로 가장 큰 것을 구하라고 합니다. 만약 답이 이진 문자열 s₁s₂…sₖ라면, 이를 이진수로 해석했을 때의 값, 즉
∑₍i=0₎^(k -1) 2ⁱ ⋅ s₍k -i₎
를 10⁹+7로 나눈 나머지를 출력합니다.
참고로, 부분 수열은 원래 문자열에서 일부 문자(또는 아무 문자도)를 삭제하여 순서를 유지하며 얻을 수 있는 문자열입니다. 두 이진 문자열(길이가 같을 때)은, 처음으로 서로 다른 문자가 나타나는 위치에서 1인 쪽이 사전 순으로 크다고 봅니다.
입력
첫 번째 줄에 세 정수 N, M, Q가 주어집니다.
다음 M개의 줄 각각에는 두 정수 l과 r (1 ≤ l ≤ r ≤ N)이 주어지며, 이는 해당 구간의 모든 문자를 뒤집는 업데이트를 의미합니다.
그 후 Q개의 줄 각각에는 세 정수 l, r, k (1 ≤ l ≤ r ≤ N, 1 ≤ k ≤ r-l+1)가 주어지며, 질의에 대한 구간과 부분 수열의 길이를 나타냅니다.
출력
각 질의에 대해, 구간 [l, r] 내에서 선택할 수 있는 k 길이의 부분 수열 중 사전 순으로 가장 큰 것을 찾습니다.
해당 부분 수열을 이진수로 해석한 값을 10⁹+7로 나눈 나머지를 한 줄에 하나씩 출력합니다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 10점 | |
| #2 | 10점 | |
| #3 | 20점 | |
| #4 | 30점 | |
| #5 | 30점 | 추가 제약 조건 없음 |
예제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
첫 번째 질의에서는 전체 구간 [1,5]에서 길이 5의 부분 수열은 "10101" 하나뿐이며, 이진수 값은 21입니다.
두 번째 질의에서는 구간 [1,5]에서 길이 4의 부분 수열 중 사전 순으로 가장 큰 것은 "1101"로, 이진수 값은 13입니다.
세 번째 질의에서는 길이 3의 경우 "111"이 최대이며, 값은 7입니다.
나머지 질의들도 같은 방식으로 계산됩니다.
예제2
9 1 1
7 9
1 8 8
3
업데이트 1회에서 구간 [7,9]의 문자를 뒤집습니다. 이후 질의는 구간 [1,8]에서 길이 8의 부분 수열을 구하는데, 최종 답은 3입니다.
예제3
30 1 1
1 30
1 30 30
73741816
업데이트 한 번 후 전체 문자열에 대해 길이 30의 부분 수열 중 사전 순으로 가장 큰 수열을 구하며, 이진수로 해석한 값이 73741816 (모듈로 10⁹+7)입니다.