KTT

概述

一般用于解决以下问题

• 序列每个点维护 $a_ix+b_i$（即一次函数）。

• 区间 $b$ 加一个非负数。

• 区间 $x$ 加一个非负数。

• 查询区间最大值。

直接线段树维护最大值是有问题的：最大值可能变化（一次函数可能有交点）。

考虑维护一个 $tim$ 记录最大值最早何时会发生变化。

可以证明复杂度是 $O((n+m) \mathrm{polylog} (n))$，证明可以看 EI 博客。

可以看作 $O((n+m)\log^2n)$。

实现与线段树类似，唯一不同的是 $tim$ 的维护

• $x$ 区间加 $c$ 时，$tim$ 应减去 $c$。

• pushup 时，$tim$ 应取左右节点 $tim$ 及交点横坐标的最小值（也就是最早变化时间）。

• 当 $tim<0 / \le 0$ 时（这里看求交点时是下取整还是上取整），进行 rebuild（其实就是 dfs，具体实现看代码）。

例题

1.EI 的第六分块

模板题，发现 lmax,rmax,maxn,sum 区间加时，都可以写成一次函数 $x$ 加的形式（$k$ 就是区间长度）。

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define pli pair<LINE,int>
#define MP make_pair
#define fi first
#define se second
const int N=4e5+100,INF=1e18;
inline int chkmin(int &x,int y){ return y<x?x=y,1:0; }
#define gc getchar()
#define rd read()
inline int read(){
	int x=0,f=0; char c=gc;
	for(;c<'0'||c>'9';c=gc) f|=(c=='-');
	for(;c>='0'&&c<='9';c=gc) x=(x<<1)+(x<<3)+(c^48);
	return f?-x:x;
}

int n,m,a[N];

struct LINE{ int a,b; };
inline LINE operator+(const LINE &x,const LINE &y){ return {x.a+y.a,x.b+y.b}; }
inline pli mer(LINE x,LINE y){
	if((x.a<y.a)||(x.a==y.a&&x.b<y.b)) swap(x,y);
	return (x.b>=y.b?MP(x,INF):MP(y,(y.b-x.b)/(x.a-y.a)));
}
struct NODE{
	LINE lm,rm,mx,sum; int tim;
	void add(int v){ lm.b+=lm.a*v,rm.b+=rm.a*v,mx.b+=mx.a*v,sum.b+=sum.a*v,tim-=v; }
};
NODE operator+(const NODE &x,const NODE &y){
	NODE z; z.tim=min(x.tim,y.tim); z.sum=x.sum+y.sum; pli tmp;
	tmp=mer(x.lm,x.sum+y.lm),z.lm=tmp.fi,chkmin(z.tim,tmp.se);
	tmp=mer(y.rm,y.sum+x.rm),z.rm=tmp.fi,chkmin(z.tim,tmp.se);
	tmp=mer(x.mx,y.mx),chkmin(z.tim,tmp.se);
	tmp=mer(tmp.fi,x.rm+y.lm),z.mx=tmp.fi,chkmin(z.tim,tmp.se);
	return z;
}

struct SMT{
	#define lc (id<<1)
	#define rc (id<<1|1)
	#define mid (l+r>>1)
	struct TREE{ NODE v; int atag; }t[N<<2];
	void psu(int id){ t[id].v=t[lc].v+t[rc].v; }
	void add(int id,int v){ t[id].v.add(v),t[id].atag+=v; }
	void spd(int id){ if(t[id].atag!=0) add(lc,t[id].atag),add(rc,t[id].atag),t[id].atag=0; }
	void rbui(int id){ if(t[id].v.tim<0) spd(id),rbui(lc),rbui(rc),psu(id); }
	void bui(int id,int l,int r){
		if(l==r) return t[id]={{{1,a[l]},{1,a[l]},{1,a[l]},{1,a[l]},INF},0},void();
		bui(lc,l,mid),bui(rc,mid+1,r),psu(id);
	}
	void add(int id,int l,int r,int ql,int qr,int v){
		if(ql<=l&&r<=qr) return add(id,v),rbui(id); spd(id);
		if(ql<=mid) add(lc,l,mid,ql,qr,v);
		if(qr>=mid+1) add(rc,mid+1,r,ql,qr,v);
		psu(id);
	}
	NODE ask(int id,int l,int r,int ql,int qr){
		if(ql<=l&&r<=qr) return t[id].v; spd(id);
		if(qr<=mid) return ask(lc,l,mid,ql,qr);
		if(ql>=mid+1) return ask(rc,mid+1,r,ql,qr);
		return ask(lc,l,mid,ql,qr)+ask(rc,mid+1,r,ql,qr); 
	}
	#undef lc
	#undef rc
	#undef mid
}S;

signed main(){
	
	n=rd,m=rd;
	for(int i=1;i<=n;++i) a[i]=rd;
	
	S.bui(1,1,n);
	for(int i=1,op,l,r,x;i<=m;++i){
		op=rd,l=rd,r=rd; if(op==1) x=rd;
		if(op==1) S.add(1,1,n,l,r,x);
		else printf("%lld\n", max(0ll,S.ask(1,1,n,l,r).mx.b));
	}
	
	return 0;
}

2.[Ynoi2015] 世上最幸福的女孩

离线一下，上 KTT 即可。

995ms

3.The Third Grace

考虑 DP，记 $f_i$ 为考虑了 $\le i$ 的点，选择点 $i$ 的最大代价。有转移

$$f_i=max_{j<i}\{f_j+cnt_{j,i}a_j\}$$

其中 $cnt_{j,i}$ 指 $l \le j \le r < i$ 的区间的数量。

记 $\max$ 里面的为 $g$，扫描线维护 $g$，每次 $i \to i+1$ 时，将 $r=i$ 的区间加入，即 $g_i \gets g_i+a_i(i \in [l,r])$。

用 KTT 实现。

code

参考

KTT 好题