Luogu4069 SDOI2016 游戏树链剖分、李超线段树

每一次加的是一个一次函数，一些呈一次函数的线段求最小值，显然用到李超线段树。

然后把维护序列的李超线段树强行上树，就直接套上树剖就可以了。

至于李超树如何区间查询，因为一次函数线段的最小值一定会取在两端，所以对于每一个点维护它和它的子树中所有线段的最低点，递归的时候如果当前区间被询问区间包含就直接返回维护的最低点，对于经过的线段再考虑它是否能够更新答案。

复杂度\(O(nlog^3n)\)可能自带小常数就过了吧……

#include<bits/stdc++.h>

//this code is written by Itst

using namespace std;

int read(){

    int a = 0; bool f = 0; char c = getchar();

    while(!isdigit(c)){f = c == '-'; c = getchar();}

    while(isdigit(c)){a = a * 10 + c - 48; c = getchar();}

    return f ? -a : a;

}

#define int long long

#define ld long double

struct line{

    int k , b;

    line(int _k = 0 , int _b = 123456789123456789ll) : k(_k) , b(_b){}

};

ld sect(line a , line b){return 1.0 * (a.b - b.b) / (b.k - a.k);}

const int _ = 1e5 + 7;

struct Edge{

    int end , upEd , w;

}Ed[_ << 1];

int head[_] , fa[_] , dep[_] , len[_] , dfn[_] , ind[_] , top[_] , sz[_] , son[_];

int N , M , cntEd , ts;

void addEd(int a , int b , int c){

    Ed[++cntEd] = (Edge){b , head[a] , c};

    head[a] = cntEd;

}

void dfs1(int x , int p){

    sz[x] = 1; fa[x] = p; dep[x] = dep[p] + 1;

    for(int i = head[x] ; i ; i = Ed[i].upEd)

        if(Ed[i].end != p){

            len[Ed[i].end] = len[x] + Ed[i].w;

            dfs1(Ed[i].end , x); sz[x] += sz[Ed[i].end];

            if(sz[Ed[i].end] > sz[son[x]]) son[x] = Ed[i].end;

        }

}

void dfs2(int x , int t){

    top[x] = t; ind[dfn[x] = ++ts] = x;

    if(!son[x]) return;

    dfs2(son[x] , t);

    for(int i = head[x] ; i ; i = Ed[i].upEd)

        if(Ed[i].end != fa[x] && Ed[i].end != son[x])

            dfs2(Ed[i].end , Ed[i].end);

}

namespace segTree{

    line arr[_ << 2]; int mn[_ << 2] , pl[_ << 2] , pr[_ << 2];

#define mid ((l + r) >> 1)

#define lch (x << 1)

#define rch (x << 1 | 1)

    void init(int x , int l , int r){

        pl[x] = l; pr[x] = r; mn[x] = 123456789123456789ll;

        if(l != r){

            init(lch , l , mid); init(rch , mid + 1, r);

        }

    }

    int calc(line A , int x){return A.k * x + A.b;}

    void up(int x){

        if(pl[x] != pr[x])

            mn[x] = min(min(mn[lch] , mn[rch]) , min(calc(arr[x] , len[ind[pl[x]]]) , calc(arr[x] , len[ind[pr[x]]])));

        else

            mn[x] = min(calc(arr[x] , len[ind[pl[x]]]) , calc(arr[x] , len[ind[pr[x]]]));

    }

    void insert(int x , int l , int r , int L , int R , line now){

        if(l >= L && r <= R){

            if(arr[x].k == now.k)

                return (void)(arr[x] = arr[x].b < now.b ? arr[x] : now) , up(x);

            ld pos = sect(arr[x] , now);

            if(arr[x].k > now.k) swap(arr[x] , now);

            if(pos > len[ind[r]]) arr[x] = now;

            else

                if(!(pos < len[ind[l]]))

                    if(pos >= len[ind[mid]]){

                        swap(arr[x] , now);

                        if(l != r) insert(rch , mid + 1 , r , L , R , now);

                    }

                    else

                        if(l != r) insert(lch , l , mid , L , R , now);

            return up(x);

        }

        if(mid >= L) insert(lch , l , mid , L , R , now);

        if(mid < R) insert(rch , mid + 1 , r , L , R , now);

        up(x);

    }

    int query(int x , int l , int r , int L , int R){

        if(l >= L && r <= R) return mn[x];

        int ans = 123456789123456789ll;

        if(mid >= L) ans = query(lch , l , mid , L , R);

        if(mid < R) ans = min(ans , query(rch , mid + 1 , r , L , R));

        return min(ans , min(calc(arr[x] , len[ind[max(l , L)]]) , calc(arr[x] , len[ind[min(r , R)]])));

    }

}

int LCA(int x , int y){

    int tx = top[x] , ty = top[y];

    while(tx != ty){

        if(dep[tx] < dep[ty]){swap(tx , ty); swap(x , y);}

        x = fa[tx]; tx = top[x];

    }

    return dfn[x] > dfn[y] ? y : x;

}

void modify(int x , int y , int a , int b){

    int tx = top[x] , ty = top[y] , flgx = -1 , flgy = 1 , lx = 0 , ly = len[x] + len[y] - 2 * len[LCA(x , y)];

    while(tx != ty){

        if(dep[tx] < dep[ty]){swap(tx , ty); swap(flgx , flgy); swap(x , y); swap(lx , ly);}

        int _k = flgx * a , _b = lx * a + b - len[x] * _k;

        segTree::insert(1 , 1 , N , dfn[tx] , dfn[x] , line(_k , _b));

        lx += -flgx * (len[x] - len[fa[tx]]);

        x = fa[tx]; tx = top[x];

    }

    if(dep[x] < dep[y]){swap(flgx , flgy); swap(x , y); swap(lx , ly);}

    int _k = flgx * a , _b = lx * a + b - len[x] * _k;

    segTree::insert(1 , 1 , N , dfn[y] , dfn[x] , line(_k , _b));

}

int work(int x , int y){

    int tx = top[x] , ty = top[y] , ans = 123456789123456789ll;

    while(tx != ty){

        if(dep[tx] < dep[ty]){swap(tx , ty); swap(x , y);}

        ans = min(ans , segTree::query(1 , 1 , N , dfn[tx] , dfn[x]));

        x = fa[tx]; tx = top[x];

    }

    return min(ans , segTree::query(1 , 1 , N , min(dfn[x] , dfn[y]) , max(dfn[x] , dfn[y])));

}

signed main(){

#ifndef ONLINE_JUDGE

    freopen("in","r",stdin);

    freopen("out","w",stdout);

#endif

    N = read(); M = read();

    for(int i = 1 ; i < N ; ++i){

        int a = read() , b = read() , c = read();

        addEd(a , b , c); addEd(b , a , c);

    }

    dfs1(1 , 0); dfs2(1 , 1); segTree::init(1 , 1 , N);

    for(int i = 1 ; i <= M ; ++i)

        if(read() == 1){

            int s = read() , t = read() , a = read() , b = read();

            modify(s , t , a , b);

        }

        else{

            int s = read() , t = read();

            printf("%lld\n" , work(s , t));

        }

    return 0;

}

巴特西

Luogu4069 SDOI2016 游戏树链剖分、李超线段树

最新文章

热门文章

巴特西

Luogu4069 SDOI2016 游戏 树链剖分、李超线段树

最新文章

热门文章

Luogu4069 SDOI2016 游戏树链剖分、李超线段树