P9112 [IOI2009] Archery
unputdownable
·
·
题解
其实 IOI 自己的英文题解讲的还是很好的，当年国家队的解题报告也是英文题解的翻译。
如果想要数据可以去 IOI 官网下载。
首先这个结构非常的混沌，起始位置不同会小小的更改靶位上初始的人，使得你很难观察性质，只能直接模拟比赛。
所以这题应该分为两个部分：优化模拟的复杂度，以及尝试减少模拟的次数。
下面先讨论如何降低模拟一次比赛的复杂度。
定义 W 集合表示 1 和 (n+2) \cdots(2 \times n) 这 n 个人的集合。
可以发现再若干轮后局面会趋于循环。（看到 r 这么大想必也能猜出来吧）
然后可以得到一个具体的结论，就是经过至多 2n 轮后局面会变成 W 集合里的人各占一个靶位，其他人以一定顺序轮转（其中 1 一定会停在 1 号靶位）。
将他们看成白球，其他看成黑球。这样就有 $n-1$ 个白球，而且可以认为白球完全相同，因为证明这个结论不需要关心某个人的具体位置。
那么一个白球能向前移动当且仅当他在 $1$ 号靶位，或者他所在的靶位两个人都是白球（我们认为这时候有一个白球开始就被卡住了）。
当他移动到一个没有白球的位置时，我们就认为他会一直卡在那里（即使能替换也只是白球换白球，对颜色没有影响）。
直接考虑每个白球和他最后会被卡住的位置，那么上面那个结论就易证了。
--------
确定结构后，这引向一个自然的分类讨论：
1. 我是 $1$ 号选手，因为我必然在 $1$ 号靶位停下，所以从 $n$ 开始即可；
2. 我不在 $W$ 集合中，我最后一定在绕圈圈，那么我只要求出 $2n+1$ 和 $3n$ 中我什么时候到达 $1$ 号靶位就能反推出让我最后的位置；
3. 我在 $W$ 中并且不是 $1$，那么我一定会卡死在一个位置，目标就是求出那个位置。
两种情况得分别优化。
--------
先讨论在 $W$ 中并且不是 $1$ 的情况。我要求出我被卡死的位置。
沿用上面证明的思想，将比我菜的看成白球，我是灰球，剩下的是黑球~~当他不存在就好~~。
还是考虑去匹配最终卡死的位置。
因为灰球即使卡在一个位置也能通过白球继续往前走，我们不妨先将灰球看成黑球。
白球直接没有区别，可以对每个白球贪心匹配前面第一个没有被匹配的靶场（然后他就会被定死在那里）。这里要注意 $1$ 号靶场是不能被匹配的，因为 $1$ 号选手会占据这个靶场并击败所有人。
然后再考虑灰球，你发现对灰球也可以贪心匹配前面第一个没有被匹配的靶场。首先他不可能走的更远，其次如果他占据了现在某个白球的靶场，那个白球到这个靶场的时候就会把灰球往前推。
实现的时候建议从 $1$ 号开始，捡起所有白球，然后从 $n$ 向 $2$ 遍历，不断重复有白球就拿然后放下一个的过程，直到所有白球都找到位置。
他的复杂度是 $\Theta(n)$ 的。
--------
接下来讨论我不在 $W$ 集合中的情况。
不难发现我们只关注 $1$ 号靶场。
$1$ 号靶场的比赛可以理解为一个人是擂主，后面的人一直挑战。
我们可以对每个时刻 $t$ 维护一个**可能去挑战的人的集合 $A$**，即假设他们一直赢，在时刻 $t$ 及以前能到达靶场 $1$ 的人的集合。
不难发现**最终挑战擂主的人一定在 $A$ 中，并且一定是最强的那一个**。
这是因为最强的人一定能赢下与集合内其他人的比赛从而一定能去挑战擂主。
而挑战擂主的人一定只有一个。
$A$ 的维护方法就是在 $t$ 轮**开始前**把初始站在靶场 $t$ 的人塞进去。
当然，上去挑战必然有一个人会输，那么那个人会在第 $t$ 轮重新回到 $n$ 号靶场，要在第 $t+n$ 轮才能回到 $A$ 中，我们认为他初始站在 $t+n$ 号靶场就行了。
记得特判初始 $1$ 号靶场的两个人并维护擂主。
复杂度也是 $\Theta(n)$ 的。
--------
接下来讨论怎么优化模拟次数。
没有思路的时候可以优先打一个表：（这是第 $56$ 个点的答案，第一行是从每个位置开始最终会到哪里的表）。
你发现他明显分成了几个单调不降的段。
你再思考可以发现，如果将 $1$ 掉到 $n$ 看成 $1$ 再往前走一步走到 $0$，以此类推（即统计从将 $1$ 掉到 $n$ 的次数 $T$，并将最终到达的位置看成 $res-n \times T$），那么这个东西在整个序列上是单调不降的。
证明是简单的，还是像上面分 $3$ 类讨论（与上面情况一一对应）：
1. 显然。
2. 思考找空位的过程，初始位置越后面，找到的空位不会越往前。
3. 加入 $A$ 的时间更晚，被弹出 $A$ 的时间不会更早。
都很显然。
由于我们之前证明了 $r$ 可以一直减 $n$ 直至小于等于 $3n$，所以上面两个模拟出的结果（$res-n \times T$）都在 $-2n$ 到 $n$ 之间，也就是说不同的 $T$ 不会很多（事实上，最多只有 $3$ 种）。
直接对每个 $T$ 二分就能做到只需要 $\Theta(\log n)$ 次模拟。
总时间复杂度 $\Theta(n \log n)$。
--------
**Code：**
```c++
#include <bits/stdc++.h>
#define pii pair <int, int>
using namespace std;
inline int read(void) {
int x=0,sgn=1; char ch=getchar();
while(ch<48||57<ch) {if(ch==45)sgn=0;ch=getchar();}
while(47<ch&&ch<58) {x=x*10+ch-48; ch=getchar();}
return sgn? x:-x;
}
void write(int x) {
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
int n,N,r,lim,Ans,pos;
int a[400005];
int cnt[3],cntT[600005][3];
pii result[400005];
inline int color(int x) { return (a[x] > a[1] ? 2 : 0); }
int bumps; // 记录我从 1 号靶场掉下去多少次
inline void init(int x) {
cnt[0]=cnt[1]=cnt[2]=bumps=0;
for(int i=1; i<=lim; ++i) cntT[i][0]=cntT[i][1]=cntT[i][2]=0;
for(int i=1; i<x; ++i) {
++cntT[i][color(i<<1)];
++cntT[i][color(i<<1|1)];
}
++cntT[x][1]; ++cntT[x][color(x<<1)];
for(int i=x+1; i<=n; ++i) {
++cntT[i][color((i<<1)-1)];
++cntT[i][color(i<<1)];
}
}
inline void challenge(int t,int i,int&host) { if(i<host) swap(i,host); ++cntT[t][i]; bumps+=(i==1); }
inline int calc1(int x) {
init(x);
int host=0; // who keep 1
for(int k=0; k<=2; ++k) if(cntT[1][k]) { host=k; --cntT[1][k]; break; }
for(int i=1; i<=N; ++i) {
for(int k=0; k<=2; ++k) cnt[k]+=cntT[i][k];
if(cnt[0]) --cnt[0],challenge(i+n,0,host);
else if(cnt[1]) --cnt[1],challenge(i+n,1,host);
else --cnt[2],challenge(i+n,2,host);
}
for(int i=1; i<=n; ++i) {
for(int k=0; k<=2; ++k) cnt[k]+=cntT[i+N][k];
if(cnt[0]) --cnt[0],challenge(1,0,host);
else if(cnt[1]) return (bumps+=(i<=r)),(i-r+n-1)%n+1;
else --cnt[2],challenge(1,2,host);
}
}
inline int calc2(int x) {
init(x);
cnt[2]=cntT[1][2]; cntT[1][2]=0;
for(int i=n; i>=2; --i) {
cnt[2]+=cntT[i][2]; cntT[i][2]=0;
if(cnt[2]) ++cntT[i][2],--cnt[2];
}
for(int i=n; i>=2; --i) {
cnt[2]+=cntT[i][2]; cntT[i][2]=0;
if(cnt[2]) ++cntT[i][2],--cnt[2];
}
for(int i=x; i>=2; --i) if(!cntT[i][2]) return i;
++bumps;
for(int i=n; i>=x; --i) if(!cntT[i][2]) return i;
}
inline pii calc(int x) {
if(result[x].first) return result[x];
int res=( a[1]<=n+1 ? calc1(x) : calc2(x) );
return result[x]=make_pair(res,bumps);
}
inline void check(int l,int p) { // 倍增找出最远的
if(p>pos) return ;
int d=1;
for(; l+d<=n; d<<=1) if(calc(l+d).first==p) l+=d; else break;
for(; d; d>>=1) if(l+d<=n&&calc(l+d).first==p) l+=d;
Ans=l; pos=p;
}
signed main() {
n=read(); N=n<<1; lim=n*3;
r=read()%n;
for(int i=1; i<=N; ++i) a[i]=read();
if(a[1]==1) return write(n),puts(""),0;
pii L=calc(1),R=calc(n);
pos=L.first;
check(1,L.first);
for(int i=L.second-1,l,r; i>=R.second; --i) {
l=1; r=n;
while(l<r) {
int mid=(l+r)>>1;
if(calc(mid).second<=i) r=mid;
else l=mid+1;
}
check(l,calc(l).first);
}
write(Ans); puts("");
return 0;
}
```