YS - Static Range Inversions Query

Solution 1

Naive solution as described in the linked CF Blog.

Time Complexity: $\mathcal{O}(Q\sqrt N\log N)$

Copy
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;
using ll = long long;
using P = pair<int, int>;
const int N = 1e5 + 1;
const int S = 300;

Solution 2

"sweepline mo"

Time Complexity: $\mathcal{O}(Q\sqrt N)$

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

using ll = long long;
using ld = long double;
using db = double;
using str = string;  // yay python!

using pi = pair<int, int>;
using pl = pair<ll, ll>;