P11678
lsj2009
·
·
题解
Preface
赛后 20min 调出，，，
Description
定义 f(a_{1\sim m},b_{1\sim m-1}) 的值为：
给定 a_{1\sim n} 和 b_{1\sim n-1}，对于任意 2\le i\le n 求出 f(a_{1\sim i},b_{1\sim i-1}) 的值。
### Solution
记 $V=\max{a_i}$。
考虑一个暴力是从左往右 dp，记 $f_{i,j}$ 表示 $x_{1\sim i-1}$ 的取值已经确定、前 $i-1$ 个不等式的限制已经满足且 $x_{i-1}=j$ 的 $\sum\limits_{j<i} b_jx_j$ 的最小值。
则 $f(a_{1\sim i},b_{1\sim i-1})$ 的值就是 $\min\limits_{j\ge a_i} f_{i,j}$。
简单粗暴地可以得到转移方程：
$$f_{i,j}\gets \left(\min\limits_{k\ge a_{i-1}-j} f_{i-1,k}\right)+j\cdot b_{i-1}$$
可以做到 $\mathcal{O}(nV^2)$ 或 $\mathcal{O}(nV)$。
考虑优化，然后就一拍脑袋说：**我猜他是凸的**！看看能不能上个 **slope trick**！
当然有点 corner case：$i\le 2$ 时有些 $f_{i,j}$ 是不合法的，也就是更严谨的是：
- 我们断言：**当 $i\ge 3$ 时 $f_{i,*}$ 是下凸的**。
套路地考虑 **归纳证明**：
- 当 $i=3$ 时，不妨对初始的 corner case 暴力讨论一下：
- 当 $i=1$ 时只有 $f_{1,0}=0$，其余值均可以视作 $\infty$。
- 当 $i=2$ 时那就是 $j\ge a_1$ 部分是一条从 $(a_1,a_1b_1)$ 开始斜率为 $b_1$ 的射线。其余部分为 $\infty$。
- 当 $i=3$ 时：
- 若 $a_2\le a_1$ 则全局范围内为一条从 $(0,a_1b_1)$ 开始斜率为 $b_2$ 的射线。
- 若 $a_2>a_1$ 则全局范围内为一条 $(0,a_2b_1)-(a_2-a_1,a_1b_1+(a_2-a_1)b_2)$ 斜率为 $b_2-b_1$ 的线段和一条从 $(a_2-a_1,a_1b_1+(a_2-a_1)b_2)$ 开始的斜率为 $b_2$ 的射线。
- 则当 $i=3$ 时 $f$ 已在 **全局范围** 内构成了一个 **下凸壳**。
- 当 $i>3$ 时且我们已经说明 $f_{i-1,*}$ 是下凸的：
- 找到 $f_{i-1,*}$ 中 **最小值的（第一个）取值点** $p$，则考察 $f_{i-1,*}$ 的差分序列 $\mathrm{d}f_{i-1,j}=f_{i-1,j}-f_{i-1,j-1}$ 有：
- 对于任意 $1\le k\le p$ 有 $\mathrm{d}f_{i-1,k}<0$。
- 对于任意 $k> p$ 有 $\mathrm{d}f_{i-1,k}\ge 0$。
- 若 $p\ge a_{i-1}$，则此时 **全局斜率变为零**，随后 **全局斜率增加 $b_{i-1}$**。
- 则此时退化为一条射线，显然仍然为凸的。
- 若 $p<a_{i-1}$，则此时我们 **截取出凸壳在 $[p,a_{i-1}]$ 的部分**，将其 **翻转**（对应到差分序列上为 **左开右闭区间翻转再取反**），然后 **放置在最前面**，其余部分斜率推平成 $0$，随后 **全局斜率增加 $b_{i-1}$**。
- 全局增加斜率并不影响凸性；考察做此操作之前的凸性：由于对于任意 $k> p$ 有 $\mathrm{d}f_{i-1,k}\ge 0$ 且递增，则 **翻转并取反** 后仍然递增且不大于 $0$，再接上剩余为 $0$ 的部分仍然符合条件。
对于 $i\le 3$ 的我们可以直接 $\mathcal{O}(V)$ 暴力做；对于 $i>3$ 的部分，根据上面的证明发现我们要支持：
1. 区间翻转。
2. 区间位移（即把三个区间 $x,y,z$ 的顺序变为 $y,x,z$）。
3. 区间取反（即把区间中所有值为 $x$ 的数变为 $-x$）。
4. 区间推平为 $0$。
5. 全局加。
使用 **FHQ-Treap** 容易维护。具体实现上：
- 注意到 $1,3$ 操作其实操作的区间一致，所以只需要打一个 tag。所以最终需要三个 tag。
- 然后还需要额外 **手动维护 $f_{i,0}$ 的值**。
视实现最终复杂度是 $\mathcal{O}(n\log{V}+V)$ 或者 $\mathcal{O}(V\log{V})$。
可以参考代码，5.4kb，倒也不算长。
### Code
```cpp
#include<bits/stdc++.h>
#define int long long
// #pragma GCC optimize(3,"Ofast","inline")
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ll long long
#define bint __int128
#define ull unsigned long long
#define uint unsigned int
#define ld double
#define PII pair<int,int>
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
#define pcnt(x) __builtin_popcount(x)
#define lg(x) (31-__builtin_clz(x))
using namespace std;
void file_IO() {
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
}
bool M1;
const int INF=0x3f3f3f3f;
const ll INFLL=0x3f3f3f3f3f3f3f3f;
const ld eps=1e-9;
mt19937 rd(time(0));
struct FHQ_Treap {
static const int N=1e6+5;
struct node {
int lson,rson,siz,val,sum,x,tag1,tag2,tag3;
node() {
lson=rson=siz=val=sum=tag1=tag2=tag3=0;
}
node(int a,int b,int c,int d,int e,int f,int g,int h,int i) {
lson=a; rson=b;
siz=c;
val=d; sum=e;
x=f;
tag1=g; tag2=h; tag3=i;
}
}; node tree[N];
#define ls(k) tree[k].lson
#define rs(k) tree[k].rson
void push_up(int k) {
tree[k].siz=tree[ls(k)].siz+tree[rs(k)].siz+1;
tree[k].sum=tree[ls(k)].sum+tree[rs(k)].sum+tree[k].val;
}
int p;
int new_node(int val) {
tree[++p]=node(0,0,1,val,val,(int)rd(),0,0,0);
return p;
}
void upd(int k,int t1,int t2,int t3) {
if(!k)
return;
if(t3) {
tree[k].val=tree[k].sum=0;
tree[k].tag1=tree[k].tag2=0;
tree[k].tag3=1;
}
if(t1) {
swap(ls(k),rs(k));
tree[k].tag1^=1;
tree[k].val=-tree[k].val;
tree[k].sum=-tree[k].sum;
tree[k].tag2=-tree[k].tag2;
}
tree[k].val+=t2;
tree[k].sum+=t2*tree[k].siz;
tree[k].tag2+=t2;
}
void push_down(int k) {
int &t1=tree[k].tag1,&t2=tree[k].tag2,&t3=tree[k].tag3;
if(t1||t2||t3) {
upd(ls(k),t1,t2,t3);
upd(rs(k),t1,t2,t3);
t1=t2=t3=0;
}
}
int merge(int u,int v) {
if(!u||!v)
return u|v;
if(tree[u].x<tree[v].x) {
push_down(u);
rs(u)=merge(rs(u),v);
push_up(u);
return u;
} else {
push_down(v);
ls(v)=merge(u,ls(v));
push_up(v);
return v;
}
}
void split(int k,int val,int &u,int &v) {
if(!k) {
u=v=0;
return;
}
push_down(k);
if(tree[k].val<val)
u=k,split(rs(k),val,rs(k),v);
else
v=k,split(ls(k),val,u,ls(k));
push_up(k);
}
void split_siz(int k,int val,int &u,int &v) {
if(!k) {
u=v=0;
return;
}
push_down(k);
if(tree[ls(k)].siz<val)
u=k,split_siz(rs(k),val-tree[ls(u)].siz-1,rs(k),v);
else
v=k,split_siz(ls(k),val,u,ls(k));
push_up(k);
}
}; FHQ_Treap T;
const int N=5e5+5,M=1e6+5,m=1e6;
int a[N],b[N],f[2][M],suf[M];
int query(int &rt,int p) {
int u=0,v=0;
T.split(rt,0,u,v);
int mnpos=T.tree[u].siz;
if(mnpos>=p) {
int val=T.tree[u].sum;
rt=T.merge(u,v);
return val;
} else {
rt=T.merge(u,v);
u=v=0;
T.split_siz(rt,p,u,v);
int val=T.tree[u].sum;
rt=T.merge(u,v);
return val;
}
}
void solve() {
int n;
scanf("%lld",&n);
rep(i,1,n)
scanf("%lld",&a[i]);
rep(i,1,n-1)
scanf("%lld",&b[i]);
cl(f,0x3f);
int p=1;
f[1][0]=0;
rep(i,2,3) {
p^=1;
rep(j,0,m)
f[p][j]=INFLL;
suf[m+1]=INFLL;
per(j,m,0)
suf[j]=min(suf[j+1],f[p^1][j]);
rep(k,0,m) {
f[p][k]=INFLL;
chkmin(f[p][k],suf[max(a[i-1]-k,0ll)]+b[i-1]*k);
}
int mn=INFLL;
rep(j,a[i],m)
chkmin(mn,f[p][j]);
printf("%lld\n",mn);
}
int x=f[p][0],rt=0;
rep(i,1,m)
rt=T.merge(rt,T.new_node(f[p][i]-f[p][i-1]));
rep(i,4,n) {
int u=0,v=0;
T.split(rt,0,u,v);
int mnpos=T.tree[u].siz;
if(mnpos<a[i-1]) {
rt=T.merge(u,v);
x+=query(rt,a[i-1]);
int w=0;
u=v=0;
T.split_siz(rt,mnpos,u,v);
int t=v; v=0;
T.split_siz(t,a[i-1]-mnpos,v,w);
T.upd(v,1,0,0);
T.upd(u,0,0,1);
T.upd(w,0,0,1);
rt=T.merge(v,T.merge(u,w));
} else {
x+=T.tree[u].sum;
rt=T.merge(u,v);
T.upd(rt,0,0,1);
}
T.upd(rt,0,b[i-1],0);
printf("%lld\n",x+query(rt,a[i]));
}
}
bool M2;
// g++ C.cpp -std=c++14 -Wall -O2 -o C
signed main() {
// file_IO();
int testcase=1;
// scanf("%d",&testcase);
while(testcase--)
solve();
debug("used time = %dms\n",(signed)(1000*clock()/CLOCKS_PER_SEC));
debug("used memory = %dMB\n",(signed)((&M1-&M2)/1024/1024));
return 0;
}
```