P11118 [ROI 2024 Day 2] 无人机比赛 题解

Description

有 $n$ 架无人机参与比赛，第 $i$ 架无人机飞过一个单位距离需 $t_i$ 秒。

赛道为一条直线，上面有 $m$ 个存档点，第 $i$ 个存档点距起点 $s_i$ 个单位长度，保证 $s_{i+1}>s_i$。

一共有 $n$ 场比赛，第 $k$ 场比赛有前 $k$ 架无人机参加，比赛按如下方式进行。

定义一个阶段为当前还未完赛的所有无人机从其存档点开始飞行，直到有一架无人机到达了下一个存档点，我们称这架无人机为此阶段的赢家。若有多架无人机同时到达，则编号最小的为赢家。

该阶段结束后，所有非赢家的无人机将被传送回此阶段开始时其所在的存档点，而赢家则更新其存档点。若赢家此时到达了第 $m$ 个存档点，那么它将完赛，后面的阶段都不参加。

当所有无人机都完赛时，那么这场比赛就结束了。

你需要对于这 $n$ 场比赛中的每一场，分别求出比赛中所有无人机的传送次数之和。

Solution

依题意得一个阶段中只有赢家改变存档点，对非赢家造成传送，而非赢家之间的相对位置都不改变，不会互相造成传送。

于是总传送次数可以拆成两两之间所造成的贡献之和，并且这只与它们两有多少个阶段输赢不同有关，即对于 $i,j$，两机互相造成的贡献为 $i,j$ 中第一架无人机完赛时，已经经过了多少个阶段。

对于一架无人机 $i$，我们定义 $w_j=(s_j-s_{j-1})\times t_i$。

那么对于 $i,j$ 算贡献，可以通过归并 $i,j$ 的两个 $w$ 序列来求出。然而 $w$ 并不有序，但我们可以通过 UR #26 石子合并 中的结论，即对于同一序列的 $w$，若 $w_{i+1}\le w_i$ 那么 $w_{i+1}$ 会在 $w_i$ 弹出后紧接地弹出，在归并后的数组中相邻。

而同一组中的 $w$ 大小关系与 $t$ 无关，与 $s$ 的差分数组有关，所以可以对 $s$ 的差分数组进行操作，将会紧邻弹出的数合在一起，设其总共有 $k$ 个这样的段。每个段计 $a_i,b_i$，表示这一段段头的值以及这一段的长度。

因为 $a_i$ 是严格递增的，那么由于 $a_1+a_2+\cdots +a_k=s_m\le 1.5\times 10^5$，所以 $k$ 的大小是 $O(\sqrt{V})$ 的，$V$ 是 $1.5\times 10^5$ 级别的。

回到对 $i,j(i<j)$ 算贡献，发现比较好算了：

• $t_i\le t_j$，那么 $i$ 先完赛，先加上 $m$ 的贡献，即 $i$ 对 $j$ 造成的贡献。$j$ 对 $i$ 造成的贡献就是看在 $i$ 完赛时，$j$ 到了第几个存档点，也就是找到最大的 $x$ 使得 $a_k\times t_i>a_x\times t_j$，然后加上 $b_1+b_2+\cdots +b_x$ 的贡献。

• $t_i>t_j$，那么 $j$ 先完赛，同样先加上 $m$ 的贡献。然后找到最大的 $x$ 使得 $a_x\times t_i\le a_k\times t_j$，同样加上 $b_1+\cdots b_x$ 的贡献，注意是 小于等于，因为 $i<j$，所以当两人用时相等时赢家是 $i$。

找 $x$ 用二分，那么至此我们用 $O(n^2\log \sqrt{V})$ 的复杂度解决了问题，比暴力分多 $10$ 分，可喜可贺。

那么怎么继续优化呢？

考虑上扫描线，我们从小到大扫 $i$，对于每一个可能的 $x$，先二分找到 $j$ 的限制（两种情况），再对这两段区间加上 $b_x$，注意我们已经把贡献分成了 $m$ 和 $b_1+\cdots +b_x$。

计算答案就是扫到 $j$ 时，取出其在线段树内的值，然后加上 $\frac{j\times (j-1)}{2}\times m$ 的贡献。

注意线段树上维护的是 离散后的 $t$ 的值，二分也是找离散后的值，同时要 先算贡献再查值，不然若 $t_i=t_j$ 时会重复算贡献。

现在时间复杂度变为了 $O(n\sqrt{V}(\log n+\log n))$，前面的 $\log$ 是二分，后面的 $\log$ 是区间修改，单点查询的线段树。但这个复杂度跑不过去，需要进一步优化。

注意到区间修改有 $O(n\sqrt{V})$ 级别，而询问只有 $O(n)$ 级别，那么可以用区间修改 $O(1)$，单点查询 $O(\sqrt{n})$ 的分块来平衡复杂度，具体的，维护每个点和每个块的差分数组，修改时修改两个点和两个块的值，查询即查询差分数组的前缀和。

但二分的 $O(\log n)$ 还没去掉，观察到当 $x$ 相同时，$i$ 递增时，其对应 $j$ 的限制也递增，$i,j$ 是离散后 $t$ 数组的下标。那么可以预处理出 $ta{g}_{i,x}$，表示二分出来的限制，用双指针维护做到时间 $O(n\sqrt{V})$，空间 $O(n\sqrt{V})$。注意两种限制的双指针有所不同，细节较多。

这个题就用时间 $O(n(\sqrt{V}+\sqrt{n}))$，空间 $O(n\sqrt{V})$ 的复杂度做完了，吗？

实际上 $k$ 的极限并不是 $\sqrt{1.5\times 10^5}$，而是 $550$ 。所以开两个 $tag$ 会爆空间，不过只要先处理一种，算贡献，再处理另外一种，算贡献就可以了。

时间上有略微卡常，只需在求 $tag$ 时使访问较为连续即可，先枚 $i$，再枚 $x$。

还有一些细节具体见代码。

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,m,k,cnt,len;
int t[150010],s[150010],tt[150010],id[150010];
int tag[150010][560];
int st[150010],hd;
int a[560],b[560];
ll fin1[150010],fin2[560],ans[150010];
void init(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>t[i],tt[i]=t[i];}sort(tt+1,tt+1+n);cnt=unique(tt+1,tt+1+n)-tt-1;len=sqrt(cnt)+1;for(int i=1;i<=n;i++){t[i]=lower_bound(tt+1,tt+1+cnt,t[i])-tt;}for(int i=1;i<=cnt+1;i++){id[i]=(i-1)/len+1;}for(int i=1;i<=m;i++){cin>>s[i];}for(int i=m;i;i--){while(hd&&s[st[hd]]-s[st[hd]-1]<=s[i]-s[i-1]) hd--;st[++hd]=i;}st[0]=m+1;for(int i=hd;i;i--){a[++k]=s[st[i]]-s[st[i]-1];b[k]=st[i-1]-st[i];}
}
void update(int l,int r,ll v){  //O(1)更新fin1[l]+=v,fin1[r+1]-=v;fin2[id[l]]+=v,fin2[id[r+1]]-=v;
}
ll query(int x){  //O(sqrt(n)) 查询ll sum=0;for(int i=1;i<id[x];i++){sum+=fin2[i];}for(int i=(id[x]-1)*len+1;i<=x;i++){sum+=fin1[i];}return sum;
}
void pres1(){  //ti<=tjfor(int j=1;j<=cnt;j++){for(int i=1;i<=k;i++){int fl=tag[j-1][i];while(1){tag[j][i]=fl;if(fl+1>cnt||(ll)tt[j]*a[k]<=(ll)tt[fl+1]*a[i]) break;fl++;}}}
}
void pres2(){  //ti>tj，两个双指针细节多，一定要理解充分for(int j=1;j<=cnt;j++){for(int i=1;i<=k;i++){int fl=tag[j-1][i];while(1){if((ll)tt[j]*a[i]<=(ll)a[k]*tt[fl]){tag[j][i]=fl;break;}fl++;}}}
}
void solve(){pres1();for(int i=1;i<=n;i++){ans[i]=query(t[i]);for(int j=1;j<=k;j++){if(tag[t[i]][j]>=t[i]){update(t[i],tag[t[i]][j],b[j]);}}}pres2();for(int i=1;i<=cnt;i++) fin1[i]=0;  //记得清空分块for(int i=1;i<=id[cnt+1];i++) fin2[i]=0;for(int i=1;i<=n;i++){ans[i]+=ans[i-1]+query(t[i]);cout<<ans[i]+(ll)i*(i-1)/2*m<<'\n';for(int j=1;j<=k;j++){if(tag[t[i]][j]<t[i]){update(tag[t[i]][j],t[i]-1,b[j]);}}}
}
int main(){ios::sync_with_stdio(0);cin.tie(nullptr);init();solve();return 0;
}