test/yosupo/static_range_inversions_query.mo.test.cpp

• View this file on GitHub
• Last update: 2024-09-01 12:11:12+09:00
• Problem: https://judge.yosupo.jp/problem/static_range_inversions_query

Depends on

• Binary Indexed Tree (src/DataStructure/BinaryIndexedTree.hpp)
• 座標圧縮 (src/Misc/compress.hpp)
• Mo's Algorithm (src/Misc/Mo.hpp)

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/static_range_inversions_query
// competitive-verifier: TLE 1
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#include <algorithm>
#include "src/Misc/compress.hpp"
#include "src/Misc/Mo.hpp"
#include "src/DataStructure/BinaryIndexedTree.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, Q;
 cin >> N >> Q;
 int A[N];
 for (int i= 0; i < N; i++) cin >> A[i];
 vector<int> v(A, A + N);
 auto id= compress(v);
 for (int i= 0; i < N; i++) A[i]= id(A[i]);
 Mo mo;
 for (int q= 0; q < Q; q++) {
  int l, r;
  cin >> l >> r;
  mo.query(l, r);
 }
 BinaryIndexedTree<long long> bit(N + 1);
 long long inv= 0, total= 0;
 auto addl= [&](int i) { inv+= bit.sum(A[i]), bit.add(A[i], 1), total++; };
 auto addr= [&](int i) { inv+= total - bit.sum(A[i] + 1), bit.add(A[i], 1), total++; };
 auto erasel= [&](int i) { inv-= bit.sum(A[i]), bit.add(A[i], -1), total--; };
 auto eraser= [&](int i) { inv-= total - bit.sum(A[i] + 1), bit.add(A[i], -1), total--; };
 long long ans[Q];
 auto out= [&](int q) { ans[q]= inv; };
 mo.run(addl, addr, erasel, eraser, out);
 for (int q= 0; q < Q; q++) cout << ans[q] << "\n";
 return 0;
}

#line 1 "test/yosupo/static_range_inversions_query.mo.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/static_range_inversions_query
// competitive-verifier: TLE 1
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#include <algorithm>
#line 4 "src/Misc/compress.hpp"
template <class T> auto compress(std::vector<T> &v) {
 return std::sort(v.begin(), v.end()), v.erase(std::unique(v.begin(), v.end()), v.end()), [&v](T x) { return std::lower_bound(v.begin(), v.end(), x) - v.begin(); };
}
#line 4 "src/Misc/Mo.hpp"
#include <numeric>
#include <cmath>
struct Mo {
 std::vector<int> L, R;
 Mo() {}
 void query(int l, int r) { L.push_back(l), R.push_back(r); } /* [l, r) */
 template <typename AL, typename AR, typename EL, typename ER, typename O> void run(const AL &add_left, const AR &add_right, const EL &erase_left, const ER &erase_right, const O &out) {
  int q= L.size(), n= *std::max_element(R.begin(), R.end()), bs= n / std::min<int>(n, std::sqrt(q));
  std::vector<int> ord(q);
  std::iota(ord.begin(), ord.end(), 0), std::sort(ord.begin(), ord.end(), [&](int a, int b) {
   int ablk= L[a] / bs, bblk= L[b] / bs;
   return ablk != bblk ? ablk < bblk : (ablk & 1) ? R[a] > R[b] : R[a] < R[b];
  });
  int l= 0, r= 0;
  for (auto i: ord) {
   while (l > L[i]) add_left(--l);
   while (r < R[i]) add_right(r++);
   while (l < L[i]) erase_left(l++);
   while (r > R[i]) erase_right(--r);
   out(i);
  }
 }
 template <typename A, typename E, typename O> void run(const A &add, const E &erase, const O &out) { run(add, add, erase, erase, out); }
};
#line 4 "src/DataStructure/BinaryIndexedTree.hpp"
template <typename T> class BinaryIndexedTree {
 std::vector<T> dat;
public:
 BinaryIndexedTree(int n): dat(n + 1, T()) {}
 BinaryIndexedTree(int n, T a): BinaryIndexedTree(std::vector<T>(n, a)) {}
 BinaryIndexedTree(const std::vector<T>& y): dat(y.size() + 1, 0) {
  for (int i= y.size(); i--;) dat[i + 1]= y[i];
  for (int i= 1, e= dat.size(), j; i < e; ++i)
   if ((j= i + (i & -i)) < e) dat[j]+= dat[i];
 }
 void add(int i, T a= 1) {
  for (++i; i < (int)dat.size(); i+= i & -i) dat[i]+= a;
 }
 T sum(int i) const {  // sum [0,i)
  T s= 0;
  for (; i; i&= i - 1) s+= dat[i];
  return s;
 }
 T sum(int l, int r) const { return sum(r) - sum(l); }  // sum [l,r)
 T operator[](int k) const { return sum(k + 1) - sum(k); }
 int find(T k) const {  // min { i : sum(i+1) > k } -> kth element(0-indexed)
  int i= 0;
  for (int p= 1 << (std::__lg(dat.size() - 1) + 1), e= dat.size(); p; p>>= 1)
   if (i + p < e && dat[i + p] <= k) k-= dat[i+= p];
  return i + 1 == (int)dat.size() ? -1 : i;  // -1 -> no solutions
 }
};
#line 10 "test/yosupo/static_range_inversions_query.mo.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, Q;
 cin >> N >> Q;
 int A[N];
 for (int i= 0; i < N; i++) cin >> A[i];
 vector<int> v(A, A + N);
 auto id= compress(v);
 for (int i= 0; i < N; i++) A[i]= id(A[i]);
 Mo mo;
 for (int q= 0; q < Q; q++) {
  int l, r;
  cin >> l >> r;
  mo.query(l, r);
 }
 BinaryIndexedTree<long long> bit(N + 1);
 long long inv= 0, total= 0;
 auto addl= [&](int i) { inv+= bit.sum(A[i]), bit.add(A[i], 1), total++; };
 auto addr= [&](int i) { inv+= total - bit.sum(A[i] + 1), bit.add(A[i], 1), total++; };
 auto erasel= [&](int i) { inv-= bit.sum(A[i]), bit.add(A[i], -1), total--; };
 auto eraser= [&](int i) { inv-= total - bit.sum(A[i] + 1), bit.add(A[i], -1), total--; };
 long long ans[Q];
 auto out= [&](int q) { ans[q]= inv; };
 mo.run(addl, addr, erasel, eraser, out);
 for (int q= 0; q < Q; q++) cout << ans[q] << "\n";
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	example_00	AC	5 ms	4 MB
g++-13	max_00	AC	898 ms	7 MB
g++-13	max_01	AC	807 ms	7 MB
g++-13	max_02	AC	801 ms	7 MB
g++-13	random_00	AC	112 ms	5 MB
g++-13	random_01	AC	236 ms	5 MB
g++-13	random_02	AC	290 ms	5 MB
g++-13	small_a_00	AC	575 ms	7 MB
g++-13	small_n_00	AC	8 ms	4 MB
g++-13	small_n_01	AC	18 ms	5 MB
g++-13	small_n_02	AC	15 ms	4 MB
g++-13	small_n_03	AC	11 ms	4 MB
g++-13	small_n_04	AC	7 ms	4 MB
clang++-18	example_00	AC	5 ms	4 MB
clang++-18	max_00	AC	795 ms	7 MB
clang++-18	max_01	AC	807 ms	7 MB
clang++-18	max_02	AC	838 ms	7 MB
clang++-18	random_00	AC	125 ms	5 MB
clang++-18	random_01	AC	247 ms	5 MB
clang++-18	random_02	AC	315 ms	5 MB
clang++-18	small_a_00	AC	665 ms	7 MB
clang++-18	small_n_00	AC	8 ms	4 MB
clang++-18	small_n_01	AC	18 ms	5 MB
clang++-18	small_n_02	AC	15 ms	4 MB
clang++-18	small_n_03	AC	12 ms	4 MB
clang++-18	small_n_04	AC	9 ms	4 MB

Back to top page