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

#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>;

Solution 2

"sweepline mo"

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

#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>;