自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:45:27，当前版本为作者最后更新于2023-03-07 14:47:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P9112 [IOI2009] Archery

通过样例提示或手玩几组小数据，我们发现有些选手一定的轮数后不再移动，而其它选手按从 $n$ 到 $1$ 的顺序环状移动。

• 考虑选手 $1$，他最终会在靶 $1$ 停下来。
• 考虑选手 $2n$，他最终会在某个非靶 $1$ 的位置停下来，因为他无法打败任何人，所以一旦进入某个非靶 $1$ 的位置，他就永远无法离开了。
• 考虑选手 $2n - 1$，他最终会在某个不是选手 $1$ 或选手 $2n$ 停下来的位置停下来，原因同理。

以此类推，可知不移动的选手为 $1$ 和 $n + 2\sim 2n$，而环状移动的选手为 $2\sim n + 1$。我们将 $n$ 个靶位按编号排成圆圈。

我们探究什么时候所有选手会有规律地移动。一个直观猜测是，等选手 $1$ 进入靶位 $1$ 后，选手 $n + 2\sim 2n$ 会在不超过 $n$ 轮后停在靶位 $2\sim n$。因此，至多 $2n$ 轮后整个局面会以 $n$ 为循环节循环。

$2n$ 轮的上界已经够用了，而且很好证明。作为补充解释，我们尝试证明一个更强的结论：

$n + 2\sim 2n$ 会在不超过 $n$ 轮后停在靶位 $2\sim n$。

证明：考虑某个靶位 $i$（$2\leq i\leq n$）且 $n$ 轮后没有 $n + 2\sim 2n$，那么 $i$ 从来没有被这样的选手经过，因为一旦经过就一直存在，无论留下的选手编号是什么。

在第一轮时，$i$ 左侧的靶位（靶位 $i - 1$）至多剩下一名 $n + 2\sim 2n$。

在第二轮时，$i$ 左侧的两个靶位总共至多剩下两名 $n + 2\sim 2n$。

特别地，在第 $i - 1$ 轮时，靶位 $1\sim i - 1$ 至多剩下 $i - 1$ 名 $n + 2\sim 2n$，且如果剩下 $i - 1$ 名，则靶位 $1$ 上至少有一名，此时我们再等一轮，第 $i$ 轮时，靶位 $1\sim i - 1$ 至多剩下 $i - 2$ 名 $n + 2\sim 2n$。

以此类推，可知第 $n$ 轮时，$i$ 左侧的 $n - 1$ 个靶位（也就是除了靶位 $i$ 本身的其它所有靶位）至多剩下 $n - 2$ 名 $n + 2\sim 2n$，但总共有 $n - 1$ 名 $n + 2\sim 2n$，这与靶位 $i$ 上没有 $n + 2\sim 2n$ 矛盾了。$\square$

这样，我们将 $R$ 替换为最小的 $R'\geq n$（或 $2n$）且 $R\equiv R'\pmod n$，答案不会改变。这给予我们 $\mathcal{O}(n ^ 3)$ 的模拟做法。

考虑优化单次 $\mathcal{O}(n ^ 2)$ 的模拟。我们观察到，若主角的技术水平为 $S_1$，则在模拟的过程中，所有 $> S_1$ 的选手是等价的，称为 $2$ 类选手；所有 $< S_1$ 的选手是等价的，称为 $0$ 类选手。并且，根据移动规则，类似上述证明，若有 $2$ 类选手进入靶位 $2\sim n$，则该靶位一直有 $2$ 类选手；若有 $1$ 类选手进入靶位 $1$，则该靶位一直有 $1$ 类选手。

因此，只要我们能够对于靶位 $2\sim n$ 求出第一次有 $2$ 类选手的时间 $t_2\sim t_n$，对于靶位 $1$ 求出第一次有 $1$ 类选手的时间 $t_1$，即可在任意时刻确定每个靶位上选手的类型，从而只维护主角的移动而不需要维护其它选手的移动。

$t_1$ 显然容易，考虑 $t_2\sim t_n$。设 $s_i$ 表示 $2$ 类选手数量关于靶位的前缀和。我们认为，如果两个 $2$ 类选手相遇，那么 初始位置靠后的选手获胜。这样，考虑最终移动到靶位 $i$ 上的选手初始靶位编号 $j$：

• 如果 $j$ 到 $i$ 不经过靶位 $1$，则 $j$ 移动到 $i$ 的充要条件是 $i\sim j$ 至少有 $j - i + 1$ 个 $2$ 类选手，即 $s_j - s_{i - 1} \geq j - (i - 1)$，且 恰好在第 $j - i + 1$ 轮到达靶位 $i$，每一步都向前移动 $1$。又因为每个靶位上至多有两个 $2$ 类选手，所以符合条件的最小的 $j$ 一定满足 $s_j - s_{i - 1} = j - (i - 1)$ 或 $j - (i - 1) + 1$。实际上，特判掉靶位 $i$ 本来就有 $2$ 类选手的情况之后，$s_j - s_{i - 1}$ 只能等于 $j - (i - 1)$。
• 如果 $j$ 到 $i$ 经过靶位 $1$，那么稍微复杂一些。首先，$j$ 移动到 $i$ 的充要条件是 $i\sim j$ 至少有 $j - i$ 个 $2$ 类选手，即 $s_j - s_{i - 1} \geq j - (i - 1) - 1$。类似地，除了靶位 $n$ 没有 $2$ 类选手，靶位 $1$ 有两个 $2$ 类选手的情况，$s_j - s_{i - 1}$ 只能等于 $j - (i - 1) - 1$。但是，$j$ 并不一定恰好在第 $j - i + 1$ 轮到达靶位 $i$：如果 $j$ 在到达靶位 $1$ 时，靶位 $1$ 有两个选手，那么 $j$ 会在这里停顿一下，使得 $j$ 在第 $j - i + 2$ 轮到达靶位 $i$。易知其充要条件为靶位 $1\sim j$ 初始全部有两个 $2$ 类选手。

求出 $t$ 之后，单次模拟的时间复杂度就可以做到 $\mathcal{O}(n)$。

因为超过一个 $2$ 类选手只能打败他，所以在靶位 $2\sim n$ 上，相较于靠前的起始位置，靠后的起始位置总要打败更多的 $2$ 类选手。而在靶位 $1$ 上，两个不同的起始位置可能等到相同的轮数才回到 $n$，但靠后的起始位置一定不会在靠前起始位置之前（更少的轮数）回到 $n$。因此，如果我们在线性的尺度下观察整个过程，设 $f_i$ 表示初始位置 $i$ 在线性尺度下的最终位置，即 $i$ 减去主角从 $i$ 出发经过 $R$ 轮的移动次数，那么对于 $i < j$，$f_i\leq f_j$。

因为 $R = \mathcal{O}(n)$，所以 $f_n - f_1 = \mathcal{O}(n)$。我们枚举 $[f_1, f_n)$ 的所有 $n$ 的倍数 $kn$，总共 $\mathcal{O}(1)$ 个，二分求出第一个 $i$ 使得 $f_i > kn$，则初始位置 $i$ 以及对应的最终位置才有可能更新答案。时间复杂度 $\mathcal{O}(n\log n)$。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
bool Mbe;
constexpr int N = 4e5 + 5;
int n, R, a[N], b[N];
pair<int, int> ans = {N, 0};
auto simulate(int p) {
  for(int i = 1; i < 2 * p; i++) a[i] = b[i + 1];
  a[2 * p] = b[1];
  for(int i = 2 * p + 1; i <= 2 * n; i++) a[i] = b[i];
  static int t[N], s[N], buc[N << 1];
  memset(s, 0, N << 2), memset(buc, 0x3f, N << 3);
  for(int i = 1; i <= 2 * n; i++) if(a[i] == 2) s[i + 1 >> 1]++;
  for(int i = 1; i <= n; i++) s[i + n] = s[i], t[i] = 1e9;
  for(int i = 1; i <= 2 * n; i++) s[i] += s[i - 1];
  for(int i = 0; i <= 2 * n; i++) s[i] += N - i;
  for(int i = n + 1; i > 1; i--) { // i 从 n + 1 开始，特判特殊情况
    if(s[i] >= s[i - 1]) t[i] = 1;
    else t[i] = buc[s[i - 1]] - i + 1;
    buc[s[i]] = i;
  }
  memset(buc, 0x3f, N << 3);
  for(int i = 2 * n; i > 1; i--) {
    if(i > n) buc[s[i]] = i;
    else {
      int p = buc[s[i - 1] - 1];
      if(p < N) t[i] = min(t[i], p - i + (s[p] - s[n] == p - n ? 2 : 1));
    }
  }
  int fir = 0, cur = 0, fin;
  for(int i = 1; i <= 2 * n; i++) {
    if(a[i] == 0 && !fir) fir = i + 1 >> 1;
    else if(a[i] == 1) fin = cur = i + 1 >> 1;
  }
  for(int _ = 1; _ <= R; _++) {
    if(cur == 1) {if(fir <= _) cur = n, fin--;}
    else if(t[cur] <= _) cur--, fin--;
  }
  ans = min(ans, {cur, -p});
  return make_pair(cur, fin);
}
bool Med;
int main() {
  fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
  #ifdef ALEX_WEI
    FILE* IN = freopen("1.in", "r", stdin); 
    FILE* OUT = freopen("1.out", "w", stdout);
  #endif
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> R, R = n + R % n;
  for(int i = 1; i <= 2 * n; i++) cin >> b[i];
  if(b[1] == 1) cout << n << "\n", exit(0);
  for(int i = 2; i <= 2 * n; i++) b[i] = b[i] < b[1] ? 0 : 2;
  b[1] = 1;
  auto fst = simulate(1), lst = simulate(n);
  for(int i = fst.second; i < lst.second; i++) {
    if(i != fst.second && (i % n + n) % n != 1) continue;
    int l = 1, r = n;
    while(l < r) {
      int m = l + r >> 1;
      auto dat = simulate(m);
      if(dat.second >= i) r = m;
      else l = m + 1;
    }
    int v = simulate(l).second;
    r = n;
    while(l < r) {
      int m = l + r + 2 >> 1;
      auto dat = simulate(m);
      if(dat.second <= v) l = m;
      else r = m - 1;
    }
    simulate(l);
  }
  cout << -ans.second << "\n";
  cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
  return 0;
}