一开始还想着“这个文笔，牛逼啊，现在都这么有技术力了吗”，结果一看后记野村美月！对不起长官，刚才没有认出你。

言归正传，虽然我既不是 s 也不是 m 但是这本书确实很有趣，而且恋爱喜剧的成分很重，野村美月老师特有的细腻文笔也表现得淋漓尽致，可以供消遣用。感觉她做得最成功的一点是避免了人物脸谱化，每个人仿佛都没有很浓厚的戏剧效果，说是恋爱喜剧不如说是小故事。

模板

经典问题：单点加区间最大子段和

加强：区间加区间最大子段和（加的都是正数）

原问题的信息维护：

s,ls,rs,mx

：区间和，包含左端点的最大和，包含右端点的最大和，区间最大子段和

我们考虑区间加对这些操作的影响，如果区间加之后最优的决策点没有发生变化，那么每个值应该可以写成一次函数的形式：

kx+b

。其中

x

表示区间加的值，

k

就是最优决策的区间长度。

为了判断最优决策区间是否发生改变，我们还需要记录一个值

lim

表示如果区间加的累计值

x>lim

则

ls,rs,mx

中至少有一个的决策会发生改变。在实现的时候我们每次给

lim

减去区间加的值，如果

lim<0

那么就暴力递归整个子树进行重构，重构时如果当前节点的

lim\ge 0

则直接返回，否则递归。

关于标记的合并：

$s=l.s+r.s$
$ls=\max(l.ls,l.s+r.ls)$
$rs=\max(r.rs,r.s+r.rs)$
$mx=\max(l.mx,r.mx,l.rs+r.ls)$
$lim=\min(l.lim,r.lim,各种决策的函数交点)$ ，函数的交点如果 $<0$ 或者没有则值为 $\inf$ 。

其中

\max

的比较依据为一次函数在

x=0

处的值的大小，

+

为一次函数加。

时间复杂度：

O((n+m)\log^3 n+q\log n)

，其中

n,m

为序列长度和修改次数，

q

为询问次数，实际跑起来是大常单

\log

的感觉，因为发明者给出的这个复杂度只是一个粗浅的上界，并没有卡满。

CPP

struct Line{int k;ll b;};
inline Line operator+(const Line &a,const Line &b){return (Line){a.k+b.k,a.b+b.b};}
pair<Line,ll>max(Line a,Line b){
	if(a.k<b.k||(a.k==b.k&&a.b<b.b))swap(a,b);
	if(a.b>=b.b)return mk(a,inf);
	return mk(b,(b.b-a.b)/(a.k-b.k));
}
struct Misaka{Line s,ls,rs,mx;ll x;};
inline Misaka operator+(const Misaka &a,const Misaka &b){
	Misaka c;pair<Line,ll>o;
	c.s=a.s+b.s,c.x=min(a.x,b.x);
	o=max(a.ls,a.s+b.ls),c.ls=o.first,c.x=min(c.x,o.second);
	o=max(b.rs,b.s+a.rs),c.rs=o.first,c.x=min(c.x,o.second);
	o=max(a.mx,b.mx),c.x=min(c.x,o.second);
	o=max(o.first,a.rs+b.ls),c.mx=o.first,c.x=min(c.x,o.second);
	return c;
}

S与S的无赖同盟（KTT）

文章操作

模板

相关推荐

评论

S与S的无赖同盟（KTT）