李超线段树合集

谁践踏了优雅 2023-10-11 13:28 40阅读 0赞

李超线段树

用来维护二维平面上很多条线段(直线)在x = x0上的最值问题

定义：

1.永久化标记：即线段树标记不删除，每个结点维护的也不一定是最优的信息，需要查询的时候一路统计标记达到最优

2.优势线段：李超树每个节点含有一个优势线段，意为完全覆盖当前区间且在当前区间mid处相比于其他该位置线段最大(小)的线段，李超树的id记录的即为当前的优势线段

3.核心思想：假设维护最大值，每次插入线段时，如果斜率较大的线段为优势线段，则斜率较小的线段只有在左子树才有机会比优势线段大

如果斜率较小的线段为优势线段，则较大的线段只有在右子树才能翻盘

修改(log(n))²(但是常数不大),查询log(n)

1.luogu4254

操作1.增加一条斜率为P,起始点为S的直线

操作2.询问k点上所有直线的最大值

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

2.luogu4097

1.  在平面上加入一条线段。记第 i 条被插入的线段的标号为 i
2.  给定一个数 k,询问与直线 x = k 相交的线段中，交点最靠上的线段的编号。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

3.luogu p4069

题意：树链上每个点添加形如a \* dis + b的值的一个点，每次查询树链上最小点

树链剖分 + 李超树

关于李超树的区间查询：

用一个Min维护区间最小值,Min的组成来源为两个子树的Min的较小值和本结点优势线段在两个端点的较小值

如果查询包含整个区间则直接返回Min，否则来源为正常区间最小值查找 + 本结点优势线段在查询两端的较小值

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <map>
    #include <set>
    #include <ctime>
    #include <cmath>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <string>
    #include <bitset>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <sstream>
    #include <iostream>
    #include <algorithm>
    #include <functional>
    using namespace std;
    #define For(i, x, y) for(int i=x;i<=y;i++)  
    #define _For(i, x, y) for(int i=x;i>=y;i--)
    #define Mem(f, x) memset(f,x,sizeof(f))  
    #define Sca(x) scanf("%d", &x)
    #define Sca2(x,y) scanf("%d%d",&x,&y)
    #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
    #define Scl(x) scanf("%lld",&x)  
    #define Pri(x) printf("%d\n", x)
    #define Prl(x) printf("%lld\n",x)  
    #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
    #define LL long long
    #define ULL unsigned long long  
    #define mp make_pair
    #define PII pair<int,int>
    #define PIL pair<int,long long>
    #define PLL pair<long long,long long>
    #define pb push_back
    #define fi first
    #define se second 
    typedef vector<int> VI;
    int read(){
         int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){
         if (c == '-') f = -1;c = getchar();}
    while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
    const double PI = acos(-1.0);
    const double eps = 1e-9;
    const int maxn = 1e5 + 10;
    const LL INF = 123456789123456789;
    const int mod = 1e9 + 7; 
    int N,M,K;
    struct Edge{
        int to,next;
        LL dis;
    }edge[maxn * 2];
    int head[maxn],tot;
    void init(){
        for(int i = 0 ; i <= N ; i ++) head[i] = -1;
        tot = 0;
    }
    void add(int u,int v,LL w){
        edge[tot].to = v;
        edge[tot].next = head[u];
        edge[tot].dis = w;
        head[u] = tot++;
    }
    int dep[maxn],top[maxn],fa[maxn],pos[maxn];
    int sz[maxn],son[maxn],to[maxn];
    LL dis[maxn];
    void dfs1(int t,int la){
        sz[t] = 1; son[t] = t;
        int heavy = 0;
        for(int i = head[t]; ~i ; i = edge[i].next){
            int v = edge[i].to;
            if(v == la) continue;
            dis[v] = dis[t] + edge[i].dis;
            dep[v] = dep[t] + 1;
            fa[v] = t;
            dfs1(v,t);
            if(sz[v] > heavy){
                heavy = sz[v];
                son[t] = v;
            }
            sz[t] += sz[v];
        }
    }
    int cnt;
    void dfs2(int t,int la){
        top[t] = la;
        pos[t] = ++cnt; to[cnt] = t;
        if(son[t] == t) return;
        dfs2(son[t],la);
        for(int i = head[t]; ~i ; i = edge[i].next){
            int v = edge[i].to;
            if((fa[t] == v) || (v == son[t])) continue;
            dfs2(v,v);
        }
    }
    LL S[maxn * 2],P[maxn * 2];
    int ttt;
    struct Tree{
        int l,r,id;
        LL Min;
    }tree[maxn << 2];
    void Pushup(int t){
        if(tree[t].l == tree[t].r) return;
        tree[t].Min = min(tree[t].Min,min(tree[t << 1].Min,tree[t << 1 | 1].Min));
    }
    void Build(int t,int l,int r){
        tree[t].l = l; tree[t].r = r;
        tree[t].id = 0; tree[t].Min = INF;
        if(l == r) return;
        int m = l + r >> 1;
        Build(t << 1,l,m); Build(t << 1 | 1,m + 1,r);
    }
    void update(int t,int l,int r,int id){
        int m = tree[t].l + tree[t].r >> 1;
        if(l <= tree[t].l && tree[t].r <= r){
            int &a = id; int &b = tree[t].id;
            if(P[a] > P[b]) swap(a,b);
            if(dis[to[m]] * P[a] + S[a] < dis[to[m]] * P[b] + S[b]){
                swap(a,b);
                if(tree[t].l != tree[t].r) update(t << 1,l,r,id);
            }else{
                if(tree[t].l != tree[t].r) update(t << 1 | 1,l,r,id);
            }
            Pushup(t);
            tree[t].Min = min(tree[t].Min,dis[to[tree[t].l]] * P[b] + S[b]);
            tree[t].Min = min(tree[t].Min,dis[to[tree[t].r]] * P[b] + S[b]);
            return;
        }
        if(r <= m) update(t << 1,l,r,id);
        else if(l > m) update(t << 1 | 1,l,r,id);
        else{
            update(t << 1,l,m,id);
            update(t << 1 | 1,m + 1,r,id);
        }
        Pushup(t);
    }
    LL query(int t,int l,int r){
        if(l <= tree[t].l && tree[t].r <= r) return tree[t].Min;
        int m = (tree[t].l + tree[t].r) >> 1;
        LL ans = INF;
        ans = min(ans,dis[to[l]] * P[tree[t].id] + S[tree[t].id]);
        ans = min(ans,dis[to[r]] * P[tree[t].id] + S[tree[t].id]);
        if(r <= m) return min(ans,query(t << 1,l,r));
        else if(l > m) return min(ans,query(t << 1 | 1,l,r));
        else{
            return min(ans,min(query(t << 1,l,m),query(t << 1 | 1,m + 1,r)));
        }
    }
    int lca(int x,int y){
        while(top[x] != top[y]) dep[top[x]] > dep[top[y]]?x = fa[top[x]]:y = fa[top[y]];
        return dep[x] < dep[y]?x:y;
    }
    void update(int u,int v,int id){
        while(top[u] != top[v]){
            if(dep[top[u]] < dep[top[v]]) swap(u,v);
            update(1,pos[top[u]],pos[u],id);
            u = fa[top[u]];
        }
        if(dep[u] > dep[v]) swap(u,v);
        update(1,pos[u],pos[v],id); 
    }
    LL query(int u,int v){
        LL ans = INF;
        while(top[u] != top[v]){
            if(dep[top[u]] < dep[top[v]]) swap(u,v);
            ans = min(ans,query(1,pos[top[u]],pos[u]));
            u = fa[top[u]];
        }
        if(dep[u] > dep[v]) swap(u,v);
        ans = min(ans,query(1,pos[u],pos[v]));
        return ans;
    }
    int main(){
        Sca2(N,M); init();
        P[0] = 0; S[0] = INF;
        for(int i = 1; i <= N - 1; i ++){
            int u = read(),v = read();
            LL w = read();
            add(u,v,w); add(v,u,w);
        }
        int root = 1;
        dfs1(root,-1); cnt = 0;
        dfs2(root,root);
        Build(1,1,N); ttt = 0;
        while(M--){
            int op = read();
            if(op == 1){
                int s = read(),t = read();
                LL a = read(),b = read();
                int x = lca(s,t);
                ttt++; P[ttt] = -a; S[ttt] = a * dis[s] + b; 
                update(s,x,ttt);
                ttt++; P[ttt] = a; S[ttt] = a * (dis[s] - 2 * dis[x]) + b;
                update(x,t,ttt);
            }else{
                int s = read(),t = read();
                Prl(query(s,t));
            }
        }
        return 0;
    }

4.2019ICPC南京网络赛I

比赛的时候一直想寻找一个维护斜率最大值的数据结构，结果没有想到

看了题解才知道真有直接维护这个的数据结构

李超树的下标代表的是洗衣机花费的时间，每个x上的最大值是当前后缀需要花费的最大值时间

动态加入后缀 维护最大值即可

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

转载于:https://www.cnblogs.com/Hugh-Locke/p/11447725.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif