Алгоритм Мо

Дана перестановка из n элементов.
Ответьте на m запросов про число инверсий для подотрезка перестановки от l до r.
Инверсией называется пара индексов i, j такая, что i < j и a_i > a_j, где a_i - это i-й элемент перестановки.

Входные данные:
В первой строке задано число n (1 <= n <= 10⁵).
Во второй строке задана перестановка из n элементов (элементы перестановки - попарно различные целые числа от 1 до n).
В третьей строке задано число m (1 <= m <= 10⁵).
В последующих m строках содержится по два числа l и r - границы запроса (1 <= l, r <= n).

Выходные данные:
Выведите m строк - ответы на данные запросы.

Примеры:
 

Входные данные	Выходные данные
5 4 5 2 3 1 3 1 3 3 5 1 5	2 2 8
6 5 2 4 3 1 6 3 4 6 2 5 1 5	1 4 8

У Эвана есть любимое число k и массив a_i длины n. Теперь он просит вас ответить на m запросов.

Для каждого запроса, задаваемого парой чисел l и r, требуется найти количество пар целых чисел i и j таких, что l ≤ i ≤ j ≤ r и xor чисел a_i, a_i + 1, ..., a_j равен k.

Входные данные:
В первой строке даны целые числа n, m и k (1 ≤ n, m ≤ 10⁵, 0 ≤ k ≤ 10⁶) — длина массива, количество запросов и любимое число Эвана соответственно.
Во второй строке записаны n целых чисел ai (0 ≤ a_i ≤ 10⁶) — имеющийся у Эвана массив.
Дальше идут m строк. В i-й строке записаны числа l_i и r_i (1 ≤ l_i ≤ r_i ≤ n), определяющие i-й запрос.

Выходные данные:
Выведите m строк, ответы на запросы в порядке их появления во входных данных.

Примеры:
 

Входные данные	Выходные данные
6 2 3 1 2 1 1 0 3 1 6 3 5	7 0
5 3 1 1 1 1 1 1 1 5 2 4 1 3	9 4 4

Имеется массив натуральных чисел a₁, a₂, ..., a_n. Рассмотрим некоторый его подмассив a_l, a_l + 1, ..., a_r, где 1 ≤ l ≤ r ≤ n, и для каждого натурального числа s обозначим через K_s число вхождений числа s в этот подмассив. Назовем мощностью подмассива сумму произведений K_s·K_s·s по всем различным натуральным s. Так как количество различных чисел в массиве конечно, сумма содержит лишь конечное число ненулевых слагаемых.

Необходимо вычислить мощности каждого из t заданных подмассивов.

Входные данные
Первая строка содержит два целых числа n и t (1 ≤ n, t ≤ 200000) — длина массива и количество запросов соответственно.
Вторая строка содержит n натуральных чисел ai (1 ≤ a_i ≤ 10⁶) — элементы массива.
Следующие t строк содержат по два натуральных числа l и r (1 ≤ l ≤ r ≤ n) — индексы левого и правого концов соответствующего подмассива.

Выходные данные
Выведите t строк, где i-ая строка содержит единственное натуральное число — мощность подмассива i-го запроса.

Примеры:
 

Входные данные	Выходные данные
3 2 1 2 1 1 2 1 3	3 6
8 3 1 1 2 2 1 3 1 1 2 7 1 6 2 7	20 20 20

Вам дан массив целых чисел А длиной n.
Необходимо ответить на m запросов вида "сообщите количество различных чисел подотрезка массива А от элемента с индексом l до элемента с индексом r" (обе границы подотрезка включены, массив нумеруется с единицы).

Входные данные:
В первой строке дано два числа: n - количество элементов массива и m - количество запросов (1 <= n, m <= 10⁵).
Во второй строке дано n целых чисел A_i - элементы массива (0 <= A_i <= 10⁶).
Далее дано m строк, в каждой по два числа l и r - границы подотрезка для каждого запроса (1 <= l <= r <= n).

Выходные данные:
В единственной строке выведите через пробел m чисел - для каждого запроса количестве различных чисел на соответствующем подотрезке.

Пример:
 

Входные данные	Выходные данные
7 5 1 3 1 2 2 4 1 1 3 4 5 3 7 2 4 7 7	2 1 3 3 1

Для приведенного ниже кода, найдите асимптотику.

#include <bits/stdc++.h>
using namespace std;

int K;

struct query
{
    int l, r, ind;
};

bool cmp(query a, query b)
{
    if (a.l / K != b.l / K)
        return a.l / K < b.l / K;
    else
        return a.r < b.r;
}

int main()
{
    int n, q;
    cin >> n >> q;
    // для простоты, считайте, что q = n
    K = (int)sqrt(n);

    vector <int> arr(n);
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    vector <query> ask(q);
    vector <int> ans(q);
    for (int i = 0; i < q; i++)
    {
        cin >> ask[i].l >> ask[i].r;
        ask[i].l--; ask[i].r--;
        ask[i].ind = i;
    }
    sort(ask.begin(), ask.end(), cmp);

    // Посчитайте асимптотику только части кода, 
    // расположенной ниже этого комментария

    int sum = 0, L = ask[0].l, R = ask[0].r;
    for (int i = ask[0].l; i <= ask[0].r; i++)
        sum += arr[i];
    ans[ask[0].ind] = sum;

    for (int i = 1; i < q; i++)
    {
        for (int j = L; j < ask[i].l; j++)
            sum -= arr[j];
        for (int j = L - 1; j >= ask[i].l; j--)
            sum += arr[j];
        for (int j = R + 1; j <= ask[i].r; j++)
            sum += arr[j];
        for (int j = R; j > ask[i].r; j--)
            sum -= arr[j];
        ans[ask[i].ind] = sum;
        L = ask[i].l; R = ask[i].r;
    }

    for (int i = 0; i < q; i++)
        cout << ans[i] << endl;

    return 0;
}

1) каждая итерация O(sqrt(n))       
2) суммарно O(nsqrt(n))     
3) каждая итерация O(logn)       
4) суммарно O(nlogn)