[PYTHON] Cumulative sum and potato method

I implemented the potato method when I was solving ABC035-C, so I will leave it as a memo. In addition, we would like the last touch for any kind of looks good or if you use at the time, including the cumulative sum. (Since I studied the potato method for the first time this time, there may be some mistakes. I would appreciate it if you could point out.)

Potato method and its implementation

The problem statement of ABC035-C is as follows.

If you want to implement it according to the problem statement, you can repeat the operation of flipping the pieces from $ l $ to $ r $, so prepare an array for N pieces (initialize with True or False at first), and Q You can invert each element from $ l_i $ to $ r_i $ each time, and the code will be as follows.

answerC1.py

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)))))

However, the constraint of n, q is $ 2 \ times {10} ^ 5 , and the worst calculation time is O ( nq $), so we can see that the time limit is not met.

The Imos method can be used here (a very effective method because you can think about dimensional expansion and special figures. It is believed.). In the potato method, addition is performed at the entrance and subtraction is performed at the exit (record). Then, when the recording stage is over, add them in order from the front (simulate).

Therefore, in this problem, when turning over from the lth to the rth, the lth element is +1 and the r + 1st element is -1. In this way, when simulating after recording, the values of the previous elements are added in order (the cumulative sum is calculated in order from the previous element), so that the number of times each element is flipped is determined. It can be calculated with a small amount of calculation. (If you think about adding +1 to the lth element and -1 to the r + 1th element, if you turn the loop with i: 0 → n, only the lth to rth elements are 1 and the other elements are You can see that it is 0.) If you implement the above as it is, the code will be as follows (O ($ n + q $)).

Also, although it has nothing to do with the potato method, changing the input to sys.stdin.readline cuts the execution time by about half, so I think that Python users should try it.

answerC2.py

#Potato law
import sys
#input→sys.stdin.readline in half the time
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))))

How to use potato method and cumulative sum

I think I explained the implementation of the potato method in ABC035 in the previous section, so I would like to generalize when to actually use it.

First, in the case of the potato method, it is considered to be used when ** the value of each interval is updated many times and finally the total value is calculated collectively **. In such a case, the amount of calculation can be significantly reduced by adding and subtracting each of ** only the entrance and exit of the section ** first, and then calculating the cumulative sum at the end.

On the other hand, in the case of cumulative sum, ** the value of the interval is not updated, and it is considered to be used when you want to find the value of several intervals at the end **. In such a case, consider ** the cumulative sum from the reference element (in many cases, the first or last element) **, and when calculating, consider the difference in the cumulative sum up to each element. By thinking, you can significantly reduce the amount of calculation.

Bonus (problem using the potato method)

ABC014-C

answerC.cc

import sys
#input→sys.stdin.readline3/In 4 hours
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)