test/yosupo/Data-Structure/Static-Range-Inversions-Query.test.cpp

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

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/static_range_inversions_query"

#include "../../../template/template.hpp"

#include "../../../others/mo.hpp"
#include "../../../SegmentTree/BinaryIndexedTree.hpp"
#include "../../../others/fastIO.hpp"

BIT<int> seg;
vi a;

void Mo::add_left(int p){
  value += seg.sum(0, a[p]);
  seg.add(a[p], 1);
}
void Mo::add_right(int p){
  value += seg.sum(a[p] + 1, n);
  seg.add(a[p], 1);
}
void Mo::del_left(int p){
  value -= seg.sum(0, a[p]);
  seg.add(a[p], -1);
}
void Mo::del_right(int p){
  value -= seg.sum(a[p] + 1, n);
  seg.add(a[p], -1);
}

int main(){
  int n,q;
  cin >> n >> q;
  a.resize(n);
  seg = BIT<int>(n);
  rep(i, n) cin >> a[i];
  vi b = a;
  sort(all(b));
  b.erase(unique(all(b)), b.end());
  rep(i, n) a[i] = lower_bound(all(b), a[i]) - b.begin();
  Mo mo(n, q);
  rep(i, q){
    int l,r;
    cin >> l >> r;
    mo.insert(l, r);
  }
  mo.build();
  rep(i, q) cout << mo.res[i] << '\n';
}

#line 1 "test/yosupo/Data-Structure/Static-Range-Inversions-Query.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/static_range_inversions_query"

#line 1 "template/template.hpp"
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <bitset>
#include <cctype>
#include <climits>
#include <functional>
#include <cassert>
#include <numeric>
#include <cstring>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define per(i, n) for(int i = (n) - 1; i >= 0; i--)
using ll = long long;
#define vi vector<int>
#define vvi vector<vi>
#define vl vector<ll>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
constexpr int mod = 1000000007;
using namespace std;
template<class T, class U>
bool chmax(T &a, const U &b){ return a < b ? (a = b, 1) : 0; }
template<class T, class U>
bool chmin(T &a, const U &b){ return a > b ? (a = b, 1) : 0; }
#line 4 "test/yosupo/Data-Structure/Static-Range-Inversions-Query.test.cpp"

#line 1 "others/mo.hpp"
ll value = 0;
struct Mo {
  struct Query { int l,r,b,idx; };
  vector<ll> res;
  vector<Query> d;
  int width, n, q;
  Mo(int n, int q) : n(n), q(q), width(max(1.0, n/max(1.0, sqrt(q*2.0/3)))), res(q), d(q){}
  void insert(const int &l, const int &r){
    assert(0 <= l && l <= r && r <= n);
    static int idx = 0;
    d[idx] = { l, r, l / width, idx };
    idx++;
  }
  void build(){
    sort(d.begin(), d.end(), [&](const Query &a, const Query &b){
      if(a.b != b.b) return a.b < b.b;
      return (a.b & 1) ? a.r > b.r : a.r < b.r;
    });
    int nl = 0, nr = 0;
    for(const auto &v : d){
      while(nl > v.l) add_left(--nl);
      while(nr < v.r) add_right(nr++);
      while(nl < v.l) del_left(nl++);
      while(nr > v.r) del_right(--nr);
      res[v.idx] = value;
    }
  }
  void add_left(int p);
  void add_right(int p);
  void del_left(int p);
  void del_right(int p);
};
#line 1 "SegmentTree/BinaryIndexedTree.hpp"
template <class T>
struct BIT {
  BIT(const int _n = 0) : n(_n), d(n){}
  BIT(const vector<T> &v) : d(v), n(v.size()){
    for(int i = 1; i <= n; i++){
      const int j = i + (i & -i);
      if(j <= n) d[j - 1] += d[i - 1];
    }
  }
  T sum(const int l, const int r) const{
    assert(0 <= l && l <= r && r <= n);
    return sum(r) - sum(l);
  }
  T sum(int i) const{
    T tot = 0;
    while(i > 0){
      tot += d[i - 1];
      i -= i & -i;
    }
    return tot;
  }
  void add(int i, const T &x){
    assert(0 <= i && i < n);
    i++;
    while(i <= n){
      d[i - 1] += x;
      i += i & -i;
    }
  }
  private:
  int n = 1;
  vector<T> d;
};
#line 1 "others/fastIO.hpp"
namespace FastIO {
struct PreCalc {
  char num[10000 * 4];
  constexpr PreCalc() : num(){
    for(int i = 0; i < 10000; i++){
      int t = i;
      for(int j = 3; j >= 0; j--){
        num[i*4 + j] = (t % 10) + '0';
        t /= 10;
      }
    }
  }
};
static constexpr PreCalc pr;
struct FastIO {
  template <class T>
  using enable_if_integer = enable_if_t<is_integral<T>::value || is_same<T, __int128_t>::value || is_same<T, __uint128_t>::value>;
  static constexpr int buf_size = 1 << 20;
  static constexpr int rem = 1 << 6;
  char in_buf[buf_size], *in_cur = in_buf + buf_size;
  char out_buf[buf_size], *out_cur = out_buf;
  FastIO(){ load(); }
  ~FastIO(){ flush(); }
  void load(){
    const int len = in_buf + buf_size - in_cur;
    memmove(in_buf, in_cur, len);
    in_cur = in_buf;
    fread(in_buf + len, 1, buf_size - len, stdin);
  }
  void flush(){
    fwrite(out_buf, 1, out_cur - out_buf, stdout);
    out_cur = out_buf;
  }
  void through(){
    if(in_cur - in_buf >= buf_size - rem) load();
    while(*in_cur <= ' ') in_cur++;
    assert(in_buf <= in_cur && in_cur < in_buf + buf_size);
  }
  #define gc() (*in_cur++)
  template <class T, enable_if_integer<T>* = nullptr>
  inline void read(T &x){
    through();
    bool neg = false;
    int c = gc();
    if(c == '-') neg = true, c = gc();
    x = c^'0'; c = gc();
    while(c >= '0' && c <= '9') x = x*10 + (c^'0'), c = gc();
    if(neg) x = -x;
  }
  inline void read(string &x){
    through();
    x.clear();
    while(true){
      char *p = in_cur;
      while(*p > ' ' && p - in_buf < buf_size - rem) p++;
      copy(in_cur, p, back_inserter(x));
      in_cur = p;
      if(*p <= ' ') break;
      load();
    }
  }
  inline void read(char &x){
    through();
    x = gc();
  }
  #undef gc
  #define pc(c) *out_cur++ = (c)
  template <class T, enable_if_integer<T>* = nullptr>
  inline void out(T x){
    static constexpr int tmp_size = sizeof(T)*5/2;
    static char tmp[tmp_size];
    if(out_cur - out_buf >= buf_size - rem) flush();
    if(!x){ pc('0'); return; }
    if(x < 0){ pc('-'); x = -x; }
    int idx = tmp_size;
    while(x >= 10000){
      idx -= 4;
      memcpy(tmp + idx, pr.num + (x % 10000)*4, 4);
      x /= 10000;
    }
    if(x < 100){
      if(x < 10){
        pc(x + '0');
      }else{
        pc(x/10 + '0');
        pc(x%10 + '0');
      }
    }else{
      if(x < 1000){
        memcpy(out_cur, pr.num + x*4 + 1, 3);
        out_cur += 3;
      }else{
        memcpy(out_cur, pr.num + x*4, 4);
        out_cur += 4;
      }
    }
    memcpy(out_cur, tmp + idx, tmp_size - idx);
    out_cur += tmp_size - idx;
  }
  inline void out(const string &s){
    flush();
    fwrite(s.c_str(), 1, s.size(), stdout);
  }
  inline void out(const char c){
    if(out_cur - out_buf >= buf_size - rem) flush();
    pc(c);
  }
  #undef pc
  template <class T>
  friend FastIO &operator>>(FastIO &io, T &x){
    io.read(x);
    return io;
  }
  template <class T>
  friend FastIO &operator<<(FastIO &io, const T &x){
    io.out(x);
    return io;
  }
};
FastIO io;
} // namespace FastIO

using FastIO::io;
#define cin io
#define cout io
#line 8 "test/yosupo/Data-Structure/Static-Range-Inversions-Query.test.cpp"

BIT<int> seg;
vi a;

void Mo::add_left(int p){
  value += seg.sum(0, a[p]);
  seg.add(a[p], 1);
}
void Mo::add_right(int p){
  value += seg.sum(a[p] + 1, n);
  seg.add(a[p], 1);
}
void Mo::del_left(int p){
  value -= seg.sum(0, a[p]);
  seg.add(a[p], -1);
}
void Mo::del_right(int p){
  value -= seg.sum(a[p] + 1, n);
  seg.add(a[p], -1);
}

int main(){
  int n,q;
  cin >> n >> q;
  a.resize(n);
  seg = BIT<int>(n);
  rep(i, n) cin >> a[i];
  vi b = a;
  sort(all(b));
  b.erase(unique(all(b)), b.end());
  rep(i, n) a[i] = lower_bound(all(b), a[i]) - b.begin();
  Mo mo(n, q);
  rep(i, q){
    int l,r;
    cin >> l >> r;
    mo.insert(l, r);
  }
  mo.build();
  rep(i, q) cout << mo.res[i] << '\n';
}