いもす法をABC035-Cを解いている際に実装したのでメモとして残しておきます。また、累積和を含めどのような時に使えば良さそうかについても最後に触れたいと思います。(今回初めていもす法を勉強したので間違っている箇所があるかもしれません。ご指摘していただくとありがたいです。)
いもす法とその実装
ABC035-Cの問題文は以下のようになります。
問題文通りに実装する場合、$l$から$r$までの駒を裏返す操作を繰り返せば良いので、N個の駒用の配列を用意して(最初はTrueかFalseで初期化)、Q回のそれぞれで$l_i$から$r_i$までのそれぞれの要素を反転させれば良く、以下のようなコードになります。
def int2(k):
return int(k)-1
n,q=map(int,input().split())
lr=[list(map(int2,input().split())) for i in range(q)]
x=[False]*n
for i in range(q):
for j in range(lr[i][0],lr[i][1]+1):
x[j]=not x[j]
print("".join(list(map(str,map(int,x)))))
しかし、n,qの制約が$2\times{10}^5$であり、最悪計算時間がO($nq$)になることから制限時間に間に合わないことがわかります。
ここで用いることができるのがいもす法になります(次元拡張や特殊な図形についても考えることができるので非常に有効な方法と考えられています。)。
いもす法では入口で加算、出口で減算をします(記録)。そして、記録の段階が終わったら前から順に足していきます(シミュレート)。
したがって、この問題ではl番目からr番目からまでを裏返すとした時にl番目の要素に+1をしてr+1番目の要素に-1をして記録をしています。このようにすると、記録の後にシミュレートする際に前の要素の値を順に足していく(累積和を前の要素から順に求めていく)ことで、それぞれの要素が何回裏返されたかをより少ない計算量で求めることができます。(l番目の要素に+1をしてr+1番目の要素に-1をする際を考えると、i:0→nでループを回せばちょうどl番目からr番目だけ1で他の要素は0になっていることがわかります。)
以上をそのまま実装すると以下のようなコードになります(O($n+q$)になります。)。
#いもす法
import sys
#input→sys.stdin.readline半分の時間に
input=sys.stdin.readline
n,q=map(int,input().split())
x=[0]*n
for i in range(q):
l,r=map(int,input().split())
x[l-1]+=1
if r<n:
x[r]-=1
for i in range(n-1):
x[i+1]+=x[i]
x[i]%=2
x[n-1]%=2
print("".join(list(map(str,x))))
いもす法と累積和の使用法
前節でABC035におけるいもす法の実装については説明できたと思うので、実際にどんな時に使えば良いかを一般化して残しておきたいと思います。
まず、いもす法の場合は、それぞれの区間の値に対して更新が何回も行われ、最後にまとめて全体の値を求めたい場合に用いると考えられます。このような場合はその区間の入口と出口のみに対し、加算と減算をそれぞれ先に行い、最後に累積和を求めていくことで大幅に計算量を減らすことができます。
それに対し、累積和の場合は、区間の値の更新は起きず、最後にいくつもの区間の値を求めたい場合に用いられると考えられます。このような場合は、基準となる要素(多くの場合は一番初めや一番最後の要素)からの累積和を考え、求める際にはそれぞれの要素までの累積和の差分を考えることで大幅に計算量を減らすことができます。
おまけ(いもす法を使う問題)
import sys
#input→sys.stdin.readline3/4の時間に
input=sys.stdin.readline
n=int(input())
x=[0]*1000001
for i in range(n):
a,b=map(int,input().split())
x[a]+=1
if b+1<1000001:
x[b+1]-=1
ans=x[0]
for i in range(1000000):
x[i+1]+=x[i]
ans=max(ans,x[i+1])
print(ans)