CF1372F Omkar and Modes 题解

来个乱搞。

思路

考虑分治。

对于最裸的暴力。

我们可以调用 solve(l, r) 进行查询。

假如这个区间的众数的出现次数是区间长度，那么可以直接退出，否则我们可以继续分治。

我们把这个暴力进行加工一下。

我们知道 \(l\sim r\) 的区间众数后。

1. 查询 \(l\sim mid\) 的区间众数，若完全与 \(l\sim r\) 一样，那么可以继续分治下去。

2. 若仅有出现次数不一样，那么意味着我们已经知道了这个数的出现位置，可以直接构造答案，从两侧继续分治。

3. 若都不一样，我们再查询 \(mid\sim r\) 的区间众数，可以仿照第一条第二条继续构造。

感觉是一个比较粗糙的做法，但又好像比较难卡。

这个做法的上下界我也不会算，如果有人可以 Hack 也比较正常。

Code

#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second
// #define int long long
#define mp(x, y) make_pair(x, y)
#define eb(...) emplace_back(__VA_ARGS__)
#define fro(i, x, y) for(int i = (x); i <= (y); i++)
#define pre(i, x, y) for(int i = (x); i >= (y); i--)
inline void JYFILE19();

typedef long long i64;
typedef pair<int, int> PII;

bool ST;
const int N = 1e6 + 10;
const int mod = 998244353;

int n, m, a[N];
map<PII, PII> mp;

inline PII ask(int l, int r) {
  if(mp.count({l, r})) {
    return mp[{l, r}];
  }
  cout << "? " << l << " " << r << endl;
  int x, f;
  cin >> x >> f;
  return mp[{l, r}] = {x, f};
}
inline void solve(int l, int r) {
  if(l > r) return;
  int mid = (l + r) >> 1, x, f;
  tie(x, f) = ask(l, r);
  if(f == r - l + 1) {
    fro(i, l, r) a[i] = x;
    return;
  }
  int y, g, ls, rs;
  tie(y, g) = ask(l, mid);
  if(x == y && g != f) {
    ls = mid - g + 1, rs = ls + f - 1;
    fro(i, ls, rs) a[i] = x;
    solve(l, ls - 1);
    solve(rs + 1, r);
    return;
  }
  if(x == y) {
    solve(l, mid);
    solve(mid + 1, r);
    return;
  }
  tie(y, g) = ask(mid + 1, r);
  if(x == y && g != f) {
    rs = mid + g, ls = rs - f + 1;
    fro(i, ls, rs) a[i] = x;
    solve(l, ls - 1);
    solve(rs + 1, r);
    return;
  }
  solve(l, mid);
  solve(mid + 1, r);
  return;
}

signed main() {
  JYFILE19();
  cin >> n;
  solve(1, n);
  cout << "! ";
  fro(i, 1, n) {
    cout << a[i] << " ";
  }
  cout <<"\n";
  return 0;
}

bool ED;
inline void JYFILE19() {
  // freopen("", "r", stdin);
  // freopen("", "w", stdout);
  ios::sync_with_stdio(0), cin.tie(0);
  double MIB = fabs((&ED-&ST)/1048576.), LIM = 32;
  cerr << "MEMORY: " << MIB << endl, assert(MIB<=LIM);
}