题解：CF1879F Last Man Standing
yshpdyt
·
·
题解
题意
有点抽象。
使用一下 RockyYue 概括的，感觉很简洁。
对于每个人，选择适当的 $x$，求其最大的分数。
## Sol
鲜花：一个点跑 $7$ 秒，总共 $43$ 个点，交一次乐观来看测两分钟，~~网差半天不出结果~~，卡常大半天人已经疯了。
不难发现一条命被攻击 $\left\lceil \frac{a_i}{x} \right\rceil$ 次后就会换到下一条命，所以总的存活回合是 $h_i\left\lceil \frac{a_i}{x} \right\rceil$ 。
对于最暴力的做法，枚举所有 $x$，再枚举所有位置，计算出每个人活到的最大回合，然后用最大值减去次大值，就是活到最后的人能获得的积分，最后每个人对可能的积分取最大值。
现在考虑优化，尝试从 $h_i$，$x$，$a_i$ 分别下手。
对于 $x$，虽然题目中没有给上限，但是 $x$ 如果比所有怪物的血量都高，砍谁都是一刀秒，答案就只剩下 $h_i$ 了，这种情况只需要算一次，所以可以规定 $x\in[1,\max\limits_{i=1}^n a_i]$，为了后续方便表达，设 $m=\max\limits_{i=1}^n a_i$。
对于 $a_i$，因为是向上取整，所以当 $x$ 充分大时不会有特别多个 $\left\lceil \frac{a_i}{x} \right\rceil$ 的值不同。可以直接枚举 $x$ 以及 $\left\lceil \frac{a_i}{x} \right\rceil$ 可能的取值，复杂度为调和级数，比较可行，接着令固定 $x$ 不变，考虑里面的枚举。
由于进行了枚举，我们考虑尽可能把相同的值放到一块进行一起计算，对 $a_i$ 进行排序就可以做到。我们只需要套一个二分就能找到 $\left\lceil \frac{a_i}{x} \right\rceil=j$ 的区间左右端点，事实上，只需要二分右端点，左端点可以从上次二分继承。
然后对于相同的值的连续一段区间，区间中的差异只有 $h_i$ 。则对于这一段区间，最大值和次大值就是 $h_i$ 的最大值和次大值。
那么剩下的就是维护 $h_i$ 了，维护最大值和次大值以及最大值的位置，可以考虑线段树，但是这玩意每次查询 $O(\log)$ ，本题需要频繁查询，很容易被卡，换用查询 $O(1)$ 的 st 表。
看了其他几篇题解，感觉把 st 表维护次大值写的有点麻烦了，事实上，我们只需要找到区间 $[l,r]$ 最大值的位置 $i$，然后再在 $[l,i-1]$ 和 $[i+1,r]$ 再次查询最大值，两个区间取最大就是次大值了。这样我们仅需要维护区间最大值即可。
对于一个 $x$，维护一个 $fmx$，$pos$，$smx$，分别代表 伤害为 $x$ 时积分最大值，最大值位置，次大值，$res_i$ 表示 $i$ 位置可能的积分的最大值：
$$fmx=\max\limits_{j=1}^{j\times x\le m} \left(j\times \max\limits_{k=l}^r h_k\right)$$
$$res_{pos}=\max\limits(res_{pos},fmx-smx)$$
次大值计算同理。
时间复杂度 $O(Tn \log^2 n)$。
这道题比较卡常，并且需要开 ` long long` ，提供一份超级快读：
```cpp
namespace MYINPUT{
const int S=(1<<20)+5;char B[S],*H=B,*T=B;
inline char gc(){if(H==T) T=(H=B)+fread(B,1,S,stdin);return H==T?EOF:*H++;}
inline int fr(){int x=0;bool fh=0;char ch=gc();while(ch<'0'||ch>'9'){if(ch=='-') fh=1;ch=gc();}while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=gc();}return fh?-x:x;}
}using MYINPUT::fr;
```
## Code
```cpp
#include<bits/stdc++.h>
#define ll long long
#define N 300005
#define endl "\n"
#define fi first
#define se second
using namespace std;
const int mod=1e9+7;
const int inf=1e18;
const double eps=1e-6;
namespace MYINPUT{
const int S=(1<<20)+5;char B[S],*H=B,*T=B;
inline char gc(){if(H==T) T=(H=B)+fread(B,1,S,stdin);return H==T?EOF:*H++;}
inline int fr(){int x=0;bool fh=0;char ch=gc();while(ch<'0'||ch>'9'){if(ch=='-') fh=1;ch=gc();}while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=gc();}return fh?-x:x;}
}using MYINPUT::fr;
struct node{
int h,p,id;
friend bool operator<(const node &a,const node &b){
return a.p<b.p;
}
}a[N];
int n,b[N];
ll res[N];
ll f[25][N];
int lg[N],g[25][N];
inline void work(){
for(int i=1;i<=lg[n];i++){
for(int j=1;j+(1<<i)-1<=n;j++){
f[i][j]=max(f[i-1][j],f[i-1][(1<<(i-1))+j]);
if(f[i][j]==f[i-1][j])g[i][j]=g[i-1][j];
else g[i][j]=g[i-1][(1<<(i-1))+j];
}
}
}
inline pair<ll,ll> qr(ll l,ll r) {
ll len=r-l+1;
ll t=max(f[lg[len]][l],f[lg[len]][r-(1<<lg[len])+1]);
ll p=g[lg[len]][l];
if(t==f[lg[len]][r-(1<<lg[len])+1])p=g[lg[len]][r-(1<<lg[len])+1];
return {t,p};
}
ll mxpos=0,mxval=0,sxval=0;;
inline void calc(ll i,ll l,ll r){
ll k=(b[l]-1)/i+1;
auto t=qr(l,r);
pair<ll,ll> t1={0,0},t2={0,0};
if(t.se>l)t1=qr(l,t.se-1);
if(t.se<r)t2=qr(t.se+1,r);
t1=max(t1,t2);
if(t.fi*k>mxval){
sxval=mxval;
mxval=t.fi*k;
mxpos=a[t.se].id;
if(t1.fi*k>sxval)sxval=t1.fi*k;
return ;
}
if(t.fi*k>sxval)sxval=t.fi*k;
if(t1.fi*k>sxval)sxval=t1.fi*k;
}
inline void sol(){
n=fr();
for(int i=1;i<=n;i++){
a[i].h=fr();
a[i].id=i;
}
for(int i=1;i<=n;i++)a[i].p=fr();
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
b[i]=a[i].p;
f[0][i]=a[i].h;
g[0][i]=i;
}
work();
for(int i=1;i<=a[n].p;i++){
ll l=0,r=1;
mxpos=0,mxval=0,sxval=0;
for(ll j=0;j*i<=a[n].p&&r<=n;j++){
r=upper_bound(b+1,b+n+1,i*j)-(b);
if(l==r)continue;
calc(i,l,r-1);
l=r;
}
if(r<=n)calc(i,r,n);
res[mxpos]=max(res[mxpos],mxval-sxval);
}
for(int i=1;i<=n;i++){
cout<<res[i]<<" ";
res[i]=0;
}
cout<<endl;
}
int main(){
lg[1]=0;
for(int i=2;i<=N-5;i++)lg[i]=lg[i/2]+1;
int ttt=fr();
while(ttt--)sol();
return 0;
}
```