This problem can be solved with a lazy segment tree in a total of \(O(N+Q\log N)\) time.

Each node of the segment tree stores the following \(6\) values for the corresponding segment:

• the number of \(0\)
• the number of \(1\)
• the number of \(2\)
• the number of \(1,0\) (i.e. the number of pairs \((i,j)\) such that \(i<j\), \(A_i=1\), and \(A_j=0\))
• the number of \(2,0\)
• the number of \(2,1\)

An operator store the following information:

• \(0,1,2\) is replaced with which value?

For the product of nodes and how to process the query, please refer to the following sample codes.

Sample code (C++, ACL)
Sample code (Python)