Recursive Queries (Codeforces 1117G)
Tags: Others, data structures

You are given a permutation $$$p_1, p_2, \dots, p_n$$$. You should answer $$$q$$$ queries. Each query is a pair $$$(l_i, r_i)$$$, and you should calculate $$$f(l_i, r_i)$$$.Let's denote $$$m_{l, r}$$$ as the position of the maximum in subsegment $$$p_l, p_{l+1}, \dots, p_r$$$.Then $$$f(l, r) = (r - l + 1) + f(l, m_{l,r} - 1) + f(m_{l,r} + 1, r)$$$ if $$$l \le r$$$ or $$$0$$$ otherwise.

Input: The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n \le 10^6$$$, $$$1 \le q \le 10^6$$$) — the size of the permutation $$$p$$$ and the number of queries.The second line contains $$$n$$$ pairwise distinct integers $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$, $$$p_i \neq p_j$$$ for $$$i \neq j$$$) — permutation $$$p$$$.The third line contains $$$q$$$ integers $$$l_1, l_2, \dots, l_q$$$ — the first parts of the queries.The fourth line contains $$$q$$$ integers $$$r_1, r_2, \dots, r_q$$$ — the second parts of the queries.It's guaranteed that $$$1 \le l_i \le r_i \le n$$$ for all queries.

Output: Print $$$q$$$ integers — the values $$$f(l_i, r_i)$$$ for the corresponding queries.

Note: Description of the queries:   $$$f(2, 2) = (2 - 2 + 1) + f(2, 1) + f(3, 2) = 1 + 0 + 0 = 1$$$;  $$$f(1, 3) = (3 - 1 + 1) + f(1, 2) + f(4, 3) = 3 + (2 - 1 + 1) + f(1, 0) + f(2, 2) = 3 + 2 + (2 - 2 + 1) = 6$$$;  $$$f(1, 4) = (4 - 1 + 1) + f(1, 2) + f(4, 4) = 4 + 3 + 1 = 8$$$;  $$$f(2, 4) = (4 - 2 + 1) + f(2, 2) + f(4, 4) = 3 + 1 + 1 = 5$$$;  $$$f(1, 1) = (1 - 1 + 1) + 0 + 0 = 1$$$. 

Sample Inputs:
4 5
3 1 4 2
2 1 1 2 1
2 3 4 4 1

Sample Outputs:
1 6 8 5 1

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def fenwick_tree(a):
    tree = list(a)
    for i in range(1, len(tree)):
        j = i + (i & -i)
        if j < len(tree):
            tree[j] += tree[i]
    return tree

def get_sum0(i, tree):
    s = 0
    while i > 0:
        s += tree[i]
        i -= i & -i
    return s

def get_sum(s, t, tree):
    ans = get_sum0(t, tree) - get_sum0(s - 1, tree)
    return ans

def add(i, x, tree):
    while i < len(tree):
        tree[i] += x
        i += i & -i

def make_graph(n, m, x):
    s = [0] * (n + 3)
    for i in range(0, 2 * m, 2):
        s[x[i] + 2] += 1
    for i in range(3, n + 3):
        s[i] += s[i - 1]
    G = [0] * m
    for i in range(0, 2 * m, 2):
        j = x[i] + 1
        G[s[j]] = x[i ^ 1]
        s[j] += 1
    return (G, s)
(n, q) = map(int, input().split())
inf = pow(10, 9) + 1
p = [inf] + list(map(int, input().split())) + [inf]
l = list(map(int, input().split()))
r = list(map(int, input().split()))
ans = [r0 - l0 + 1 for (l0, r0) in zip(l, r)]
x = [0] * (n + 1)
(y, z) = ([0] * (2 * q), [0] * (2 * n))
for i in range(q):
    y[2 * i + 1] = i
for i in range(n):
    z[2 * i + 1] = i + 1
for _ in range(2):
    st = [0]
    for i in range(1, n + 1):
        pi = p[i]
        while p[st[-1]] < pi:
            st.pop()
        x[i] = i - st[-1] - 1
        st.append(i)
    for i in range(q):
        y[2 * i] = l[i]
    for i in range(1, n + 1):
        z[2 * i - 2] = i - x[i]
    (G, s0) = make_graph(n, q, y)
    (H, s1) = make_graph(n, n, z)
    p.reverse()
    tree1 = fenwick_tree(x)
    tree2 = [0] * (n + 1)
    for u in range(1, n + 1):
        for j in range(s0[u], s0[u + 1]):
            i = G[j]
            v = r[i]
            (l[i], r[i]) = (n - r[i] + 1, n - l[i] + 1)
            ans[i] += get_sum(u, v, tree1)
            ans[i] -= get_sum(u, v, tree2) * u
        for j in range(s1[u], s1[u + 1]):
            i = H[j]
            add(i, u, tree1)
            add(i, 1, tree2)
sys.stdout.write(' '.join(map(str, ans)))

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def fenwick_tree(a):
    tree = list(a)
    for i in range(1, len(tree)):
        j = i + (i & -i)
        if j < len(tree):
            tree[j] += tree[i]
    return tree

def get_sum0(i, tree):
    s = 0
    while i > 0:
        s += tree[i]
        i -= i & -i
    return s

def get_sum(s, t, tree):
    ans = get_sum0(t, tree) - get_sum0(s - 1, tree)
    return ans

def add(i, x, tree):
    while i < len(tree):
        tree[i] += x
        i += i & -i
(n, q) = map(int, input().split())
inf = pow(10, 9) + 1
p = [inf] + list(map(int, input().split())) + [inf]
l = list(map(int, input().split()))
r = list(map(int, input().split()))
ans = [0] * q
x = [0] * (n + 1)
lc = max(n + 1, q + 1)
cnt = [0] * lc
cnt[0] = -1
s = [0] * q
t = [0] * n
for _ in range(2):
    st = [0]
    for i in range(1, n + 1):
        pi = p[i]
        while p[st[-1]] < pi:
            st.pop()
        x[i] = i - st[-1] - 1
        st.append(i)
    for i in l:
        cnt[i] += 1
    for i in range(1, lc):
        cnt[i] += cnt[i - 1]
    for i in range(q):
        s[cnt[l[i]]] = i
        cnt[l[i]] -= 1
    for i in range(1, lc):
        cnt[i] = 0
    for i in range(1, n + 1):
        cnt[i - x[i]] += 1
    for i in range(1, lc):
        cnt[i] += cnt[i - 1]
    for i in range(1, n + 1):
        t[cnt[i - x[i]]] = i
        cnt[i - x[i]] -= 1
    for i in range(1, lc):
        cnt[i] = 0
    p.reverse()
    tree1 = fenwick_tree(x)
    tree2 = [0] * (n + 1)
    (j, k) = (0, 0)
    for u in range(1, n + 1):
        while j < q:
            i = s[j]
            if l[i] ^ u:
                break
            v = r[i]
            (l[i], r[i]) = (n - r[i] + 1, n - l[i] + 1)
            ans[i] += get_sum(u, v, tree1)
            ans[i] -= get_sum(u, v, tree2) * u
            j += 1
        while k < n:
            i = t[k]
            if i - x[i] ^ u:
                break
            add(i, u, tree1)
            add(i, 1, tree2)
            k += 1
for i in range(q):
    ans[i] += r[i] - l[i] + 1
sys.stdout.write(' '.join(map(str, ans)))

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def fenwick_tree(a):
    tree = list(a)
    for i in range(1, len(tree)):
        j = i + (i & -i)
        if j < len(tree):
            tree[j] += tree[i]
    return tree

def get_sum0(i, tree):
    s = 0
    while i > 0:
        s += tree[i]
        i -= i & -i
    return s

def get_sum(s, t, tree):
    ans = get_sum0(t, tree) - get_sum0(s - 1, tree)
    return ans

def add(i, x, tree):
    while i < len(tree):
        tree[i] += x
        i += i & -i
(n, q) = map(int, input().split())
inf = pow(10, 9) + 1
p = [inf] + list(map(int, input().split())) + [inf]
l = list(map(int, input().split()))
r = list(map(int, input().split()))
ans = [0] * q
x = [0] * (n + 1)
for _ in range(2):
    st = [0]
    for i in range(1, n + 1):
        pi = p[i]
        while p[st[-1]] < pi:
            st.pop()
        x[i] = i - st[-1] - 1
        st.append(i)
    s = [l[i] * q + i for i in range(q)]
    s.sort()
    t = [(i - x[i]) * (n + 1) + i for i in range(1, n + 1)]
    t.sort()
    p.reverse()
    tree1 = fenwick_tree(x)
    tree2 = [0] * (n + 1)
    (j, k) = (0, 0)
    for u in range(1, n + 1):
        while j < q:
            if s[j] // q ^ u:
                break
            i = s[j] % q
            v = r[i]
            (l[i], r[i]) = (n - r[i] + 1, n - l[i] + 1)
            ans[i] += get_sum(u, v, tree1)
            ans[i] -= get_sum(u, v, tree2) * u
            j += 1
        while k < n:
            if t[k] // (n + 1) ^ u:
                break
            i = t[k] % (n + 1)
            add(i, u, tree1)
            add(i, 1, tree2)
            k += 1
for i in range(q):
    ans[i] += r[i] - l[i] + 1
sys.stdout.write(' '.join(map(str, ans)))