SS241030B. 世界(world)
题意
在一个 \(n\) 列的竖着的二维世界里。每列有一个高度为 \(a_i\) 的石柱。你从 \((1,a_1)\) 的石头上面出发。每次可以往左或右边走一步（前提是左边或右边没有石头）、或者挖掉左边或者右边的石头、或者挖掉自己脚底下的石头。
挖掉一个石头会使得它上面的所有石头一起消失。
你有 \(k\) 的血量，如果脚下没有踩着石头，你就会掉下去，掉下 \(h\) 个单位会受到 \(h^2\) 的伤害（注意挖自己脚下也会掉下去）。
问最少操作多少次，使得血量非负，对于每个 \(1\le i \le n\)，到达 \((i,0)\) 上面。
solution
想 + 写 + 调花了 3h+，先冲完 t2 正解再写 t3、t4 暴力，这是赌博。赌博是有很大风险的。不能再赌了，虽然赢了的结果极具诱惑性，如 CSP-S2023，但是如果输了就会像 GDOI2024 一般惨烈。建议下次先写后面的暴力。
赛事做法太恶心了，现在整理一下。
省流：设 \(f_i\) 表示不走回头路走到 \((i,0)\) 的最小次数，\(ans_i=\min(f_i,f_{j,j>i}+2(j-i))\)。设 \(g_j=f_j+2j\)，变成求 \(ans_i=\min_{j\ge i}\{g_j\}-2i\)。求 \(f_i\) 使用简单贪心 + 二分 + 想象出式子。时间复杂度 \(O(n \log k)\)。
显然你不会往上走只会往下掉。
可以感觉到要走到 \((i,0)\)，你会尽量在石柱的顶部走，可能你走到第 \(i\) 列就一直往下挖，也可能走到第 \(i\) 列之后你继续往右边走（因为可以多掉几次，减少挖石头的代价），然后再掉头回来，此时你左侧的石柱全部比你高（否则你之前就会掉到石柱的高度），因此你需要挖一次走一次。
把每个前缀最小值的列称为关键列。对与非关键列你一定要先挖才能走过去，而对于关键列，你一定会先往下挖几格然后直接跳下去，你挖的石头数量不会超过两个柱子的高度差。
对于不走回头路的一类，你的方案一定是往下挖和跳关键列，往右挖和走非关键列。走到 \(\le i\) 的最靠后的关键列时一直下挖到低，然后边挖边走到 \((i,0)\)。
赛后才发现一定会走到最右边的关键列才下挖，一定不劣。
对于走回头路的一类，我们枚举关键列 \(j\)，先走到 \(j\) 的顶部然后往下挖到底，然后左挖一下，左走一下，走到 \((i,0)\)。
可以证明这样是最优的。
于是对于每个关键列 \(i\)，可以设 \(f_i\) 表示走到 \((i,0)\) 的最小次数。
第一种情况就直接是最右边的关键列 \(f_j\) 加上 \(2(i-j)\)。
第二种情况就枚举 \(j\ge i\)，算 \(f_j+2(j-i)\)。
发现 \(f_j-2(j-i)=f_j-2j+2i\)，于是直接把 \(2j\) 揉进 \(f_j\) 里面，变成求 \((\min_{j\ge i} f_j)+2i\)。求个后缀最小值即可。
然后现在解决如何求 \(f_i\)。
首先我们希望尽可能地多跳少挖，但是又要保证不会摔死。比较显然的是我们希望每次跳的高度尽量相等。设这个高度是 \(x\)，算一下伤害是多大，然后 \(O(1)\) 或者二分求解。有：
\[伤害=cnt_{d>x}\cdot x^2+(\sum d [d>x] -cnt_{d>x}\cdot x)+\sum d^2 [d \le x]+a_i \]就是高度差 \(>x\) 的地方跳 \(x\) 行，\(\le x\) 的地方跳 \(d\)，然后加上 \(>x\) 的地方往下挖的伤害和在 \(a_i\) 处往下挖的伤害。
表示为 \(cnt\cdot x^2 +sum-sum'+s+a_i\) 应该可以对应上吧
发现 \(cnt\)、\(sum\) 都是与 \(x\) 相关的分段函数，因此只能二分做。显然二分上界是 \(\sqrt{k}\)，下界需要取到 \(1\)，否则下文算 \(y\) 会出现除数为 \(0\) 的情况。
你发现 \(x\) 其实是单调不增的，所以上界可以双指针优化常数。
这里注意 \(d=0\) 的情况需要特判，此时你会直接往右边走一步，因此 \(f_i=f_{i-1}+1\)。然后又引出非关键列的 \(f_i\) 是多少，因为你会往右边挖一次然后走一步，因此有 \(f_i=f_{i-1}+2\)。
但是可能有一部分 \(>x\) 的地方可以选择跳 \(x+1\)，设有 \(y\) 个地方要跳 \(x+1\)。（下面的式子就要求上面的式子必须是 \(>x\) 和 \(\le x\)，不能是 \(\ge x\) 和 \(< x\)，否则 \(cnt\) 个位置有一些可能不能跳 \(x+1\) 的）
\[y(x+1)^2+(cnt-y)x^2+sum-sum'-y+s+a_i \le k \]这个不等式可以 \(O(1)\) 算。即
\[y=\lfloor \frac{k-cnt-x^2-sum+sum'-s-a_i}{(x+1)^2-x^2-1}\rfloor \]然后就是：
\[f_i=i-1+sum-sum'-y+a_i+cnt' \]这里是，往右边走花费 \(i-1\) 次，往下挖花费 \(sum-sum'-y\) 次和 \(a_i\) 次。\(cnt'\) 是 \(1\sim i\) 之间非关键列的个数，因为每个非关键列需要往右挖。
这些 \(cnt\)、\(sum\)、\(s\) 可以树状数组维护。
然后算《省流》的美丽式子就做完了。时间复杂度 \(O(n \log k)\)。感觉细节挺多的？主要是式子比较难想象出来。
code
简单重构了一下赛场恶心代码。现在简洁了一些。
#include<bits/stdc++.h>
// #define LOCAL
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
typedef long long ll;
#define gc getchar_unlocked
#define isdigit(x) (x>='0'&&x<='9')
template <typename T>
void read(T &x) {
x=0;
T fl=1;
char ch=gc();
for(;!isdigit(ch);ch=gc()) if(ch=='-') fl=-1;
for(;isdigit(ch);ch=gc()) x=(x<<3)+(x<<1)+ch-'0';
x=x*fl;
}
#define pc putchar_unlocked
template <typename T>
void write (T x,char ch) {
static int st[40];
int top=0;
if(x<0) pc('-'),x=-x;
ll y=10;
do {
st[top++]=x%10;
x=x/y;
}while(x);
while(top) pc(st[--top]+'0');
pc(ch);
}
constexpr int N=1e6+7;
constexpr ll inf=2e18+7;
int n,a[N],c[N];
ll k;
ll f[N];
ll l,r;
ll cnt0;
struct tree {
ll tr1[N][2],tr2[N];
ll b[N];
int m;
void init() {
rep(i,1,n) b[i]=c[i];
sort(b,b+n+1);
m=unique(b,b+n+1)-b-1;
}
void add1(int x,ll cnt,ll sum) {
for(;x<=m;x+=x&-x) tr1[x][0]+=cnt,tr1[x][1]+=sum;
}
void add2(int x,ll s) {
for(;x<=m;x+=x&-x) {
tr2[x]+=s;
if(tr2[x]>k) tr2[x]=k+1;
}
}
void ask1(int x,ll &cnt,ll &sum) {
for(;x;x-=x&-x) cnt+=tr1[x][0],sum+=tr1[x][1];
}
void ask2(int x,ll &s) {
for(;x;x-=x&-x) {
s+=tr2[x];
if(s>k+1) { s=k+1; return; }
}
}
void query(ll x,ll &cnt,ll &sum,ll &s) {
int y=upper_bound(b+1,b+m+1,x)-b;
ask1(m-y+1,cnt,sum);
ask2(y-1,s);
}
void insert(ll x) {
ll y=lower_bound(b+1,b+m+1,x)-b;
add1(m-y+1,1,x);
add2(y,x*x);
}
}T;
ll check(ll x,int a) {
ll cnt=0,sum=0,s=0;
T.query(x,cnt,sum,s);
__int128 ss=(__int128)cnt*x*x+sum-cnt*x+s+a;
return ss>k?k+1:ss;
}
ll find1(int i,ll l,ll r) {
while(l<r) {
ll mid=(l+r+1)>>1;
if(check(mid,a[i])>k) r=mid-1;
else l=mid;
}
return l;
}
ll find2(ll i,ll x,ll &sum,ll &cnt) {
ll s=0;
T.query(x,cnt,sum,s);
if(cnt==0) return 0;
return (k-cnt*x*x-sum+cnt*x-s-a[i])/((x+1)*(x+1)-x*x-1);
}
int la;
bool fl[N];
ll g[N];
int main() {
#ifdef LOCAL
freopen("my.out","w",stdout);
#else
freopen("world.in","r",stdin);
freopen("world.out","w",stdout);
#endif
read(n),read(k);
l=1,r=sqrt(1.0*k);
rep(i,1,n) read(a[i]);
la=a[1];
rep(i,1,n) {
if(a[i]<=la) {
c[i]=la-a[i];
la=a[i];
}else fl[i]=1;
}
T.init();
f[1]=a[1];g[1]=a[1]+2;
rep(i,2,n) {
if(fl[i]) { f[i]=f[i-1]+2; g[i]=f[i]+2*i; cnt0++; continue;}
if(c[i]==0) {
f[i]=f[i-1]+1;
g[i]=f[i]+2*i;
continue;
}
T.insert(c[i]);
ll x=find1(i,l,r);
r=x;
ll sum=0,cnt=0;
ll y=find2(i,x,sum,cnt);
f[i]=i-1+sum-cnt*x-y+a[i]+cnt0;
g[i]=f[i]+2*i;
}
per(i,n-1,1) {
g[i]=min(g[i],g[i+1]);
}
rep(i,1,n) {
ll ans=g[i]-2*i;
write(ans,' ');
}
}