Aizu 2450 Do use segment tree 树链剖分+线段树

2023-01-31 09:39:12

Do use segment tree

Time Limit: 1 Sec

Memory Limit: 256 MB

题目连接

http://www.bnuoj.com/v3/problem_show.php?pid=39566

Description

Given a tree with n (1 ≤ n ≤ 200,000) nodes and a list of q (1 ≤ q ≤ 100,000) queries, process the queries in order and output a value for each output query. The given tree is connected and each node on the tree has a weight wi (-10,000 ≤ wi ≤ 10,000).

Each query consists of a number ti (ti = 1, 2), which indicates the type of the query , and three numbers ai, bi and ci (1 ≤ ai, bi ≤ n, -10,000 ≤ ci ≤ 10,000). Depending on the query type, process one of the followings:

(ti = 1: modification query) Change the weights of all nodes on the shortest path between ai and bi (both inclusive) to ci.
(ti = 2: output query) First, create a list of weights on the shortest path between ai and bi (both inclusive) in order. After that, output the maximum sum of a non-empty continuous subsequence of the weights on the list. ci is ignored for output queries.

Input

The first line contains two integers n and q. On the second line, there are n integers which indicate w1, w2, ... , wn.

Each of the following n - 1 lines consists of two integers si and ei (1 ≤ si, ei ≤ n), which means that there is an edge between si and ei.

Finally the following q lines give the list of queries, each of which contains four integers in the format described above. Queries must be processed one by one from top to bottom.

Output

For each output query, output the maximum sum in one line.

Sample Input

Sample Output

HINT

题意

给你一棵树，然后查询一条链上，区间连续最大和

然后区间更新两个操作

题解：

树链剖分+线段树

1.树链剖分要bfs，不然会爆栈

2.如果wa了，可以尝试开ll试试

3.线段树，注意保存从左边开始的最大值，从右边开始最大值，这个区间的最大值，这个区间和

4.建议用lca写

//////////////////////////////

代码：

#include <cstdio>

#include <iostream>

#include <cstring>

#include <algorithm>

#include <queue>

using namespace std;

const int maxn = 2e5 + ;

const long long inf = 1LL << ;

typedef pair<long long,long long>dl;

const long long check = -(1LL << );

typedef long long SgTreeDataType;

struct treenode

{

  int L , R  ;

  SgTreeDataType sum , Lv , Rv , setv , maxv;

  void updata(SgTreeDataType v)

  {

      setv = v ;

      sum = (R-L+)*v;

      maxv = (v > ) ? (R-L+)*v : v;

    Rv = Lv = maxv;

  }

};

struct QueryData

{

    long long MaxValue , Left , Right ,sum;

    QueryData(long long MaxValue = ,long long Left = ,long long Right = ,long long sum = ) :MaxValue(MaxValue) , Left(Left) , Right(Right) , sum(sum){}

};

treenode tree[maxn * ];

inline void push_down(int o)

{

    if(tree[o].setv == inf) return ;

    SgTreeDataType lazyval = tree[o].setv;

    tree[*o].updata(lazyval) ; tree[*o+].updata(lazyval);

    tree[o].setv = inf;

}

inline void push_up(int o)

{

    tree[o].sum = tree[*o].sum + tree[*o+].sum;

    tree[o].Rv = max(tree[o*+].Rv,tree[o*+].sum + tree[o*].Rv);

    tree[o].Lv = max(tree[o*].Lv,tree[o*].sum + tree[o*+].Lv);

    tree[o].maxv = max( max(tree[o*].maxv , tree[o*+].maxv) , max( tree[o*].Rv + tree[o*+].Lv ,max(tree[o*].sum + tree[o*+].Lv , tree[o*+].sum + tree[o*].Rv)) );

}

inline void build_tree(int L , int R , int o)

{

    tree[o].L = L , tree[o].R = R,tree[o].sum =  , tree[o].setv = inf , tree[o].maxv = tree[o].Lv = tree[o].Rv = ;

    if (R > L)

    {

        int mid = (L+R) >> ;

        build_tree(L,mid,o*);

        build_tree(mid+,R,o*+);

    }

}

inline void updata(int QL,int QR,SgTreeDataType v,int o)

{

    int L = tree[o].L , R = tree[o].R;

    if (QL <= L && R <= QR) tree[o].updata(v);

    else

    {

        push_down(o);

        int mid = (L+R)>>;

        if (QL <= mid) updata(QL,QR,v,o*);

        if (QR >  mid) updata(QL,QR,v,o*+);

        push_up(o);

    }

}

inline QueryData QueryMax(int QL,int QR,int o)

{

    int L = tree[o].L , R = tree[o].R;

    if (QL <= L && R <= QR) return QueryData(tree[o].maxv,tree[o].Lv,tree[o].Rv,tree[o].sum);

    else

    {

        int mid = (L+R)>>;

        push_down(o);

        QueryData res;

        if(QL<=mid && QR <= mid)  res = QueryMax(QL,QR,*o);

        else if(QL>mid&&QR>mid) res = QueryMax(QL,QR,*o+);

        else

        {

            QueryData Lv = QueryMax(QL,QR,*o);

            QueryData Rv = QueryMax(QL,QR,*o+);

            res.MaxValue = max( max(Lv.MaxValue,Rv.MaxValue) , Lv.Right+Rv.Left );

            res.Left=Lv.Left,res.Right=Rv.Right;res.sum=Lv.sum+Rv.sum;

            res.Left=max(res.Left,Lv.sum+Rv.Left);

            res.Right=max(res.Right,Rv.sum+Lv.Right);

        }

        push_up(o);

        return res;

    }

}

inline dl QueryLeftMax(int QL,int QR,int o)

{

    int L = tree[o].L , R = tree[o].R;

    if(QL<=L && R <= QR) return make_pair(tree[o].Lv,tree[o].sum);

    else

    {

        push_down(o);

        int mid = (L+R) >> ;

        dl result;

        if(QL > mid) result = QueryLeftMax(QL,QR,o*+);

        else if(QR <= mid) result = QueryLeftMax(QL,QR,o*);

        else

        {

            dl LL = QueryLeftMax(QL,QR,o*);

            dl RR = QueryLeftMax(QL,QR,o*+);

            long long sum = LL.second + RR.second;

            long long Lval = max(LL.first , LL.second + RR.first);

            result = make_pair(Lval,sum);

        }

        push_up(o);

        return result;

    }

}

inline dl QueryRightMax(int QL,int QR,int o)

{

    int L = tree[o].L , R = tree[o].R;

    if(QL<=L && R <= QR) return make_pair(tree[o].Rv,tree[o].sum);

    else

    {

        push_down(o);

        int mid = (L+R) >> ;

        dl result;

        if(QL > mid) result = QueryRightMax(QL,QR,o*+);

        else if(QR <= mid) result = QueryRightMax(QL,QR,o*);

        else

        {

            dl LL = QueryRightMax(QL,QR,o*);

            dl RR = QueryRightMax(QL,QR,o*+);

            long long sum = LL.second + RR.second;

            long long Rval = max(RR.first , RR.second + LL.first);

            result = make_pair(Rval,sum);

        }

        push_up(o);

        return result;

    }

}

long long QuerySum(int QL,int QR,int o)

{

    int L = tree[o].L , R = tree[o].R;

    if(QL <= L && R <= QR) return tree[o].sum;

    else

    {

        int mid = (L+R) >> ;

        long long res = ;

        push_down(o);

        if(QL <= mid) res += QuerySum(QL,QR,*o);

        if(QR > mid) res += QuerySum(QL,QR,*o+);

        push_up(o);

        return res;

    }

}

vector<int>G[maxn];

int n , q ,val[maxn] , son[maxn] , idx[maxn] , top[maxn] , deep[maxn], fa[maxn] , head[maxn],T=;

void test()

{

    n = ;

    build_tree(  , n , );

    for(int i =  ; i <= n ; ++ i) updata( i , i , i , );

    updata(,,-,);

    QueryData res;

    dl BB;

    res = QueryMax(,n,);

    BB = QueryLeftMax(,n,);

    cout << res.MaxValue << endl;

    cout << BB.first << endl;

}

//********

int dfs_clock;

int que[maxn*],num[maxn],iii[maxn],b[maxn];

void build_List()

{

    int ft = , rear = ;

    que[rear++] = ;

    fa[] = ;

    deep[] = ;

    while(ft < rear)

    {

        int u = que[ft++];

        for(int i = ; i < G[u].size(); i++)

        {

            int v = G[u][i];

            if(v == fa[u]) continue;

            fa[v] = u;

            que[rear++] = v;

            deep[v] = deep[u]+;

        }

    }

    memset(num, , sizeof (num));

    for(int i = n-; i >= ; i--)

    {

        int u = que[i];

        num[u]++;

        num[fa[u]] += num[u];

    }

    for(int i = ; i <= n; i++)

    {

        for(int j = ; j < G[i].size(); j++) if(G[i][j] != fa[i])

                if(G[i][] == fa[i] || num[G[i][j]] > num[G[i][]])

                    swap(G[i][], G[i][j]);

    }

    top[] = ;

    for(int i = ; i < n; i++)

    {

        int u = que[i];

        if(G[fa[u]][] == u) top[u] = top[fa[u]];

        else top[u] = u;

    }

    memset(iii, , sizeof (iii));

    ft = ;

    dfs_clock = ;

    que[++ft] = ;

    idx[] = ++dfs_clock;

    b[] = val[];

    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;

            idx[v] = ++dfs_clock;

            b[idx[v]] = val[v];

            iii[u]++;

        }

    }

    for(int i =  ; i <= n ; ++ i) updata(i , i , b[i] , );

}

//*********

void my_updata(int u , int v , int c)

{

    int f1 = top[u] , f2 = top[v];

    while(f1 != f2)

    {

        if(deep[f1] < deep[f2]) swap(f1,f2) , swap(u,v);

        updata(idx[top[u]],idx[u],c,);

        u = top[u] , u = fa[u] , f1 = top[u];

    }

    if(deep[u] > deep[v])  swap(u,v);

    updata(idx[u] , idx[v] , c , );

}

long long solve(int u ,int v)

{

    int f1 = top[u] , f2 = top[v];

    if(u == v) return QueryMax(idx[u],idx[u],).MaxValue;

    long long  s[];s[] = s[] = check;

    int cur = ;

    long long ans=check;

    while(f1 != f2)

    {

        if(deep[f1] < deep[f2]) swap(f1,f2) , swap(u,v) , cur ^= ;

        long long sum = QuerySum(idx[top[u]],idx[u],);

        long long tt = QueryMax(idx[top[u]],idx[u],).MaxValue;

        ans = max(ans , tt);

        tt = QueryRightMax(idx[top[u]],idx[u],).first;

        ans = max(ans ,tt);

        ans = max(ans ,s[cur] + tt);

        tt = QueryLeftMax(idx[top[u]],idx[u],).first;

        s[cur] = max(sum + s[cur],tt);

        ans = max(ans , s[cur]);

        u = top[u] , u = fa[u] , f1 = top[u];

    }

    if(deep[u] > deep[v]) swap(u,v) , cur ^= ;

    ans = max(ans , QueryMax(idx[u],idx[v],).MaxValue);

    if(s[cur^] != (check)) ans = max( ans , s[cur^] + QueryRightMax(idx[u],idx[v],).first);

    if(s[cur] != (check)) ans = max( ans , s[cur] + QueryLeftMax(idx[u],idx[v],).first);

    if(s[cur] != (check) &&  s[cur^] != (check)) ans = max( ans , QuerySum(idx[u],idx[v],) + s[] + s[]);

    return ans;

}

inline int read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

int main(int argc,char * argv[])

{

    scanf("%d%d",&n,&q);

    for(int i =  ; i <= n ; ++ i)  scanf("%d",val+i);

    for(int i =  ; i < n ; ++ i)

    {

        int u , v;scanf("%d%d",&u,&v);

        G[u].push_back(v);G[v].push_back(u);

    }

    build_tree(,n,);

    build_List();

    while(q--)

    {

        int x,y,z,w;scanf("%d%d%d%d",&x,&y,&z,&w);

        if(x == ) my_updata(y,z,w);

        else printf("%lld\n",solve(y,z));

    }

    return ;

}

码农公寓