题解：P11118 [ROI 2024 Day 2] 无人机比赛
_maojun_
·
·
题解
做一些处理。
记 a_{i,j} 表示第 i 个无人机从第 j-1 个门到第 j 个门的耗时。
这个问题的模型实际上是对这 n 个数组 a_i 的一个顺序归并。一个经典的观察是，如果存在一个段 [l,r]，满足 \forall l<i\le r,a_{p,i}\le a_{p,l}，那么一旦 (p,l) 被删除，(p,l+1),\dots,(p,r) 都会被一并删除，也就是这些点是绑定的。这样极长地划分可以把一行划分成若干个段。
记 d_i=s_i-s_{i-1},S=s_m，则有 \sum d_i=S\le 1.5\times10^5。
注意到 a_{i,j}=t_id_j，同行 a 的大小关系之和 d 有关，所以实际上每行的段都是一样的，等于在 d 中划分出来的段。
根据上诉的限制，段之间满足开头元素递增，即 d_{l_1}<d_{l_2}<\dots<d_{l_m'}，则，有 m'\le O(\sqrt S)。
记 w'_{i,j} 表示第 i 个人通过第 j 段的耗时，则有 w'_{i,j}=t_id_{l_j}，同行 w' 单增。
先考虑怎么计算全局的答案。
形式化地：$\mathrm{ans}=\sum\limits_{i=1}^n\sum\limits_{j\ne i}\sum\limits_{k=1}^{m'}[w'_{j,k}\le w'_{i,m'}]l_k$，其中 $l_k$ 为第 $k$ 段的长度。
可以不钦定 $j\ne i$，最后减去 $j=i$ 的答案，即 $nm$。
由于 $k$ 范围较小，考虑固定 $i,k$ 计数：$[w'_{j,k}\le w'_{i,m'}]\Leftrightarrow t_j\le\dfrac{t_id_{m'}}{d_k}$，相当于提出一个对 $t_j$ 的限制 $t_j\le R_{i,k}$。
如果固定 $k$，把 $i$ 按 $t$ 从小到大枚举，这个边界是单调的，可以双指针扫一遍做到 $O(n\sqrt S)$。
---
对所有前缀的查询，相当于增加 $i,j\le x$ 的限制。
考虑计算 $\mathrm{ans}_x-\mathrm{ans}_{x-1}$，即 $i=x,j<x$ 的答案，以及 $i\le x,j=x$ 的答案。
- $i=x,j<x$：$\sum\limits_{j<x}\sum\limits_k[t_j\le R_{x,k}]l_k$。
枚举 $k$，查询 $R_{x,k}$ 的前缀和 $S$，把 $Sl_k$ 贡献到答案，然后给 $t_x$ 单点加一。
$O(n)$ 次单点修改，$O(n\sqrt S)$ 次前缀查询，可以根号平衡。
- $i\le x,j=x$：$\sum\limits_{i\le x}\sum\limits_k[t_x\le R_{i,k}]l_k$。
枚举 $k$，给 $R_{x,k}$ 单点加 $l_k$。查询 $t_x$ 的后缀和，贡献到答案。
$O(n\sqrt S)$ 次单点修改，$O(n)$ 次后缀查询，也可以根号平衡。
最后复杂度做到 $O(n(\sqrt n+\sqrt S))$。
```cpp
const int N=1.5e5+5;
int n,m,tt=0,s[N],t[N],ln[N];
int id[N],rk[N];
typedef long long ll;
int lm[N][550];ll as[N];
const int B=400;
int I[N],L[N],R[N];
int s1[N],s2[N];ll s3[N],s4[N];
inline void U1(int p){
for(int i=p;i<=R[I[p]];i++)s1[i]++;
for(int i=I[p];i<=I[n];i++)s2[i]++;
}
inline int Q1(int p){return s2[I[p]-1]+s1[p];}
inline void U2(int p,int k){s3[p]+=k;s4[I[p]]+=k;}
inline ll Q2(int p){
ll x=0;
for(int i=I[p]+1;i<=I[n];i++)x+=s4[i];
for(int i=p;i<=R[I[p]];i++)x+=s3[i];
return x;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&t[i]);
iota(id+1,id+n+1,1);
stable_sort(id+1,id+n+1,[&](int x,int y){return t[x]<t[y];});
for(int i=1;i<=n;i++)rk[id[i]]=i;
for(int i=1;i<=m;i++)scanf("%d",&s[i]);
for(int i=m;i>=2;i--)s[i]-=s[i-1];
for(int i=1,j;i<=m;i=j+1){
for(j=i;j<m&&s[j+1]<=s[i];j++);
ln[++tt]=j-i+1;s[tt]=s[i];
}
for(int j=1;j<=tt;j++)for(int i=1,p=0;i<=n;i++){
while(p<n&&make_pair((ll)t[id[p+1]]*s[j],id[p+1])<=make_pair((ll)t[id[i]]*s[tt],id[i]))p++;
lm[id[i]][j]=p;
}
for(int i=1;i<=n;i++)I[i]=(i-1)/B+1;
for(int i=1;i<=I[n];i++){L[i]=R[i-1]+1;R[i]=R[i-1]+B;}R[I[n]]=n;
for(int i=1;i<=n;i++){
for(int k=1;k<=tt;k++)U2(lm[i][k],ln[k]);
as[i]=Q2(rk[i]);
for(int k=1;k<=tt;k++)as[i]+=(ll)Q1(lm[i][k])*ln[k];
U1(rk[i]);
}
for(int i=1;i<=n;i++)printf("%lld\n",as[i]+=as[i-1]-m);
return 0;
}
```