Part 1：标记永久化

一言以蔽之：标记永久化就是不再下放标记，而是让标记永久地停留在线段树的节点上，统计答案时再考虑这些标记的影响

Part 2：维护直线

我们以下面这道题为例子来进行讲解

[JSOI2008] Blue Mary开公司

（题目传送门）

题目大意

在平面上有两种操作：

• Project：插入一条 $y=kx+b$ 的直线，给定 $k,b$
• Query：求所有直线中与直线 $x=t$ 的交点的纵坐标最大值是多少

解题思路

• 我们首先建立一棵线段树，每个节点代表一个区间，且有一个标记记录一条直线

• 对于插入直线的操作：

  • 如果当前区间还没有标记，我们将这个区间标记为当前直线

  • 如果有标记，但插入的直线完全覆盖原先的直线，即替换掉原先的直线

  • 如果插入的直线被原先的直线完全覆盖，即返回

  • 剩下的情况就是插入的和原先的直线在区间内有交点。那么我们令 $mid=(l+r)/2$，令与直线 $x=mid$ 交点纵坐标更大的直线作为当前区间被标记的直线。然后递归交点所在的区间子树，继续修改即可

• 对于查询操作，类似标记永久化，找到所有覆盖了 $x=t$ 的区间，考虑该区间的贡献即可

• 时间复杂度：$O(n\log n)$

代码

#include<bits/stdc++.h>
using namespace std;const int N=100010,T=50010;
const double eps=1e-12;struct line
{double k,b; //斜率和截距int l,r; bool flag; //标记#define flag(x)  tree[x].flag
}tree[4*T];int n;
char op[10];double calc(line a,int x) //通过x计算y
{return (double)x*a.k+a.b;
}void build(int p,int l,int r)
{tree[p]=(line){0,0,1,50000,0};if(l==r)return;int mid=(l+r)>>1;build(p*2,l,mid);build(p*2+1,mid+1,r);
}void change(int p,int l,int r,line k)
{if(k.l<=l && k.r>=r) //完全覆盖区间{if(!flag(p)) //没有标记tree[p]=k,flag(p)=1;else if(calc(k,l)-calc(tree[p],l)>eps && calc(k,r)-calc(tree[p],r)>eps) //有标记但插入的更优tree[p]=k;else if(calc(k,l)-calc(tree[p],l)>eps || calc(k,r)-calc(tree[p],r)>eps) //有交点{int mid=(l+r)>>1;if(calc(k,mid)-calc(tree[p],mid)>eps) //令与x=mid交点更高的作为标记swap(tree[p],k);if(calc(k,l)-calc(tree[p],l)>eps) //递归交点的区间子树change(p*2,l,mid,k);elsechange(p*2+1,mid+1,r,k);}}else //未完全覆盖{int mid=(l+r)>>1;if(k.l<=mid)change(p*2,l,mid,k);if(k.r>mid)change(p*2+1,mid+1,r,k);}
}double ask(int p,int l,int r,int x) //标记永久化的查询需要不断递归直到一个点
{if(l==r){if(flag(p))return calc(tree[p],x);return -1e18;}int mid=(l+r)>>1;double val=-1e18;if(flag(p))val=calc(tree[p],x); //当前点的标记if(x<=mid) //递归子树return max(val,ask(p*2,l,mid,x));return max(val,ask(p*2+1,mid+1,r,x));} int main()
{build(1,1,50000);scanf("%d",&n);for(int i=1; i<=n; i++){scanf("%s",op);if(op[0]=='P'){double s,p;scanf("%lf%lf",&s,&p);line now=(line){p,s-p,1,50000,1};change(1,1,50000,now);}else{int t;scanf("%d",&t);double ans=ask(1,1,50000,t);int anss=(int)(ans/100.0);if(anss<0)printf("0\\n");elseprintf("%d\\n",anss);}}return 0;
}

[CEOI2017] Building Bridges

（题目传送门）

题目大意

有 $n$ 根柱子依次排列，每根柱子都有一个高度。第 $i$ 根柱子的高度为 hih_ihi​。

现在想要建造若干座桥，如果一座桥架在第 $i$ 根柱子和第 $j$ 根柱子之间，那么需要 (hi−hj)2(h_i-h_j)^2(hi​−hj​)2​​ 的代价。

在造桥前，所有用不到的柱子都会被拆除，因为他们会干扰造桥进程。第 $i$ 根柱子被拆除的代价为 wiw_iwi​，注意 wiw_iwi​ 不一定非负，因为可能政府希望拆除某些柱子。

现在政府想要知道，通过桥梁把第 $1$ 根柱子和第 $n$ 根柱子连接的最小代价。注意桥梁不能在端点以外的任何地方相交。

对于 $100\%$ 的数据，有 2≤n≤105;0≤hi,∣wi∣≤1062\\le n\\le 10^5;0\\le h_i,\\vert w_i\\vert\\le 10^62≤n≤105;0≤hi​,∣wi​∣≤106。

解题思路

• 首先 O(n2)O(n^2)O(n2) 的 dp 很好想
  设 fif_ifi​ 表示连接第 $1$ 根和第 $i$ 根柱子的最小代价，答案即为 fnf_nfn​
  那么状态转移方程也是显然的：
  fi=min⁡{fj+(hi−hj)2+∑k=j+1i−1wk}f_i=\\min\\{f_j+(h_i-h_j)^2+\\sum\\limits_{k=j+1}^{i-1}w_k\\}fi​=min{fj​+(hi​−hj​)2+k=j+1∑i−1​wk​}

• 现在我们令 wi+=wi−1w_i+=w_{i-1}wi​+=wi−1​，即做一次前缀和，则有
  fi=min⁡{fj+(hi−hj)2+wi−1−wj}f_i=\\min\\{f_j+(h_i-h_j)^2+w_{i-1}-w_j\\}fi​=min{fj​+(hi​−hj​)2+wi−1​−wj​}

• 考虑优化，将式子化简得：
  fi=hi2+wi−1+min⁡{fj−2hihj+hj2−wj}f_i=h_i^2+w_{i-1}+\\min\\{f_j-2h_ih_j+h_j^2-w_j\\}fi​=hi2​+wi−1​+min{fj​−2hi​hj​+hj2​−wj​}

• 我们令 k=−2hj,b=fj+hj2−wjk=-2h_j,\\:b=f_j+h_j^2-w_jk=−2hj​,b=fj​+hj2​−wj​，则后面的式子转化为一条直线 y=khi+by=kh_i+by=khi​+b，问题转化为求所有直线与 x=hix=h_ix=hi​ 的交点的纵坐标的最小值，并插入当前自己所代表的直线

代码

#include<bits/stdc++.h>
#define LL long long
using namespace std;const int N=100010,M=1000010;
const LL INF=1e16;struct line
{LL k,b;int l,r;bool flag;#define flag(x)  tree[x].flag
}tree[4*M];int n;
LL h[N],w[N],f[N];LL calc(line a,LL x)
{return x*a.k+a.b;
}void build(int p,int l,int r)
{tree[p]=(line){0,0,0,M,0};if(l==r)return;int mid=(l+r)>>1;build(p*2,l,mid);build(p*2+1,mid+1,r);
}void change(int p,int l,int r,line k)
{if(k.l<=l && k.r>=r){if(!flag(p))tree[p]=k,flag(p)=1;else if(calc(k,l)<calc(tree[p],l) && calc(k,r)<calc(tree[p],r))tree[p]=k;else if(calc(k,l)<calc(tree[p],l) || calc(k,r)<calc(tree[p],r)){int mid=(l+r)>>1;if(calc(k,mid)<calc(tree[p],mid))swap(k,tree[p]);if(calc(k,l)<calc(tree[p],l))change(p*2,l,mid,k);elsechange(p*2+1,mid+1,r,k);}}else{int mid=(l+r)>>1;if(k.l<=mid)change(p*2,l,mid,k);if(k.r>mid)change(p*2+1,mid+1,r,k);}
}LL ask(int p,int l,int r,LL x)
{if(l==r){if(flag(p))return calc(tree[p],x);return INF;}int mid=(l+r)>>1;LL val=INF;if(flag(p))val=calc(tree[p],x);if(x<=mid)return min(val,ask(p*2,l,mid,x));return min(val,ask(p*2+1,mid+1,r,x));} int main()
{build(1,0,M);scanf("%d",&n);for(int i=1; i<=n; i++)scanf("%lld",&h[i]);for(int i=1; i<=n; i++)scanf("%lld",&w[i]),w[i]+=w[i-1];f[1]=0;line now={-2*h[1],h[1]*h[1]-w[1],0,M,1};change(1,0,M,now);for(int i=2; i<=n; i++){f[i]=h[i]*h[i]+w[i-1]+ask(1,0,M,h[i]);now={-2*h[i],f[i]+h[i]*h[i]-w[i],0,M,1};change(1,0,M,now);	}printf("%lld",f[n]);return 0;
}

五月天