暑期总结2

感觉暑假里要把四大离线算法学完(先猜一个flag)。

最开始的两天讲的是整体二分。

就是把询问离线，去二分答案的值域，并把当前可行的答案带着走。

大概长这样：

// 当前 qry[L~R] 的答案的值域在 [l,r]
void slove(int l,int r,int L,int R) 
{
    if(l>r || L>R) return ;
    // 递归到边界，更新答案。
    if(l==r) { for(int i=L;i<=R;i++) ans[qry[i].id]=l; return ; }

    int mid((l+r)>>1),t1(0),t2(0);
    for(int i=L;i<=mid;i++)
    {
        // ck(i)=true 表示qry[i]的答案在左半部分
        if(ck(i)) q1[++t1]=qry[i];
        else q2[++t2]=qry[i];
    }

    // 划分询问数组
    for(int i=L;i<=L+t1-1;++i) qry[i]=q1[i-L+1];
    for(int i=L+t;i<=R;++i)    qry[i]=q2[i-L-t1+1];
    // 递归
    slove(l,mid,L,L+t1-1),slove(mid+1,r,L+t1,R);
}

然后，它能够优化 $DP$ 。。。

如果 $f[i]$ 的最优决策点 $p[i]$ 存在单调性，那么就能在 $\Theta(nlogn)$ 求出 $f$$[1$~$n]$。

长这样：

// 要求出 f[l~r]， 决策点在 [L,r] 间。
void slove(int l,int r,int L,int R)
{
    if(l>r || L>R) return ;

    // 以求最小值为例：
    // mi 表示最优值，p表示最优决策点
    int mid=(l+r)/2,p=0,mi=INF;
    for(int i=L;i<=R && i<=mid;++i)
    {
        // ask(i,mid): mid由i转移而来的代价
        if(ask(i,mid)<mi)
            mi=ask(i,mid),p=i;
    }

    //计算 f
    f[mid]=min(f[mid],mi);
    //划分区间
    slove(l,mid-1,L,p),slove(mid+1,r,p,R);
}

---

---

---

然后讲了斜率优化。

斜率优化不只是优化DP，例如 机器学习题

本质是把式子化成

$$b~=~min / max\{~ y-kx ~\}$$

的形式，然后利用凸包去切截距。

放一张图：

---

下面是自学内容：李超树

李超树结局的是一类 动态线段问题 ：

给你若干操作，要求在线。

1 k b : 插入一条 $y=kx+b$ 的线段

2 x0 : 询问当 $x=x_0$ 时，最小的 y。

新来的区间一定会与老区间产生焦点，从而划分为两部分(一部分答案为老区间，另一部分为新区间)。

我们递归新区间的部分即可。

int tot,indx,rt;
struct node{ int k,b; }a[N];
struct seg{
	#define ls tr[u].lson
	#define rs tr[u].rson
	int lson,rson,id; 
}tr[N<<2];

inline int f(int id,int x) { return a[id].k*x+a[id].b; }
inline bool cmp(int i,int j,int x) { return f(i,x)<f(j,x); }
//插入编号为id的线段。 
void add(int &u,int l,int r,int id)
{
	int &p=tr[u].id;
	if(!u) return (tr[u=++tot].id=id),void();
	if(l==r) return (cmp(id,p,l) ? p=id : 0),void();

	int mid((l+r)>>1);
	if(cmp(id,p,mid)) swap(id,tr[u].id);
	if(cmp(id,p,l)) add(ls,l,mid,id);
	else add(rs,mid+1,r,id);
} void insert(int k,int b) { a[++indx]={k,b}; add(rt,0,INF,indx); }

//询问x=t时的最小y 
int ask(int u,int l,int r,int t)
{
	int p=tr[u].id;
	if(!u) return INF;
	if(l==r) return f(p,t);
	int mid((l+r)>>1);
	return min(f(p,t) , t<=mid ? ask(ls,l,mid,t) : ask(rs,mid+1,r,t));
} int query(int x) { return ask(rt,0,INF,x); }

这玩意的$log_n \approx 1$，空间也小得可怜。