DP 优化
Part 1 最长上升子序列
优先队列优化最长上升子序列。每次将求完的 \(f_i\) 丢进 priority_queue，求最大值时取堆顶。
复杂度 \(O(n^2)\to O(n\log n)\)
Part 2 线段树优化 DP
写出常规 DP 转移方程式，区间修改、查询如果可以用线段树维护就可将 \(O(n)\to O(\log n)\)。
【例 1】[TJOI2011]书架
已知长为 \(n\) 的数组 \(a\)、整数 \(m\)，将 \(a\) 分为若干连续段，要求每段和 \(\le m\)，求每段最大值之和的最小值。
设 \(f_i\) 表示前缀 \(a_{1...i}\) 的答案，
发现没有办法用线段树维护一个既含 \(\max\) 又含 \(\min\) 的东西，但是它可以维护,其中 \(g_j\) 为一个和 \(f_j\) 地位相等的量；它可以支持对 \(f_j,g_j\) 的实时修改和对 \(f_j,g_j,f_j+g_j\) 的实时查询。
观察到 \(a_i\) 的添加只会对 \(j\in[pre_i+1,i]\) 的 \(\max(a_{j+1},...,a_i)(1)\) 产生影响，其中 \(pre_{i}\) 表示 \(i\) 前面最近的大于等于 \(a_i\) 的数的位置，因此可以令 \(g_j\) 表示式子 \((1)\) 的值，而对 \(g_{pre_i+1}...g_i\) 区间修改为 \(a_i\) 即可。
求 \(f_i\) 时需要查询 \(q\sim i\) 的 \(f+g\) 的和即可，求完之后在线段树中单点更新 \(f_i\)。
下面代码实现中维护的 \(fm\) 实际上是 \(f_{i-1}+g_i\)，$f% 实际上是 \(f_{i-1}\)。
#include
using namespace std;
const int N=1e5+5;
#define int long long
int n,m,top,a[N],s[N],stk[N],pre[N],f[N];
struct segmt {
int f,fm,tag;
}t[N<<2];
void pushup(int k){
t[k].f=min(t[k<<1].f,t[k<<1|1].f);
t[k].fm=min(t[k<<1].fm,t[k<<1|1].fm);
}
void pushdown(int k){ //change max
if(!t[k].tag)return;
t[k<<1].tag=t[k<<1|1].tag=t[k].tag;
t[k<<1].fm=max(t[k<<1].fm,t[k<<1].f+t[k].tag);
t[k<<1|1].fm=max(t[k<<1|1].fm,t[k<<1|1].f+t[k].tag);
t[k].tag=0;
}
void build(int l,int r,int k){
if(l==1&&l==r){t[k].tag=0,t[k].f=t[k].fm=0;return;}
if(l==r){t[k].tag=0,t[k].f=t[k].fm=1e9;return;}
int mid=l+r>>1;
build(l,mid,k<<1),build(mid+1,r,k<<1|1);
pushup(k);
}
void chgmx(int L,int R,int v,int l,int r,int k){
if(L<=l&&r<=R){
t[k].tag=v;
t[k].fm=v+t[k].f;
return;
}
pushdown(k);
int mid=l+r>>1;
if(L<=mid)chgmx(L,R,v,l,mid,k<<1);
if(R>mid)chgmx(L,R,v,mid+1,r,k<<1|1);
pushup(k);
}
void chgf(int p,int v,int l,int r,int k){
if(l==r){t[k].fm-=t[k].f,t[k].fm+=v,t[k].f=v;return;}
pushdown(k);
int mid=l+r>>1;
if(p<=mid)chgf(p,v,l,mid,k<<1);
else chgf(p,v,mid+1,r,k<<1|1);
pushup(k);
}
int ask(int L,int R,int l,int r,int k){
if(L<=l&&r<=R)return t[k].fm;
pushdown(k);
int mid=l+r>>1,ans=1e9;
if(L<=mid)ans=min(ans,ask(L,R,l,mid,k<<1));
if(R>mid)ans=min(ans,ask(L,R,mid+1,r,k<<1|1));
return ans;
}
signed main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
s[i]=s[i-1]+a[i];
while(top&&a[stk[top]] Part 3 前缀和优化(后缀和优化)
AGC024E
灯塔
则主要求 \(f_i=\max_{j
所求式可以看成是对于每一个 \(j\)，有一个函数 \(f_j(i)=h_j+\sqrt{i-j}(i\ge j)\)
在同一张纸上画出各函数图像↓（借用了他人博客图片）
我们知道 \(\sqrt x\) 函数的增长速率单调减慢，所以每个时刻的值最大（最考上）的函数所属的 \(j\) 一定是单调不降的。
我们发现了决策单调性。
如何使用决策单调性
用一个“单调队列”存储若干三元组 \((j,l,r)\)，表示目前，\([l,r]\) 的最优决策为 \(j\)，所有的 \([l,r]\) 并起来应该是 \([i,n]\) 这个区间。
- 取出队头 \((j,l,r)\)，若 \(r
- 将队头的 \(l\) 设为 \(i\)
- 计算 \(f[i]\)
- 取出队尾 \((j,l,r)\)，若对于 \(f_l\)，\(j\) 比 \(i\) 劣，则结合单调性可知 \([l,r]\) 都废除，令 \(pos=l\)，重复此步骤（直到队空or不满足条件）
- 取出队尾 \((j,l,r)\)，若对于 \(f_r\)，\(j\) 比 \(i\) 劣，则在 \([l,r]\) 上二分一个最小的 \(mid\) 使得对于 \(f_mid\)，\(j\) 比 \(i\) 劣，令 \(pos=mid\)
- 将 \((i,pos,n)\) 入队尾
#include
using namespace std;
const int N=1e5+5;
int n,l,r,h[N];
double f[N],g[N];
struct J {
int x,l,r;
}q[N];
void solve(int h[],double f[]){
l=1,r=0;q[++r]={1,1,n};
for(int i=2;i<=n;i++){
while(l<=r&&q[l].r>1;
if(h[q[r].x]+sqrt(mid-q[r].x)>n;
for(int i=1;i<=n;i++)cin>>h[i];
solve(h,f);
reverse(h+1,h+n+1);
solve(h,g);
reverse(h+1,h+n+1);
reverse(g+1,g+n+1);
for(int i=1;i<=n;i++)cout<