Aoj 2450 Do use segment tree【树链剖分】

叁歲伎倆 2022-08-09 01:50 48阅读 0赞

树链剖分，个人因为姿势太丑就不发代码了。  
维护四个域。  
区间和，右端最大连续值，左端最大连续值，答案。

注意的是，2操作是一个有序的操作，因此需要求一个LCA，从某点更新到LCA，再从LCA更新到另一个点。当然也有不要LCA的方法，就是通过判断深度，不swap，直接旋转地找。

// whn6325689
    // Mr.Phoebe
    // http://blog.csdn.net/u013007900
    #include <algorithm>
    #include <iostream>
    #include <iomanip>
    #include <cstring>
    #include <climits>
    #include <complex>
    #include <fstream>
    #include <cassert>
    #include <cstdio>
    #include <bitset>
    #include <vector>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <ctime>
    #include <set>
    #include <map>
    #include <cmath>
    #include <functional>
    #include <numeric>
    #pragma comment(linker, "/STACK:1024000000,1024000000")
    
    
    using namespace std;
    
    #define eps 1e-9
    #define PI acos(-1.0)
    #define INF 0x3f3f3f3f
    #define LLINF 1LL<<62
    #define speed std::ios::sync_with_stdio(false);
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    typedef pair<ll, ll> pll;
    typedef complex<ld> point;
    typedef pair<int, int> pii;
    typedef pair<pii, int> piii;
    typedef vector<int> vi;
    
    #define CLR(x,y) memset(x,y,sizeof(x))
    #define CPY(x,y) memcpy(x,y,sizeof(x))
    #define clr(a,x,size) memset(a,x,sizeof(a[0])*(size))
    #define cpy(a,x,size) memcpy(a,x,sizeof(a[0])*(size))
    #define debug(a) cout << #a" = " << (a) << endl;
    #define debugarry(a, n) for (int i = 0; i<(n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }
    
    #define mp(x,y) make_pair(x,y)
    #define pb(x) push_back(x)
    #define lowbit(x) (x&(-x))
    
    #define MID(x,y) (x+((y-x)>>1))
    #define getidx(l,r) (l+r | l!=r)
    #define ls getidx(l,mid)
    #define rs getidx(mid+1,r)
    #define lson l,mid
    #define rson mid+1,r
    
    template<class T>
    inline bool read(T &n)
    {
        T x = 0, tmp = 1;
        char c = getchar();
        while((c<'0' || c > '9') && c != '-' && c != EOF) c = getchar();
        if(c == EOF) return false;
        if(c == '-') c = getchar(), tmp = -1;
        while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
        n = x*tmp;
        return true;
    }
    template <class T>
    inline void write(T n)
    {
        if(n<0)
        {
            putchar('-');
            n = -n;
        }
        int len = 0,data[20];
        while(n)
        {
            data[len++] = n%10;
            n /= 10;
        }
        if(!len) data[len++] = 0;
        while(len--) putchar(data[len]+48);
    }
    //-----------------------------------
    const int MAXN = 200020;
    
    struct Node
    {
        ll sumv, suml, sumr, maxv;
        ll sett;
        Node()
        {
            sumv = 0;
            sett = INF;
            suml = sumr = maxv = -INF;
        }
        void setv(ll x, ll num)
        {
            sett = x;
            sumv = x*num;
            if(x >= 0)
                suml = sumr = maxv = sumv;
            else
                suml = sumr = maxv = x;
        }
        Node operator + (const Node &rhs) const
        {
            Node c;
            c.sett = INF;
            c.sumv = sumv + rhs.sumv;
            c.suml = max(suml, sumv+rhs.suml);
            c.sumr = max(sumr+rhs.sumv, rhs.sumr);
            c.maxv = max(maxv, rhs.maxv);
            c.maxv = max(c.maxv, sumr+rhs.suml);
            return c;
        }
    } p[MAXN<<1];
    
    vector<int> G[MAXN];
    int num[MAXN], top[MAXN], dep[MAXN];
    int dfn[MAXN], b[MAXN], fa[MAXN], dfs_clock;
    int que[MAXN], iii[MAXN], a[MAXN];
    int n, q, ql, qr, _v;
    
    void gao()
    {
        int ft = 0, rear = 0;
        que[rear++] = 1;
        fa[1] = 0;
        dep[1] = 1;
        while(ft < rear)
        {
            int u = que[ft++];
            for(int i = 0; i < G[u].size(); i++)
            {
                int v = G[u][i];
                if(v == fa[u]) continue;
                fa[v] = u;
                que[rear++] = v;
                dep[v] = dep[u]+1;
            }
        }
        memset(num, 0, sizeof num);
        for(int i = n-1; i >= 0; i--)
        {
            int u = que[i];
            num[u]++;
            num[fa[u]] += num[u];
        }
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j < G[i].size(); j++) if(G[i][j] != fa[i])
                    if(G[i][0] == fa[i] || num[G[i][j]] > num[G[i][0]])
                        swap(G[i][0], G[i][j]);
        }
        top[1] = 1;
        for(int i = 1; i < n; i++)
        {
            int u = que[i];
            if(G[fa[u]][0] == u) top[u] = top[fa[u]];
            else top[u] = u;
        }
        memset(iii, 0, sizeof iii);
        ft = 0;
        dfs_clock = 0;
        que[++ft] = 1;
        dfn[1] = ++dfs_clock;
        b[1] = a[1];
        while(ft)
        {
            int u = que[ft];
            if(iii[u] >= G[u].size()) ft--;
            else if(G[u][iii[u]] == fa[u]) iii[u]++;
            else
            {
                int v = G[u][iii[u]];
                que[++ft] = v;
                dfn[v] = ++dfs_clock;
                b[dfn[v]] = a[v];
                iii[u]++;
            }
        }
    }
    
    void print(int a[])
    {
        for(int i = 1; i <= n; i++)
            printf("%d ", a[i]);
        puts("");
    }
    
    void test()
    {
        print(fa);
        print(top);
        print(dep);
        print(dfn);
        print(b);
        print(num);
    }
    
    void build(int l, int r)
    {
        int idx=getidx(l,r),mid=MID(l,r);
        p[idx].sett=INF;
        if(l==r)
        {
            p[idx].setv(b[l], 1);
            return;
        }
        build(lson);
        build(rson);
        p[idx]=p[ls]+p[rs];
    }
    
    void push_down(int l, int r)
    {
        int idx=getidx(l,r),mid=MID(l,r);
        if(p[idx].sett!=INF)
        {
            p[ls].setv(p[idx].sett,mid-l+1);
            p[rs].setv(p[idx].sett,r-mid);
            p[idx].sett=INF;
        }
    }
    
    void update(int l,int r,int L,int R)
    {
        int idx=getidx(l,r),mid=MID(l,r);
        if(L<=l && r<=R)
        {
            p[idx].setv(_v, r-l+1);
            return;
        }
        push_down(l,r);
        if(L<=mid) update(lson,L,R);
        if(R>mid) update(rson,L,R);
        p[idx]=p[ls]+p[rs];
    }
    
    
    Node query(int l, int r,int L,int R)
    {
        int idx=getidx(l,r),mid=MID(l,r);
        if(L==l && r==R)
            return p[idx];
        push_down(l,r);
        if(R<=mid) return query(lson,L,R);
        if(L>mid)  return query(rson,L,R);
        return query(lson,L,mid)+query(rson,mid+1,R);
    }
    
    int lca(int u, int v)
    {
        while(top[u] != top[v])
        {
            if(dep[top[u]] < dep[top[v]]) swap(u, v);
            u=fa[top[u]];
        }
        return dep[u] > dep[v] ? v : u;
    }
    
    void change(int u, int v, int c)
    {
        int t=lca(u, v);
        _v=c;
        while(top[u] != top[t])
        {
            update(1,n,dfn[top[u]],dfn[u]);
            u=fa[top[u]];
        }
        update(1,n,dfn[t],dfn[u]);
    
        while(top[v] != top[t])
        {
            update(1,n,dfn[top[v]],dfn[v]);
            v=fa[top[v]];
        }
        if(v != t)
            update(1,n,dfn[t]+1,dfn[v]);
    }
    
    ll outputquery(int u, int v)
    {
        if(dfn[u] > dfn[v]) swap(u, v);
        int t=lca(u, v);
        if(t==u) swap(u, v);
    
        Node L,R;
        while(top[u] != top[t])
        {
            L=query(1,n,dfn[top[u]],dfn[u])+L;
            u=fa[top[u]];
        }
        L=query(1,n,dfn[t],dfn[u])+L;
    
        while(top[v] != top[t])
        {
            R=query(1,n,dfn[top[v]],dfn[v])+R;
            v=fa[top[v]];
        }
        if(v!=t)
            R=R+query(1,n,dfn[t]+1,dfn[v]);
    
        return max(max(L.maxv, R.maxv), L.suml+R.suml);
    }
    
    int main()
    {
        //freopen("data.txt","r",stdin);
        int op, u, v, c;
        while(~scanf("%d %d",&n,&q))
        {
            for(int i=1; i<=n; i++)
            {
                read(a[i]);
                G[i].clear();
            }
            for(int i=1; i < n; i++)
            {
                read(u),read(v);
                G[u].push_back(v);
                G[v].push_back(u);
            }
            gao();
            build(1,n);
            while(q--)
            {
                read(op),read(u),read(v),read(c);
                if(op==1)
                    change(u,v,c);
                else
                    write(outputquery(u,v)),putchar('\n');
            }
        }
        return 0;
    }

不要求LCA的方法。

#include <bits/stdc++.h>
    #define MAXN 300500
    #define lson getidx(l, mid)
    #define rson getidx(mid + 1, r)
    
    using namespace std;
    typedef long long LL;
    const LL inf = 0x3f3f3f3f3f3f;
    struct edge
    {
        int to,next;
    } E[MAXN*2];
    int head[MAXN],si,sz[MAXN],top[MAXN],son[MAXN],fa[MAXN],w[MAXN],dep[MAXN], add[MAXN<<1], isupdate[MAXN<<1], N, Q, A[MAXN], idx, mp[MAXN], que[MAXN];
    struct node
    {
        LL sum,ls,rs,ans;
        node(LL _ans = 0, LL _sum = 0, LL _ls = 0, LL _rs = 0 )
        {
            ans = _ans;
            sum = _sum;
            ls = _ls;
            rs = _rs;
        }
    } tree[MAXN<<1];
    void add_edge(int u,int v)
    {
        E[si].to = v;
        E[si].next = head[u];
        head[u] = si ++;
    }
    void bfs(int v)
    {
    //printf("fa[%d]=%d\n",v,fa[v]);
        int l = 0, r = 0;
        for(que[r ++] = v; l < r; l ++)
        {
            int now = que[l];
            for(int i =head[now]; ~i; i = E[i].next)
            {
                int u =E[i].to;
                if( u == fa[now] )continue;
                fa[u] = now;
                dep[u] = dep[now] + 1;
                que[r ++] = u;
            }
        }
        for(; r; r --)
        {
            int now = que[r - 1];
            sz[now] = 1;
            son[now] = 0;
            for(int i =head[now]; ~i; i = E[i].next)
            {
                int u =E[i].to;
                if( u == fa[now] )continue;
                sz[now] += sz[u];
                if( sz[son[now]] < sz[u] )
                {
                    son[now] = u;
                }
            }
        }
    }
    void rdfs(int v,int root)
    {
        w[v] = ++ idx;
        mp[idx] = v;
        top[v] = root;
        if( son[v] ) rdfs(son[v], root);
        for(int i =head[v]; ~i; i = E[i].next)
        {
            int u = E[i].to;
            if( u == fa[v] || u == son[v] )continue;
            rdfs(u,u);
        }
    }
    int getidx(int l,int r)
    {
        return l + r | l != r;
    }
    void updatenode(node &p, int x, int l, int r)
    {
        p = node( x, x * (r - l + 1), x, x );
        if( x >= 0)
        {
            p = node(x * (r - l + 1), x * (r - l + 1), x * (r - l + 1), x * (r - l + 1));
        }
    }
    void push_down(int l, int r)
    {
        int p =getidx(l, r), mid = l + r >> 1;
        if( l == r || !isupdate[p] )return;
        updatenode(tree[lson], add[p], l, mid);
        updatenode(tree[rson], add[p], mid + 1, r);
        isupdate[p] = false;
        isupdate[lson] = true;
        isupdate[rson] = true;
        add[lson] = add[rson] = add[p];
    }
    node unite(node a, node b)
    {
        node p;
        p.ans = max(a.ans, b.ans);
        p.ans = max(p.ans, a.rs + b.ls);
        p.sum = a.sum + b.sum;
        p.ls = max(a.ls, a.sum + b.ls);
        p.rs = max(b.rs, b.sum + a.rs);
        return p;
    }
    void put_up(int l, int r)
    {
        int p =getidx(l, r), mid = l + r >> 1;
        if( l == r ) return;
        tree[p] = unite(tree[lson], tree[rson]);
    }
    
    void build(int l,int r)
    {
        int p =getidx(l, r);
        isupdate[p] = false;
        add[p] = 0;
        if( l == r )
        {
            updatenode(tree[p], A[mp[l]], l, r);
            //  printf("[%d,%d]:%lld, %lld ,%lld, %lld\n",l, r,tree[p].ans, tree[p].sum, tree[p].ls, tree[p].rs);
            return;
        }
        int mid = l + r >> 1;
        build(l, mid);
        build(mid + 1, r);
        put_up(l, r);
        //printf("[%d,%d]:%lld, %lld ,%lld, %lld\n",l, r,tree[p].ans, tree[p].sum, tree[p].ls, tree[p].rs);
    }
    void update(int l, int r, int _l, int _r, int x)
    {
        if( l > _r || r < _l )return;
        if( _l <= l && r <= _r )
        {
            int p = getidx(l, r);
            updatenode(tree[p], x, l, r);
            add[p] = x;
            isupdate[p] = true;
            return;
        }
        int mid = l + r >> 1;
        push_down(l, r);
        update(l, mid, _l, _r, x);
        update(mid + 1, r, _l, _r, x);
        put_up(l, r);
    }
    void update(int u,int v,int x)
    {
        int a = top[u], b = top[v];
        while(a != b)
        {
            if( dep[a] < dep[b] )
            {
                swap(a, b);
                swap(u, v);
            }
            update(1, N, w[a], w[u], x);
            u = fa[a];
            a = top[u];
        }
        if( dep[u] < dep[v] )
        {
            swap(u, v);
        }
        update(1, N, w[v], w[u], x);
    }
    node query(int l, int r, int _l, int _r)
    {
        if( _l <= l && r <= _r )
        {
            return tree[getidx(l, r)];
        }
        int mid = l + r >> 1;
        push_down(l, r);
        if( _r <= mid ) return query(l, mid, _l, _r);
        else if( _l > mid ) return  query(mid + 1, r, _l, _r);
        else
        {
            return unite(query(l, mid, _l, _r), query(mid + 1, r, _l, _r));
        }
    }
    
    LL query(int u, int v)
    {
        int a = top[u], b = top[v];
        node lpath = node(-inf , 0, -inf, -inf), rpath = node(-inf, 0, -inf, -inf);
        while(a != b)
        {
            if( dep[a] > dep[b])
            {
                node res = query(1, N, w[a], w[u]);
                swap(res.ls, res.rs);
                lpath = unite(lpath, res);
                //  printf("lpath:%d->%d: %lld %lld %lld %lld\n", a, u, lpath.ans,lpath.sum, lpath.ls, lpath.rs);
                u = fa[a];
                a = top[u];
            }
            else
            {
                node res = query(1, N, w[b], w[v]);
                rpath = unite(res, rpath);
                //printf("rpath:%d->%d: %lld %lld %lld %lld\n", b, v, rpath.ans,rpath.sum, rpath.ls, rpath.rs);
                v = fa[b];
                b = top[v];
            }
        }
        node ans;
        if( dep[u] < dep[v] )
        {
            ans = query(1, N, w[u], w[v]);
        }
        else
        {
            ans = query(1, N, w[v], w[u]);
            swap(ans.ls,ans.rs);
        }
        // printf("%d->%d: %lld %lld %lld %lld\n", v, u, ans.ans,ans.sum, ans.ls, ans.rs);
        ans = unite(lpath, ans);
        //  printf(": %lld %lld %lld %lld\n",  ans.ans,ans.sum, ans.ls, ans.rs);
        ans = unite(ans, rpath);
        return ans.ans;
    }
    int main()
    {
        //  freopen("in", "r", stdin);
        scanf("%d %d", &N, &Q);
        for(int i = 1; i <= N; i ++)
        {
            scanf("%d", &A[i]);
        }
        memset(head, -1, sizeof head);
        si = 0;
        idx = 0;
        for(int i = 1, u, v; i < N; i ++)
        {
            scanf("%d%d", &u, &v);
            add_edge(u, v);
            add_edge(v, u);
        }
        fa[1] = dep[1] = 0;
        bfs(1);
        rdfs(1, 1);
        build(1, N);
        for(int i = 1, t, u, v, x; i <= Q; i ++)
        {
            scanf("%d%d%d%d", &t, &u, &v, &x);
            if( t == 1 )
            {
                update(u, v, x);
            }
            else
            {
                long long ans = query(u, v);
                printf("%lld\n", ans);
            }
        }
        return 0;
    }