I think the problem authors maybe intended for people to use a data structure that allows for fast queries and updates. You can make it run in \$Q\log(N)\$ time by using a tree structure.
First note that flipping coins in the interval \$[l,r)\$ is the same as flipping \$[0,r)\$ and \$[0,l)\$, so we are reduced to flipping \$[0,r)\$. The idea is not to actually flip anything, but to use a binary tree which records the number, \$n_{i,j}\$ of heads over intervals of the form \$I_{i,j}=2^i[j,j+1)\$. The children of \$I_{i,j}\$ are \$I_{i-1,2j}\$ and \$I_{i-1,2j+1}\$.
Each update caused by flipping \$[0,r)\$ can be broken down as a sequence of flips of intervals \$I_{i,p_i}\$, where \$p_i=\sum_{j>i}2^{j-i}r_j\$ are derived from the binary expansion \$\sum_{j\ge0}2^jr_j\$ of \$r\$. To flip \$[0,r)\$ you have to (i) flip \$I_{i,p_i}\$ for each \$r_i=1\$, which means changing \$n_{i,p_i}\$ to \$2^i-n_{i,p_i}\$, (ii) fix up the ancestor nodes of the form \$I_{i+1,p_i/2}\$, (iii) make a note of a flip at the node \$(i,p_i)\$ in a separate array so that all descendant nodes can be reversed when they are queried.
(iii) saves the trouble of doing an order \$N\$ amount of work fixing up child nodes, at the cost of causing queries an extra \$\log_2(N)\$ work checking all ancestors for flips. Actually this isn't really much extra work because the query already took \$\log_2(N)\$ time.
There is an example implementation below. (Sorry, it's not pretty.)
Edit to add: I tried submitting this to Codechef and it passed in the pypy and Python 2 categories (with the fastest running time and the only valid entry respectively), but timed out in Python 3. Presumably it is only just fast enough as Python 2, and only just too slow as Python 3.
Edit to add more detailed explanation:
The invariant that is maintained is that the number of heads over the range \$I_{i,j}=[j\$<<\$i,(j+1)\$<<\$i)\$ is equal to sums\$[i][j]\$ or \$2^i-\$sums\$[i][j]\$ according to whether \$\sum_{d>0} \$flips\$[i+d][j\$>>\$d]\$ is even or odd respectively.
This sounds awkward, but it's just a binary tree, or rather, two identically-indexed binary trees: one corresponding to sums[][] (integers) and one to flips[][] (booleans).
The nodes are indexed by \$(i,j)\$ for \$0\le j<2^{n-i}\$, where \$n\$ is equal to \$\log_2(N)\$ rounded up to the nearest integer. The node at \$(i,j)\$ represents the interval \$[2^i.j,2^i(j+1))\$. For \$i>0\$, the children of \$(i,j)\$ are \$(i-1,2j)\$ and \$(i-1,2j+1)\$, being the two intervals that together form the parent interval, while the \$(0,j)\$ nodes are leaves.
For example, suppose \$N=32\$, \$n=5\$, and we wish to flip the interval \$[0,23)\$. ("Flipping this interval" is a shorthand for updating the trees sums[][] and flips[][] maintaining the invariant, as if the coins in positions \$0,\ldots,22\$ had all been flipped.)
First write \$23\$ in binary as \$23=16+4+2+1\$, then separately flip the intervals \$[0,16)\$, \$[16,20)\$, \$[20,22)\$, \$[22,23)\$.
For example, what should we do to flip the interval \$[16,20) = I_{2,4}\$?
First we need to change sums\$[2][4]\$ to \$4-\$sums\$[2][4]\$. That fixes queries of \$I_{2,4}\$ itself. (This corresponds to the loop in the code prefaced by the comment "flip coins [(R-M)&-M, R&-M)".)
Then we need to fix the count for the parent interval, \$[16,24) = I_{3,2}\$. This can be done by setting the number of heads in \$[16,24)\$ equal to our new number for \$[16,20)\$ plus that in \$[20,24)\$. Then the grandparent interval, \$[16,32)\$ needs to be adjusted by rewriting its head count to be that of \$[16,24)\$ plus that of \$[24,32)\$. (This corresponds to the loop in the code prefaced by the comment "Fix ancestors of changed nodes". Though actually these operations are amalgamated for all of \$[0,16)\$, \$[16,20)\$, \$[20,22)\$, \$[22,23)\$.)
Then we need to fix the count for queries of all descendant intervals: \$[16,18)\$, \$[18,20)\$, \$[16,17)\$, \$[17,18)\$, \$[18,19)\$, \$[19,20)\$. In general there could be quite a lot of these, and if we did something manually for all of them, it would ruin our complexity order. So instead we defer this operation to query time (i.e., op=1, where we seek the head count) and just note that we need it to behave as if all of these intervals had be flipped in their entirety. This is effected by inverting the boolean flips\$[2][4]\$, corresponding to the interval \$[16,20)\$. This deferred evaluation puts an obligation at query time to check the flip status of all parent nodes, inverting the headcount if the number of ancestor flip booleans is odd. (Variable fl in csum().)
Note: the code below is \$O(N+Q\log(N))\$ rather than \$O(Q\log(N))\$. The additional \$N\$ comes from allocating the arrays sums and flips. This term could be removed by using dictionaries instead, replacing the initialisation of sums and flips by
from collections import defaultdict
sums=[defaultdict(int) for i in range(n+1)]
flips=[defaultdict(bool) for i in range(n+1)]
but I've left it as arrays here because it runs faster for the typical values we are using here, roughly \$N=Q=100000\$.
from sys import stdin
def getline(): return map(int,stdin.readline().split())
N, Q = getline()
n=1
while (1<<n)<N: n+=1
sums=[[0]*((N>>i)+2) for i in range(n+1)]
flips=[[False]*((N>>i)+1) for i in range(n+1)]
# We keep information about the dice over "standard intervals" I_{i,j}=[j<<i,(j+1)<<i).
#
# These form a binary tree where the children of I_{i,j} are I_{i-1,2j} and I_{i-1,2j+1},
# and the parent of I_{i,j} is I_{i+1,j>>1}.
#
# The parent interval I_{i,j} is the disjoint union of its two children.
# For example if i=3, j=5, then I_{3,5}=[40,48) is the union of
# I_{2,10}=[40,44) and I_{2,11}=[44,48).
#
# The interval [0,R) decomposes into a disjoint union of standard intervals
# I_{i,j} according to the binary expansion of R:
# If R = r_n r_{n-1} ... r_0 in binary (r_i=0 or 1), then
# [0,R) is the disjoint union of I_{i,(R>>i)-1} over i such that r_i=1.
#
# The collection of all ancestor nodes of all standard intervals in the decomposition
# of [0,R) is I_{i,R>>i} over all i>0 (whether or not r_i = 0 or 1).
#
# We maintain the invariant:
# Number of heads over the range I_{i,j} = sums[i][j] modified by flips[i'][j']
# as (i',j') ranges over the ancestors of (i,j) in the tree.
def flip(R):# flip coins [0,R)
m=0;M=1
while M<=R:
if R&M:# flip coins [(R-M)&-M, R&-M)
t=(R-M)>>m
sums[m][t]=M-sums[m][t]
flips[m][t]=not flips[m][t]# invert flip status to make descendants work
m+=1;M<<=1
# Fix ancestors of changed nodes
m=1;M=2
while M<=N:
R2=R>>m
sums[m][R2]=sums[m-1][2*R2]+sums[m-1][2*R2+1]
if flips[m][R2]: sums[m][R2]=M-sums[m][R2]
m+=1;M<<=1
def csum(R):# Sum over [0,R)
s=0
fl=False
for m in range(n,-1,-1):
M=1<<m
if R&M:
t=sums[m][(R-M)>>m]
if fl: t=M-t
s+=t
fl=(fl!=flips[m][R>>m])# exclusive or
return s
out=[]
for i in range(Q):
op, A, B = getline()# operation, start, end (inclusive)
B+=1
if op==0: flip(A);flip(B)
else: out.append(str(csum(B)-csum(A)))
print("\n".join(out))
pypy\$\endgroup\$#do Somethingis worse than no comment at all \$\endgroup\$listbefore you unpack. Unpacking works with generators. \$\endgroup\$ifstatement to flip the coins can be simplified toc[m] = 1 - c[m]\$\endgroup\$