题解 ABC282F 【Union of Two Sets】

· · 题解

（看了官方题解，出题人确实是根据 ST 表的原理出了这样一道题）

回顾下 ST 表的原理：我们利用倍增预处理出以 i 位置为左端点，包含 2^j 个元素的区间的最值。对于 [l, r] 区间最值的询问，我们适当选取 k，把其拆分为 [l, l + 2^k - 1]，[r - 2^k + 1, r] 两个区间的最值，使得两个区间的并为原询问区间，直接合并两个区间的答案。

整个过程恰好与本题的任务相对应！只不过，在这个问题中，我们不需要查询最值，只需要在构建 ST 表的过程中给相应区间标号，并在询问时输出拆分后的两个查询区间编号即可。

// Problem: F - Union of Two Sets
// Contest: AtCoder - HHKB Programming Contest 2022 Winter
// (AtCoder Beginner Contest 282)
// URL: https://atcoder.jp/contests/abc282/tasks/abc282_f
// Author : StudyingFather
// Site : https://studyingfather.com
// Memory Limit: 1024 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <cmath>
#include <iostream>
using namespace std;
int f[4005][15];
int main() {
  ios::sync_with_stdio(false);
  int n, cnt = 0;
  cin >> n;
  // 按道理这里循环应该是先 j 后 i
  // 不过这里不进行任何实际求值，就完全无所谓了
  for (int i = 1; i <= n; i++)
    for (int j = 0; i + (1 << j) - 1 <= n; j++) f[i][j] = ++cnt;
  cout << cnt << endl;
  for (int i = 1; i <= n; i++)
    for (int j = 0; i + (1 << j) - 1 <= n; j++)
      cout << i << ' ' << i + (1 << j) - 1 << endl;
  int q;
  cin >> q;
  while (q--) {
    int l, r;
    cin >> l >> r;
    int k = log2(r - l + 1);
    cout << f[l][k] << ' ' << f[r - (1 << k) + 1][k] << endl;
  }
  return 0;
}