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)$

1#include <bits/stdc++.h>
2using namespace std;
3 
4using ll = long long;
5using ld = long double;
6using db = double; 
7using str = string; // yay python!
8
9using pi = pair<int,int>;
10using pl = pair<ll,ll>;

Solution 2

"sweepline mo"

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

1#include <bits/stdc++.h>
2using namespace std;
3 
4using ll = long long;
5using ld = long double;
6using db = double; 
7using str = string; // yay python!
8
9using pi = pair<int,int>;
10using pl = pair<ll,ll>;