列の平方分割(Sqrt-Decomposition)

説明

列の平方分割により、区間クエリを効率的に処理できるようになる場合がある。

ここでは長さ $N$ の要素があって各要素にはその要素の高さと値が設定されているときの問題を扱う(二次元座標のイメージ)。最初の要素の高さは全て $0$ である。このときある区間の高さに対して一様に $1$ 加減算、ある区間のある高さまたはある高さ以上にある要素の和を求めるクエリの処理を平方分割により $O(\sqrt N)$ で解く。

(ある高さにある要素の和だけを求めたい場合には $1$ 加減算に限定しなくても sum を unordered_map などでもつことによりギャグが可能)

空間計算量が破滅しがちなので、必要なところだけ領域を確保するように注意して実装している($O(Q)$ とかだと思う)。

計算量

• クエリ $O(\sqrt N)$

実装例

• SqrtDecomposition($N$, $L=0$):= テンプレートの $T$ は値の型、$E$ は高さの型。要素数 $N$ の列で初期化する。初期の高さと値は全て $0$ である。$L$ は query_low を投げるときに指定する。
• set($k$, $x$):= 要素 $k$ に $x$ を格納する。
• add($a$, $b$):= 区間 $[a, b)$ に $1$ を加算する。
• sub($a$, $b$):= 区間 $[a, b)$ に $1$ を減算する。
• query($a$, $b$, $x$):= 区間 $[a, b)$ の高さ $x$ にある要素の和を求める。
• query_low($a$, $b$):= 区間 $[a, b)$ の高さ $L$ 以上にある要素の和を求める。
• build($add$, $dat$):= 列の高さが $add$、値が $dat$ で初期化する。$add$ が一様に高いけど変化が少ないみたいなときに使う(空間計算量はそのブロックでの高さの最大値-最小値になる)。

template< typename T, typename E = int >
struct SqrtDecomposition {

  vector< E > block_add, elem_add;
  vector< int > block_pos;
  vector< T > data, lsum;
  vector< vector< T > > sum;
  int N, B, K;
  E L;

  SqrtDecomposition(int N, E L = 0) : N(N), L(L) { // 区間のlow以上の和を求める
    B = (int) sqrt(N);
    K = (N + B - 1) / B;

    block_add.assign(K, 0);
    block_pos.resize(N);
    for(int k = 0; k < K; k++) {
      for(int i = k * B; i < min((k + 1) * B, N); i++) block_pos[i] = k;
    }
    elem_add.assign(N, 0);
    data.assign(N, 0);
    sum.assign(K, vector< T >(B, 0));
    lsum.assign(K, 0);
  }


  void build(const vector< E > &add, const vector< T > &dat) {
    assert(add.size() == elem_add.size());
    assert(dat.size() == data.size());
    elem_add = add;
    data = dat;
    for(int k = 0; k < K; k++) {
      E tap = elem_add[k * B];
      for(int i = k * B; i < min((k + 1) * B, N); i++) tap = min(tap, elem_add[i]);
      block_add[k] = tap;
      for(int i = k * B; i < min((k + 1) * B, N); i++) {
        elem_add[i] -= block_add[k];
        set(i, dat[i]);
      }
    }
  }

  inline void del(int k) {
    sum[block_pos[k]][elem_add[k]] -= data[k];
    if(block_add[block_pos[k]] + elem_add[k] >= L) lsum[block_pos[k]] -= data[k];
  }

  inline void set(int k) {
    while(sum[block_pos[k]].size() <= elem_add[k]) sum[block_pos[k]].push_back(0);
    sum[block_pos[k]][elem_add[k]] += data[k];
    if(block_add[block_pos[k]] + elem_add[k] >= L) lsum[block_pos[k]] += data[k];
  }

  void set(int k, T x) {
    data[k] = x;
    set(k);
  }

  void add(int a, int b) {
    for(int k = 0; k < K; k++) {
      int l = k * B;
      int r = min(l + B, N);

      if(r <= a || b <= l) {

      } else if(a <= l && r <= b) {
        block_add[k]++;
        if(0 <= L - block_add[k] && L - block_add[k] < sum[k].size()) {
          lsum[k] += sum[k][L - block_add[k]];
        }
      } else {
        for(int i = max(a, l); i < min(b, r); i++) {
          del(i);
          elem_add[i]++;
          set(i);
        }
      }
    }
  }


  void sub(int a, int b) {
    for(int k = 0; k < K; k++) {
      int l = k * B;
      int r = min(l + B, N);

      if(r <= a || b <= l) {

      } else if(a <= l && r <= b) {
        if(0 <= L - block_add[k] && L - block_add[k] < sum[k].size()) {
          lsum[k] -= sum[k][L - block_add[k]];
        }
        block_add[k]--;
      } else {
        if(0 <= L - block_add[k] && L - block_add[k] < sum[k].size()) {
          lsum[k] -= sum[k][L - block_add[k]];
        }
        block_add[k]--;
        for(int i = l; i < max(a, l); i++) {
          del(i);
          elem_add[i]++;
          set(i);
        }
        for(int i = min(b, r); i < r; i++) {
          del(i);
          elem_add[i]++;
          set(i);
        }
      }
    }
  }


  T query(int a, int b, E x) {
    T ret = 0;
    for(int k = 0; k < K; k++) {
      int l = k * B;
      int r = min(l + B, N);

      if(r <= a || b <= l) {

      } else if(a <= l && r <= b) {
        if(0 <= x - block_add[k] && x - block_add[k] < sum[k].size()) {
          ret += sum[k][x - block_add[k]];
        }
      } else {
        for(int i = max(a, l); i < min(b, r); i++) {
          if(block_add[k] + elem_add[i] == x) ret += data[i];
        }
      }
    }
    return ret;
  }


  T query_low(int a, int b) {
    T ret = 0;
    for(int k = 0; k < K; k++) {
      int l = k * B;
      int r = min(l + B, N);

      if(r <= a || b <= l) {

      } else if(a <= l && r <= b) {
        ret += lsum[k];
      } else {
        for(int i = max(a, l); i < min(b, r); i++) {
          if(block_add[k] + elem_add[i] >= L) ret += data[i];
        }
      }
    }
    return ret;
  }
};

検証

AtCoder 早稲田大学プログラミングコンテスト2019 D - Choose Your Characters

int main() {
  int N, M;
  vector< int > g[100000];
  cin >> N >> M;
  for(int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    g[b].emplace_back(a);
  }
  for(int i = 0; i < N; i++) {
    g[i].emplace_back(i);
  }
  int in[100000] = {};
  int ok = 0;
  SqrtDecomposition< int > tap(N, 1);
  for(int i = 0; i < N; i++) tap.set(i, 1);
  int ptr = 0, ret = inf, l;
  for(int i = 0; i < N; i++) {
    while(ptr < N && tap.query_low(0, N) < N) {
      tap.add(0, N);
      for(auto &to : g[ptr]) tap.sub(to, to + 1);
      ++ptr;
    }
    if(tap.query_low(0, N) == N) {
      if(ptr - i < ret) {
        ret = ptr - i;
        l = i;
      }
    }
    tap.sub(0, N);
    for(auto &to : g[i]) tap.add(to, to + 1);
  }
  if(ret == inf) cout << -1 << endl;
  else cout << l + 1 << " " << l + 1 + ret - 1 << endl;
}