李超线段树
- 用途 : 在平面上插入一个线段或直线，求出与\(x=a\)相交的线段中纵坐标最大的线段编号。
将任务转化成
- 插入一个定义域为\([l,r]\)的一次函数
- 给定\(k\)，求定义域包含\(k\)的所有一次函数中，在\(x=k\)处取值最大的那个，如果有多个函数取值相同，选编号最小的。
注意 : 若线段垂直于\(x\)轴，设线段两端点为\((x,y_0)，(x,y_1)，y_0\le y_1\)，则插入定义域为\([x,x]\)的一次函数\(f(x)=0*x+y_1\)
做法 : 维护每个区间的中点处最高的线段。
假设当前区间原最优线段为\(g\)，新插入的线段为\(f\)
假设当前在中点处
- 若\(f\)更优，则将\(f\)与\(g\)交换。
- 若\(f\)不如\(g\)优
- 若左端点处\(f\)更优，则\(f,g\)必然在左半区间产生交点，所以\(f\)只可能在左半区间优于\(g\)，递归左儿子
- 若右端点处\(f\)更优，同理，递归右儿子
- 若都不优，返回即可
- 若相交，归为\(f\)不如\(g\)
将\(g\)作为区间最优线段。
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
#ifdef LOCAL
FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
// FILE *ErrFile=errfile("err.err");
#else
FILE *Infile = stdin,*OutFile = stdout;
//FILE *ErrFile = stderr;
#endif
const int N = 1e5 + 10,V = 40000;
const db eps = 1e-9;
#define pbi pair<db,int>
#define mk make_pair
struct Line{
db k,b;
inline db get_val(int x){return k*x+b;}
}s[N];int tot = 0;
inline bool cmp(int id1,int id2,int x){
db val1 = s[id1].get_val(x),val2 = s[id2].get_val(x);
if(val1 > val2 + eps) return true;
if(val2 > val1 + eps) return false;
return id1 < id2;
}
inline bool operator < (pbi a,pbi b){
if(a.first + eps < b.first) return true;
if(b.first + eps < a.first) return false;
return a.second > b.second;
}
inline pbi Max(pbi a,pbi b){return a < b?b:a;}
class Segment_Tree{
private:
struct segment_tree{
int ls,rs,val;
#define ls(x) tree[x].ls
#define rs(x) tree[x].rs
#define val(x) tree[x].val
}tree[V<<1];
int cnt = 0;
public:
int rt;
void update(int &k,int l,int r,int sl,int sr,int id){
if(!k) k = ++cnt;
if(sl <= l && r <= sr){
bool cmpl = cmp(id,val(k),l),cmpr = cmp(id,val(k),r);
if(cmpl && cmpr) return val(k) = id,void();
if(!cmpl && !cmpr) return;
int mid = (l+r)>>1;
if(cmp(id,val(k),mid)) swap(val(k),id);
if(cmp(id,val(k),l)) update(ls(k),l,mid,sl,sr,id);
if(cmp(id,val(k),r)) update(rs(k),mid+1,r,sl,sr,id);
}
else{
int mid = (l+r)>>1;
if(sl <= mid) update(ls(k),l,mid,sl,sr,id);
if(sr > mid) update(rs(k),mid+1,r,sl,sr,id);
}
}
pbi query(int k,int l,int r,int x){
if(!k) return mk(-1e18,-1);
pbi res = mk(s[val(k)].get_val(x),val(k));
if(l == r) return res;
int mid = (l+r)>>1;
if(x <= mid) res = Max(res,query(ls(k),l,mid,x));
else res = Max(res,query(rs(k),mid+1,r,x));
return res;
}
}T;
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
int n,lastans = 0;cin>>n;
while(n--){
int op;cin>>op;
if(op){
int x0,y0,x1,y1;
cin>>x0>>y0>>x1>>y1;
x0 = (x0 + lastans - 1) % 39989 + 1;
x1 = (x1 + lastans - 1) % 39989 + 1;
y0 = (y0 + lastans - 1) % 1000000000 + 1;
y1 = (y1 + lastans - 1) % 1000000000 + 1;
if(x0 > x1) swap(x1,x0),swap(y1,y0);
tot++;
if(x0 == x1) s[tot] = {0,max(1.0*y1,1.0*y0)};
else{
db k = 1.0*(y1-y0)/(x1-x0),b = y0 - k*x0;
s[tot] = {k,b};
}
T.update(T.rt,1,40000,x0,x1,tot);
}
else{
int x;cin>>x;x = (x + lastans - 1) % 39989 + 1;
cout<<(lastans = T.query(T.rt,1,40000,x).second)<<'\n';
}
}
}
这道题是全局修改，注意s不是截距,s-k才是
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
#ifdef LOCAL
FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
// FILE *ErrFile=errfile("err.err");
#else
FILE *Infile = stdin,*OutFile = stdout;
//FILE *ErrFile = stderr;
#endif
const int N = 1e5 + 10,V = 5e4 + 10;
const db eps = 1e-9;
struct Line{
db k,b;
inline db get_val(int x){return k*x+b;}
}s[N];int tot = 0;
inline bool cmp(int id1,int id2,int x){
db val1 = s[id1].get_val(x),val2 = s[id2].get_val(x);
if(val1 > val2 + eps) return true;
if(val2 > val1 + eps) return false;
return id1 < id2;
}
inline db Max(db a,db b){
if(a > b + eps) return a;
else return b;
}
class Segment_Tree{
private:
struct segment_tree{
int ls,rs,val;
#define ls(x) tree[x].ls
#define rs(x) tree[x].rs
#define val(x) tree[x].val
}tree[V<<1];
int cnt = 0;
public:
int rt;
void update(int &k,int l,int r,int id){
if(!k) k = ++cnt;
bool cmpl = cmp(id,val(k),l),cmpr = cmp(id,val(k),r);
if(cmpl && cmpr) return val(k) = id,void();
if(!cmpl && ! cmpr) return;
int mid = (l + r)>>1;
if(cmp(id,val(k),mid)) swap(id,val(k));
if(cmp(id,val(k),l)) update(ls(k),l,mid,id);
if(cmp(id,val(k),r)) update(rs(k),mid+1,r,id);
}
db query(int k,int l,int r,int x){
if(!k) return 0;
db res = s[val(k)].get_val(x);
if(l == r) return res;
int mid = (l+r)>>1;
if(x <= mid) res = Max(res,query(ls(k),l,mid,x));
else res = Max(res,query(rs(k),mid+1,r,x));
return res;
}
}T;
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
int n;cin>>n;
while(n--){
string op;cin>>op;
if(op[0] == 'P'){
db b,k;cin>>b>>k;
b -= k;
s[++tot] = {k,b};
T.update(T.rt,1,V-10,tot);
}
else{
int x;cin>>x;
int ans = T.query(T.rt,1,V-10,x);
cout<<ans/100<<'\n';
}
}
}
当然，李超线段树还可以上树(与树剖放在一起)
可以参见[SDOI2016] 游戏
这个坑待填，主要是用处不是很大，像是为了凑在一起而强行凑在一起的。
如果我闲的没事就写了。
重头戏，李超线段树维护凸包，从而维护斜率优化dp
一道例题 : [CEOI2017] Building Bridges
dp式子
\[f_i=\min\{f_j+sum_{i-1}-sum_j+(h_i-h_j)^2\} \]其中\(sum_n=\sum_{i=1}^nw_i\)
简单化一下，就是
\[f_i=-2h_ih_j+f_j+h_j^2-sum_j+sum_{i-1}+h_i^2 \]\(sum_{i-1}+h_i^2\)为常数项，先扔出来不考虑。
我们发现上式就是一个\(y=kx+b\)的形式，其中
\[\begin{cases} y &= f_i\\ k &= -2h_j\\ x &= h_i\\ b &= h_j^2-sum_j+f_j \end{cases}\]那么就是求\(x=h_i\)时的各个已经插入的函数最小值
然后就没了
注意inf要设极大，一开始插入一个\(k=0,b=inf\)的直线，开long long.
点此查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
#ifdef LOCAL
FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
// FILE *ErrFile=errfile("err.err");
#else
FILE *Infile = stdin,*OutFile = stdout;
//FILE *ErrFile = stderr;
#endif
const int N = 1e5 + 10,V = 1e6 + 10;
#define int long long
const int INF = 1e18;
int n,h[N],w[N],f[N];
struct Line{
int k,b;
inline int get_val(int x){return k*x+b;}
}s[N];int tot = 0;
inline bool cmp(int id1,int id2,int x){return s[id1].get_val(x) < s[id2].get_val(x);}
struct Segment_Tree{
private:
struct segment_tree{
int ls,rs,val;
#define ls(x) tree[x].ls
#define rs(x) tree[x].rs
#define val(x) tree[x].val
}tree[V<<1];
int cnt = 0;
public:
int rt;
void update(int &k,int l,int r,int id){
if(!k) k = ++cnt;
bool cmpl = cmp(id,val(k),l),cmpr = cmp(id,val(k),r);
if(cmpl && cmpr) return val(k) = id,void();
if(!cmpl && !cmpr) return;
int mid = (l+r)>>1;
if(cmp(id,val(k),mid)) swap(val(k),id);
if(l == r) return;
if(cmp(id,val(k),l)) update(ls(k),l,mid,id);
if(cmp(id,val(k),r)) update(rs(k),mid+1,r,id);
}
int query(int k,int l,int r,int x){
if(!k) return INF;
int res = s[val(k)].get_val(x);
if(l == r) return res;
int mid = (l+r)>>1;
if(x <= mid) res = min(res,query(ls(k),l,mid,x));
else res = min(res,query(rs(k),mid+1,r,x));
return res;
}
}T;
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cout.tie(nullptr)->sync_with_stdio(false);
cin>>n;
for(int i = 1;i <= n; ++i) cin>>h[i];
for(int i = 1;i <= n; ++i) cin>>w[i];
for(int i = 1;i <= n; ++i) w[i] += w[i - 1];
s[0] = {0,INF};
f[1] = 0;
s[1] = {-2*h[1],h[1]*h[1]-w[1]+f[1]};
T.update(T.rt,0,1e6,1);
for(int i = 2;i <= n; ++i){
f[i] = T.query(1,0,1e6,h[i]) + w[i - 1] + h[i] * h[i];
s[i] = {-2*h[i],h[i]*h[i]-w[i]+f[i]};
T.update(T.rt,0,1e6,i);
}
cout<<f[n]<<'\n';
}