Auto comment: topic has been translated by ligaydima (original revision, translated revision, compare)

Take a look at this problem and its editorial: https://mirror.codeforces.com/contest/940/problem/F

Actual Discussion: https://mirror.codeforces.com/blog/entry/44711

Tl;dr version that I understood.

Online Mo's Algorithm : $$$O((N + Q)*N^{\frac{2}{3}})$$$

Method:

Group into contiguous buckets, each of size $$$N^{\frac{2}{3}}$$$.

So number of buckets = $$$N^{\frac{1}{3}}$$$

for lbucket = 0 to N^1/3:
    for rbucket = lbucket to N^1/3:
        // iterate over the stream of all the updates AND queries from this pair
        // i.e the L belongs to [lbucket * N^2/3, (lbucket + 1) * N^2/3)
        // and R belongs to [rbucket * N^2/3, (rbucket + 1) * N^2/3)
        // in chronological order
            if at a query: 
                slide l pointer to query l, slide r pointer to query r. 
                // should be 2*N^2/3 shifts at most
                print global answer
            if at an update:
                update the global state