李超线段树例题BZOJ1568、3938

阅读：评论：0

大佬的博客讲的很清晰
李超线段树就是标记永久化维护区间线段最值的数据结构
假设有下列的问题：
给定平面中 n n n条线段，(给出斜率 k k k和截距 b b b，并且知道线段左右端点的横坐标值为多少)，然后 m m m个询问，每次给定 x = x 0 x = x_0 x=x0，问和 x = x 0 x = x_0 x=x0相交的直线中，横坐标值最大为多少。
很明显 n n n和 m m m数据范围大了之后，我们无法暴力，此时看到区间端点，可以想能否用数据结构维护这个东西，即----李超线段树。

复杂度分析：
每次查询是 l o g n logn logn的，
每次插入更新，我们可以把整个权值的域划分为 l o g n logn logn个区间，这里是同一般更新的，但是每个区间内，我们要下放非优势线段，所以又套了一个 l o g log log，总体更新复杂度为 l o g 2 n log^2n log2n，但貌似常数比较小。

维护这个线段可以用结构体和数组实现，我个人偏好结构体一些，比较好写。
这里用结构体里面带 f l a g flag flag来判断是否被标记过了，因为更新牵扯到优势线段的更新，不好操作，另开一个数组来维护

bool flag[N];
struct seg {double k,b;int l,r;seg(){}seg(double _k,double _b,int _l,int _r) {k = _k,b = _b,l = _l,r = _r;}double gety(const int &pos) const {//返回某处的函数值return k * pos + b;}double crossx(const seg &ts) const {//获得两个线段之间的交点return (ts.b - b) / (k - ts.k);}
}tree[N << 2];

更新过程主要是其实就是涉及到 m i d mid mid和端点处 l , r l,r l,r几处的函数值讨论一下，即可完成，画图会更清晰的理解。

void modify(int rt,int l,int r,seg ins) {int mid = (l + r) >> 1;if(l >= ins.l && r <= ins.r) {if(!flag[rt]) {//未被覆盖 直接更新tree[rt] = ins; flag[rt] = true; return ;}(l) - tree[rt].gety(l) > eps && (r) - tree[rt].gety(r) > eps) {//当前插入的线段整体更优tree[rt] = ins; return ;}(l) - tree[rt].gety(l) > eps || (r) - tree[rt].gety(r) > eps) {//任有一段大(mid) - tree[rt].gety(mid) > eps) swap(ins,tree[rt]);//tree保持的是当前最优线段//画画图就理解了ssx(tree[rt]) - mid < -eps) modify(lson,l,mid,ins);else modify(rson,mid+1,r,ins);}return ;}if(ins.l <= mid) modify(lson,l,mid,ins);if(ins.r > mid) modify(rson,mid+1,r,ins);
}

查询就比较普通

double query(int rt,int l,int r,int pos) {if(l == r) return tree[rt].gety(pos);int mid = (l + r) >> 1;double ans = tree[rt].gety(pos);if(pos <= mid) ans = max(ans,query(lson,l,mid,pos));else ans = max(ans,query(rson,mid+1,r,pos));return ans;
}

到此就是大致的粗糙简易模板了

1. 1. 1.BZOJ 1568 裸的模板题

#include <bits/stdc++.h>using namespace std;#define pb emplace_back
#define MP make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define lson rt<<1
#define rson rt<<1|1
#define CLOSE std::ios::sync_with_stdio(false)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-10;
const int ma = 50000;
const int N = 1e5 + 10;
int n;
char op[10];
struct seg {double k,b;int l,r,fg;double gety(const int &pos) const {return k * pos + b;}double crossx(const seg &a) const {return (a.b - b) / (k - a.k);}
}tree[N<<2];
void build(int rt,int l,int r) {tree[rt].k = 0,tree[rt].b = 0,tree[rt].l = 1,tree[rt].r = ma;if(l == r) return ;int mid = (l + r) >> 1;build(lson,l,mid); build(rson,mid+1,r);
}
void modify(int rt,int L,int R,seg k) {if(L >= k.l && R <= k.r) {// cout << rt << ' ' << tree[rt].fg << "****n";(L) - tree[rt].gety(L) > eps && k.gety(R) - tree[rt].gety(R) > eps) {tree[rt] = k; return ;}(L) - tree[rt].gety(L) > eps || k.gety(R) - tree[rt].gety(R) > eps) {int mid = (L + R) >> 1;(mid) - tree[rt].gety(mid) > eps) swap(k,tree[rt]);//tree[rt] 存最优ssx(tree[rt]) - mid < -eps) modify(lson,L,mid,k);else modify(rson,mid+1,R,k);}return ;}int mid = (L + R) >> 1;if(k.l <= mid) modify(lson,L,mid,k);if(k.r > mid) modify(rson,mid+1,R,k);
}
double query(int rt,int l,int r,int pos) {if(l == r) return tree[rt].gety(pos);int mid = (l + r) >> 1;double ans = tree[rt].gety(pos);if(pos <= mid) return max(ans,query(lson,l,mid,pos));else return max(ans,query(rson,mid+1,r,pos));
}int main() {scanf("%d",&n);build(1,1,ma);for(int i = 1;i <= n;i ++) {scanf("%s",&op);if(op[0] == 'P') {double k,b;scanf("%lf%lf",&b,&k);seg tmp;tmp.k = k,tmp.b = b - k,tmp.l = 1,tmp.r = ma;modify(1,1,ma,tmp);}else if(op[0] == 'Q') {int x;scanf("%d",&x);// cout << query(1,1,ma,x) << 'n';int res = (int)(query(1,1,ma,x) / 100);printf("%dn",res);}}return 0;
}
/*
100
Project 5.10200 0.65000
Project 2.76200 1.43000
Query 4
Query 2
Project 3.80200 1.17000
Query 2
Query 3
Query 1
Project 4.58200 0.91000
Project 5.36200 0.39000
*/

2. 2. 2.BZOJ3938 转换一下题意建立李超树模型

思路：对于每个机器人他距离原点的位置 x x x其实是和时间 t t t相关联的，也就是说每个机器人的位置其实就是 x − t x - t x−t的一次函数图像，对应每个机器人的每段 x − t x - t x−t图像都可变为一个线段，而又因为题目求得距离原点的距离最大值，所以我们就建两棵树分别维护整个区间上的最大值和最小值，最后取绝对值大者皆可。
时间范围大，离散化一下，存一下线段，基本变成了模板题。

这道题细节还是有的，注意别忘了存下来最开始的位置也当做线段，每个机器人最后一次操作和时间范围边界点也当做线段，两边都不要遗漏。
因为插入的时候，交点和 m i d mid mid大小符号判断写反了，debug了一天，都快wa吐了…

#include <bits/stdc++.h>using namespace std;#define pb emplace_back
#define MP make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define lson rt<<1
#define rson rt<<1|1
#define CLOSE std::ios::sync_with_stdio(false)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-6;
const int N = 1e5 + 10;
const int M = 6e5 + 10;
bool flag[2][M<<2];
struct seg {ll k,b;int l,r;seg(){}seg(ll _k,ll _b,int _l,int _r) {k = _k,b = _b,l = _l,r = _r;}ll gety(const ll &pos) const {return k * pos + b;}ll crossx(const seg &ts) const {return (ts.b - b) / (k - ts.k); }
}tree[2][M << 2];
int n,m;
ll init[N],lsh[M];
int cnt;
struct Q {ll v,ti;int id;char op[10];
}q[M];
void modifymax(int rt,int l,int r,seg ins) {int mid = (l + r) >> 1;if(l >= ins.l && r <= ins.r) {if(!flag[0][rt]) {tree[0][rt] = ins; flag[0][rt] = true; return ;}(lsh[l]) > tree[0][rt].gety(lsh[l]) && (lsh[r]) > tree[0][rt].gety(lsh[r])) {tree[0][rt] = ins; return ;}(lsh[l]) > tree[0][rt].gety(lsh[l]) || (lsh[r]) > tree[0][rt].gety(lsh[r])) {(lsh[mid]) > tree[0][rt].gety(lsh[mid])) swap(ins,tree[0][rt]);ssx(tree[0][rt]) < lsh[mid]) modifymax(lson,l,mid,ins);else modifymax(rson,mid+1,r,ins);}return ;}if(ins.l <= mid) modifymax(lson,l,mid,ins);if(ins.r > mid) modifymax(rson,mid+1,r,ins);
}
void modifymin(int rt,int l,int r,seg ins) {int mid = (l + r) >> 1;if(l >= ins.l && r <= ins.r) {if(!flag[1][rt]) {tree[1][rt] = ins; flag[1][rt] = true; return ;}(lsh[l]) < tree[1][rt].gety(lsh[l]) && (lsh[r]) < tree[1][rt].gety(lsh[r])) {tree[1][rt] = ins; return ;}(lsh[l]) < tree[1][rt].gety(lsh[l]) || (lsh[r]) < tree[1][rt].gety(lsh[r])) {(lsh[mid]) < tree[1][rt].gety(lsh[mid])) swap(ins,tree[1][rt]);ssx(tree[1][rt]) < lsh[mid]) modifymin(lson,l,mid,ins);else modifymin(rson,mid+1,r,ins);}return ;}if(ins.l <= mid) modifymin(lson,l,mid,ins);if(ins.r > mid) modifymin(rson,mid+1,r,ins);
}
ll res1,res2;
ll qmax(int rt,int l,int r,int pos) {// if(flag[0][rt]) res1 = max(res1,tree[0][rt].gety(lsh[pos]));if(l == r) return tree[0][rt].gety(lsh[pos]);int mid = (l + r) >> 1;ll ans = tree[0][rt].gety(lsh[pos]);if(pos <= mid) ans = max(ans,qmax(lson,l,mid,pos));else ans = max(ans,qmax(rson,mid+1,r,pos));return ans;
}ll qmin(int rt,int l,int r,int pos) {// if(flag[1][rt]) res2 = min(res2,tree[1][rt].gety(lsh[pos]));if(l == r) return tree[1][rt].gety(lsh[pos]);int mid = (l + r) >> 1;ll ans = tree[1][rt].gety(lsh[pos]);if(pos <= mid) return min(ans,qmin(lson,l,mid,pos));else return min(ans,qmin(rson,mid+1,r,pos));
}bool vis[N];
ll lastk[N],lastb[N],lastt[N];
int getid(ll x) {return lower_bound(lsh + 1,lsh + 1 + cnt,x) - lsh;
}int main() {scanf("%d%d",&n,&m);for(int i = 1;i <= n;i ++) {scanf("%lld",&lastb[i]);}for(int i = 1;i <= m;i ++) {scanf("%lld%s",&q[i].ti,q[i].op);lsh[++cnt] = q[i].ti; if(q[i].op[0] == 'c') {scanf("%d%lld",&q[i].id,&q[i].v);}}lsh[++cnt] = 0;//用于插入初始值sort(lsh + 1,lsh + 1 + cnt);cnt = unique(lsh + 1,lsh + 1 + cnt) - lsh - 1;for(int i = 1;i <= m;i ++) {if(q[i].op[0] == 'c') {int no = q[i].id;// vis[no] = 1;int l = getid(lastt[no]),r = getid(q[i].ti);// cout << lastk[no] << ' ' << lastb[no] << ' ' << l << ' ' << r << "***n";modifymax(1,1,cnt,seg(lastk[no],lastb[no],l,r));modifymin(1,1,cnt,seg(lastk[no],lastb[no],l,r));lastb[no] = lastb[no] + q[i].ti * (lastk[no] - q[i].v);lastk[no] = q[i].v;lastt[no] = q[i].ti;}}for(int i = 1;i <= n;i ++) {int l = getid(lastt[i]);modifymax(1,1,cnt,seg(lastk[i],lastb[i],l,cnt));modifymin(1,1,cnt,seg(lastk[i],lastb[i],l,cnt));}for(int i = 1;i <= m;i ++) {if(q[i].op[0] == 'q') {int no = q[i].id;int time = getid(q[i].ti);res1 = res2 = 0;res1 = qmax(1,1,cnt,time); res2 = qmin(1,1,cnt,time);// ll res1 = qmax(1,1,cnt,time); ll res2 = qmin(1,1,cnt,time);// cout << res1 << ' ' << res2 << 'n';ll res = max(res1,-res2);printf("%lldn",res);}}return 0;
}
/*
4 5
-20 0 20 100
10 command 1 10
20 command 3 -10
30 query
40 command 1 -30
50 query
*/

数组标记线段实现：

#include <bits/stdc++.h>using namespace std;#define pb emplace_back
#define MP make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define lson rt<<1
#define rson rt<<1|1
#define CLOSE std::ios::sync_with_stdio(false)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-6;
const int N = 1e5 + 10;
const int M = 6e5 + 10;
bool flag[2][M<<2];
ll tagk[2][M<<2],tagb[2][M<<2];
int n,m;
ll init[N],lsh[M];
int cnt;
struct Q {ll v,ti;int id;char op[10];
}q[M];
ll cal(ll k,ll b,ll x) {return k * x + b;
}
void modifymax(int rt,int l,int r,int L,int R,ll k,ll b) {int mid = (l + r) >> 1;if(l >= L && r <= R) {if(!flag[0][rt]) {tagk[0][rt] = k,tagb[0][rt] = b,flag[0][rt] = true; return ;}// if(cal(k,b,lsh[l]) > cal(tagk[0][rt],tagb[0][rt],lsh[l]) && cal(k,b,lsh[r]) > cal(tagk[0][rt],tagb[0][rt],lsh[r])) {ll f1 = k * lsh[l] + b,f2 = tagk[0][rt] * lsh[l] + tagb[0][rt];ll f3 = k * lsh[r] + b,f4 = tagk[0][rt] * lsh[r] + tagb[0][rt];if(f1 <= f2 && f3 <= f4) return ;if(f1 >= f2 && f3 >= f4) {tagk[0][rt] = k,tagb[0][rt] = b; return ;}ll crossx = (tagb[0][rt] - b) / (k - tagk[0][rt]);if(f1 >= f2) {if(crossx <= lsh[mid]) modifymax(lson,l,mid,L,R,k,b);else { modifymax(rson,mid+1,r,L,R,tagk[0][rt],tagb[0][rt]); tagk[0][rt] = k,tagb[0][rt] = b; }}else {if(crossx > lsh[mid]) modifymax(rson,mid+1,r,L,R,k,b);else { modifymax(lson,l,mid,L,R,tagk[0][rt],tagb[0][rt]); tagk[0][rt] = k,tagb[0][rt] = b; }		}return ;}if(L <= mid) modifymax(lson,l,mid,L,R,k,b);if(R > mid) modifymax(rson,mid+1,r,L,R,k,b);
}
void modifymin(int rt,int l,int r,int L,int R,ll k,ll b) {int mid = (l + r) >> 1;if(l >= L && r <= R) {if(!flag[1][rt]) {tagk[1][rt] = k,tagb[1][rt] = b,flag[1][rt] = true; return ; }ll f1 = k * lsh[l] + b,f2 = tagk[1][rt] * lsh[l] + tagb[1][rt];ll f3 = k * lsh[r] + b,f4 = tagk[1][rt] * lsh[r] + tagb[1][rt];if(f1 >= f2 && f3 >= f4) return ;if(f1 <= f2 && f3 <= f4) {tagk[1][rt] = k,tagb[1][rt] = b; return ;}ll crossx = (tagb[1][rt] - b) / (k - tagk[1][rt]);if(f1 <= f2) {if(crossx <= lsh[mid]) modifymin(lson,l,mid,L,R,k,b);else { modifymin(rson,mid+1,r,L,R,tagk[1][rt],tagb[1][rt]); tagk[1][rt] = k,tagb[1][rt] = b; }}else {if(crossx > lsh[mid]) modifymin(rson,mid+1,r,L,R,k,b);else { modifymin(lson,l,mid,L,R,tagk[1][rt],tagb[1][rt]); tagk[1][rt] = k,tagb[1][rt] = b; }		}return ;}if(L <= mid) modifymin(lson,l,mid,L,R,k,b);if(R > mid) modifymin(rson,mid+1,r,L,R,k,b);
}
ll res1,res2;
void qmax(int rt,int l,int r,int pos) {if(flag[0][rt]) res1 = max(res1,tagk[0][rt] * lsh[pos] + tagb[0][rt]);if(l == r) return ;//cal(tagk[0][rt],tagb[0][rt],lsh[pos]);int mid = (l + r) >> 1;if(pos <= mid) qmax(lson,l,mid,pos);else qmax(rson,mid+1,r,pos);
}
void qmin(int rt,int l,int r,int pos) {if(flag[1][rt]) res2 = min(res2,tagk[1][rt] * lsh[pos] + tagb[1][rt]);if(l == r) return ;int mid = (l + r) >> 1;if(pos <= mid) qmin(lson,l,mid,pos);else qmin(rson,mid+1,r,pos);
}
bool vis[N];
ll lastk[N],lastb[N],lastt[N];
int getid(ll x) {return lower_bound(lsh + 1,lsh + 1 + cnt,x) - lsh;
}int main() {scanf("%d%d",&n,&m);ll ma = 0;for(int i = 1;i <= n;i ++) {scanf("%lld",&lastb[i]);ma = max(ma,lastb[i]);}for(int i = 1;i <= m;i ++) {scanf("%lld%s",&q[i].ti,q[i].op);lsh[++cnt] = q[i].ti; if(q[i].op[0] == 'c') {scanf("%d%lld",&q[i].id,&q[i].v);}}lsh[++cnt] = 0;//用于插入初始值sort(lsh + 1,lsh + 1 + cnt);cnt = unique(lsh + 1,lsh + 1 + cnt) - lsh - 1;for(int i = 1;i <= m;i ++) {if(q[i].op[0] == 'c') {int no = q[i].id;int l = getid(lastt[no]),r = getid(q[i].ti);// cout << lastk[no] << ' ' << lastb[no] << ' ' << l << ' ' << r << "***n";modifymax(1,1,cnt,l,r,lastk[no],lastb[no]);modifymin(1,1,cnt,l,r,lastk[no],lastb[no]);lastb[no] = lastb[no] + q[i].ti * (lastk[no] - q[i].v);lastk[no] = q[i].v;lastt[no] = q[i].ti;}}for(int i = 1;i <= n;i ++) {int l = getid(lastt[i]);// cout << lastk[i] << ' ' << lastb[i] << ' ' << l << ' ' << cnt << "***n";modifymax(1,1,cnt,l,cnt,lastk[i],lastb[i]);modifymin(1,1,cnt,l,cnt,lastk[i],lastb[i]);}for(int i = 1;i <= m;i ++) {if(q[i].op[0] == 'q') {int no = q[i].id;int time = getid(q[i].ti);res1 = res2 = 0;qmax(1,1,cnt,time);qmin(1,1,cnt,time);// ll res1 = qmax(1,1,cnt,time); ll res2 = qmin(1,1,cnt,time);ll res = max(res1,-res2);printf("%lldn",res);}}return 0;
}
/*
4 5
-20 0 20 100
10 command 1 10
20 command 3 -10
30 query
40 command 1 -30
50 query
*/