题解：P9292 [ROI 2018] Robomarathon

ltl0825 · 2025-10-28 19:49:06 · 题解

题目传送门\ 更好的阅读体验

题目大意：

有 N 名机器人选手参加马拉松，选手编号为 1 \dots N，分道编号也为 1 \dots N。选手 i 占据分道 i，跑完全程需要 a_i 秒。

设 S \subseteq \{1, 2, \dots, N\} 表示初始发炮的分道集合。
选手 i 的起跑时刻为： x_i = \min_{j \in S} |i - j|
选手 i 的冲线时间为： f_i = a_i + x_i

当 p=1 时：对于每个选手 i，求它的最好排名（最小）\ 当 p=2 时：对于每个选手 i，求它的最坏排名（最大）

题目思路：

对于 $p=1$ 很好考虑：直接在当前位置放一个，别的地方都不放，这对于当前的 $i$ 是最优的。\ 对于 $i$ 来说，排名在其前的满足 $a_j+ \left |i-j \right | < a_i$。\ 当 $j<i$ 时：$a_j+i-j<a_i$ 即 $a_j-j<a_i-i$。我们将 $a_i-i$ 当作一个数丢入树状数组，每次从左到右扫一遍，对于当前的就查询 $a_i-i-1$ 的前缀。\ 当 $j>i$ 时：$a_j-i+j<a_i$ 即 $a_j+j<a_i+i$。我们将 $a_i+i$ 当作一个数丢入树状数组，每次从右到左扫一遍，对于当前的就查询 $a_i+i-1$ 的前缀。\ 将两次操作的和 $+1$ 输出即可。
我们考虑先将所有跑道放上喇叭。假设 $i \le \left \lfloor \frac{n}{2} \right \rfloor $。\ 对于当前位置 $i$，我删去它的喇叭肯定会使 $i$ 的排名不增，那我肯定删去它。\ 若我同时在删去 $i+1$ 和 $i-1$。那么 $i$ 的 $x_i =2$，$i-1$ 和 $i+1$ 的 $x_i=1$ 别的 $x_i$ 都是 $0$，肯定会使 $i$ 的排名不增，那我肯定删去它。\ 重复这个流程，知道左边剩下一个 $1$ 右边是 $2\times i -1 \sim n$，这时不能再这样了，因为 $1$ 删了就会导致 $1\sim i-1$ 的发令喇叭变成 $2\times i-1$ 不优。\ 当然，我们还可以只放在 $n$ 这个位置，这也是优的。\ 所以，有两种：一种是放在 $1$ 和 $2\times i -1 \sim n$ 另一种是放在 $n$。\ 对于右半部分，即 $i>\left \lfloor \frac{n}{2} \right \rfloor$ 同理，可以自己试着推一下。\ # 代码（详细注释，细节提醒） ```cpp #include<bits/stdc++.h> #define int long long #define OUT(x) cout<<"LINE: "<<__LINE__<<" INFO: "<<x<<'\n'; using namespace std; int n,p; int a[400010]; int tree[1600010]; int lowbit(int x) { return x&-x; } void add(int x,int v) { for(;x<=800000;x+=lowbit(x)) { tree[x]+=v; } } int ask(int x) { int ans=0; for(;x;x-=lowbit(x)) { ans+=tree[x]; } return ans; } int b[400010]; int c[400010];//ai+i int d[400010];//ai-i int ans[400010]; int ans1[400010]; struct node{ int pos,val,op,q,add; }kk[850010]; int e[800010]; int f[400010]; int g[400010]; void solve(int op) { if(op == 0) { int k=n/2; memset(tree,0,sizeof(tree)); /* [1,i-1]的统计：满足fj<fi的j的数量 a[j]+i-j<a[i] a[j]-j<a[i]-i */ for(int i=1;i<=k;i++) { ans1[i]+=ask(c[i]-1); add(c[i],1); } memset(tree,0,sizeof(tree)); int ll=0; /* 这里是统计[i,2*i-1]：满足fj<fi的j的数量我们发现，对于一个 i+1<=j<=2*i-1 它要满足：a[j]+2*i-1-j<=a[i]+i-1 a[j]-j<=a[i]-i 所以我们需要知道，在[i,2*i-1]这个区间中，满足a[j]-j<=a[i]-i的j的数量那么我们将每个i的这种询问拆成两个询问：[1,2*i-1]满足a[j]-j<=a[i]-i的j的数量-[1,i-1]满足a[j]-j<=a[i]-i的j的数量，类似前缀查询这样就可以把这些询问记下来，按坐标排序，依次查询。我们还要把每个点加入进去，也就也是在i位置加入a[i]-i node成员的意义： pos:查询或加入的时间。 val：查询或加入的值 op：查询对对应i的贡献（i-1是-1，2*i-1是1，这样加一下就可以达到区间查询） q：查询对应哪个i add：当前是加入还是查询 */ for(int i=k;i>=1;i--) { kk[++ll]={i-1,d[i]-1,-1,i,0};//拆询问 kk[++ll]={2*i-1,d[i]-1,1,i,0}; } for(int i=1;i<=2*k-1;i++) { kk[++ll]={i,d[i],1,1,1};//每个点要加入 } sort(kk+1,kk+ll+1,[](node x,node y){return x.pos==y.pos?x.add>y.add:x.pos<y.pos;});//排序，注意，当时间相同时，这里是先加入，在查询 for(int i=1;i<=ll;i++) { if(kk[i].add)//加入 { add(kk[i].val,1); continue; } ans1[kk[i].q]+=kk[i].op*ask(kk[i].val);//查询 } /* [2*i,n]：满足fj<fi的j的数量 j要满足：f[j]<f[i]+i-1 所以要将a[i]与a[i]+i-1离散化这里需要小心一些（细节多）。我们从 floor(n/2) ~ 1枚举当i%2 == 0时：我们每次加入a[i*2]和a[i*2+1]，其中i=n/2时只能加入a[i*2] 当i%2 != 0时：我们每次加入a[i*2]和a[i*2+1] 每次查询a[i]+i-1的前缀 */ ll=0; memset(tree,0,sizeof(tree)); int len1=0; //离散化 for(int i=1;i<=n;i++) { e[++len1]=a[i]; e[++len1]=a[i]+i-1; } sort(e+1,e+1+len1); len1=unique(e+1,e+1+len1)-e-1; for(int i=1;i<=n;i++) { f[i]=lower_bound(e+1,e+1+len1,a[i])-e; g[i]=lower_bound(e+1,e+1+len1,a[i]+i-1)-e; } if(k*2 == n)//进行操作 { for(int i=k;i>=1;i--) { if(i == k) { add(f[i*2],1); } else { add(f[i*2],1); add(f[i*2+1],1); } ans1[i]+=ask(g[i]-1); } } else { for(int i=k;i>=1;i--) { add(f[i*2],1); add(f[i*2+1],1); ans1[i]+=ask(g[i]-1); } } } else//右边同理，我就不说了 { int k=n/2+1; memset(tree,0,sizeof(tree)); for(int i=n;i>=k;i--) { ans1[i]+=ask(d[i]-1); add(d[i],1); } memset(tree,0,sizeof(tree)); int ll=0; for(int i=k*2-n;i<=n;i++) { kk[++ll]={i,c[i],1,1,1}; } for(int i=k;i<=n;i++) { kk[++ll]={2*i-n-1,c[i]-1,-1,i,0}; kk[++ll]={i,c[i]-1,1,i,0}; } sort(kk+1,kk+ll+1,[](node x,node y){return x.pos==y.pos?x.add>y.add:x.pos<y.pos;}); for(int i=1;i<=ll;i++) { if(kk[i].add) { add(kk[i].val,1); continue; } ans1[kk[i].q]+=kk[i].op*ask(kk[i].val); } ll=0; memset(tree,0,sizeof(tree)); int len1=0; for(int i=1;i<=n;i++) { e[++len1]=a[i]; e[++len1]=a[i]+n-i; } sort(e+1,e+1+len1); len1=unique(e+1,e+1+len1)-e-1; for(int i=1;i<=n;i++) { f[i]=lower_bound(e+1,e+1+len1,a[i])-e; g[i]=lower_bound(e+1,e+1+len1,a[i]+n-i)-e; } if(k*2-n-1 == 1) { for(int i=k;i<=n;i++) { if(i == k) { add(f[2*i-n-1],1); } else { add(f[i*2-n-1],1); add(f[i*2-n-2],1); } ans1[i]+=ask(g[i]-1); } } else { for(int i=k;i<=n;i++) { if(i == k) { continue; } add(f[i*2-n-1],1); add(f[i*2-n-2],1); ans1[i]+=ask(g[i]-1); } } } } signed main() { ios::sync_with_stdio(0); cin.tie(0); cin>>n>>p; for(int i=1;i<=n;i++) { cin>>a[i]; b[i]=a[i]+i; } //离散化 sort(b+1,b+1+n); int len=unique(b+1,b+1+n)-b-1; for(int i=1;i<=n;i++) { c[i]=lower_bound(b+1,b+1+len,a[i]+i)-b; } for(int i=1;i<=n;i++) { b[i]=a[i]-i; } sort(b+1,b+1+n); len=unique(b+1,b+1+n)-b-1; for(int i=1;i<=n;i++) { d[i]=lower_bound(b+1,b+1+len,a[i]-i)-b; } if(p == 1) { for(int i=n;i>=1;i--)//右->左 { ans[i]=ask(c[i]-1); add(c[i],1); } memset(tree,0,sizeof(tree)); for(int i=1;i<=n;i++)//左->右 { ans[i]+=ask(d[i]-1); add(d[i],1); } for(int i=1;i<=n;i++) { cout<<ans[i]+1<<'\n';//不要忘了+1 } //a[j]+i-j<a[i] -> a[j]-j<a[i]-i //a[j]+j-i<a[i] -> a[j]+j<a[i]+i } if(p == 2) { for(int i=1;i<=n;i++)//左半部分，放在n的位置 { add(d[i],1); } for(int i=1;i<=n/2;i++) { ans[i]=ask(d[i]-1); } memset(tree,0,sizeof(tree)); for(int i=1;i<=n;i++)//右半部分，放在1的位置 { add(c[i],1); } for(int i=n/2+1;i<=n;i++) { ans[i]=ask(c[i]-1); } solve(0);//左半部分 solve(1);//右半部分 for(int i=1;i<=n;i++) { cout<<max(ans[i],ans1[i])+1<<'\n';//不要忘了+1，取的是max } } return 0; } ```