Although I’ve almost finished all the topics on modular arithmetic and number theory covered in the USACO Guide, I still feel completely stuck when facing problems (especially this latest one). For example, in this problem I don’t know how to handle the case when num < k. Is it that my ability isn’t enough, or is my learning method wrong?
Question: [https://usaco.org/index.php?page=viewproblem2&cpid=1498&lang=en]
import sys
from bisect import bisect_left as bileft;from bisect import bisect_right as biright
from collections import defaultdict
input = sys.stdin.readline
mod = 10**9+7
n,m,q = map(int,input().split())
diff = defaultdict(int)
for _ in range(m):
l,r = map(int,input().split())
diff[l] ^= 1 # mark flip toggle at l
diff[r+1] ^= 1 # mark flip toggle after r
diflist = sorted([[key,val] for key,val in diff.items()]) # [3,1],[5,1] (sorted toggle points)
countlist = [[0,0,0]] # [pos, prefix_ones_before_pos, is_one_block_flag]
status = 0
for i,[key,val] in enumerate(diflist):
if val == 1:
if status:
countlist.append([key,countlist[-1][1]+diflist[i][0]-diflist[i-1][0]-1,0]) # close one-run
else:
countlist.append([key,countlist[-1][1]+1,1]) # start one-run
status ^= 1
bilist = [i[0] for i in countlist] # boundary positions for binary search
ans = []
for _ in range(q):
l,r,k = map(int,input().split());l-=1
li = biright(bilist,l)-1;ri = biright(bilist,r)-1 # find blocks covering l and r
if countlist[li][2]:numl = l-countlist[li][0]+countlist[li][1]
else:numl=countlist[li][1]
if countlist[ri][2]:numr = r-countlist[ri][0]+countlist[ri][1]
else:numr=countlist[ri][1]
num = numr-numl # number of '1's in substring [l+1..r]
if num >= k:ans.append(str((pow(2,k,mod)-1)%mod)) # all-ones answer
else:
pass # need help here: build lexicographically largest subsequence when num < k
print('\n'.join(ans))