bzoj 4127: Abs 树链剖分

4127: Abs

Time Limit: 40 Sec Memory Limit: 256 MB
Submit: 11 Solved: 5
[Submit][Status][Discuss]

Description

 给定一棵树,设计数据结构支持以下操作

    1 u v　d　 表示将路径 (u,v) 加d

    2　u　v  表示询问路径 (u,v) 上点权绝对值的和

Input

第一行两个整数n和m，表示结点个数和操作数

接下来一行n个整数a_i,表示点i的权值

接下来n-1行,每行两个整数u,v表示存在一条(u,v)的边

接下来m行,每行一个操作,输入格式见题目描述

Output

对于每个询问输出答案

Sample Input

4 4
-4 1 5 -2
1 2
2 3
3 4
2 1 3
1 1 4 3
2 1 3
2 3 4

Sample Output

10
13
9

HINT

对于100%的数据，n,m <= 10^5 且 0<= d,|a_i|<= 10^8

　　我们分开处理正数负数情况，注意加数为正，所以一个负数被加成正数最多发生O(n)次，我们需要实现的就是快速的判定是否有某个负数加成了正数，维护负数集合中的最大值和位置即可。如果负数集合的最大值大于0，那么我们求得最大值所在位置，然后暴力将它修改到正数集合即可。

　　注意这道题INF取0x3f3f3f3f要出事。

　　第一次写链剖的每个链单独建线段树版本，不是太难。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define MAXN 210000

#define MAXT MAXN*4

#define MAXV MAXN

#define MAXE MAXN*2

#define INFL 0x3f3f3f3f3f3f3f3f

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

#define abs(x) ((x)>0?x:-(x))

typedef long long qword;

inline int nextInt()

{

        register char ch;

        register int x=;

        register bool f=false;

        while (ch=getchar(),ch<'' || ch>'')f|=ch=='-';

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

        return x*(f?-:);

}

struct sgt_node

{

        int lc,rc;

        int sd;

        qword sv;

        qword pls;

        pair<qword,int> mx;

}sgt[MAXT];

int topt=;

int a[MAXN];

int b[MAXN];

void update(int now)

{

        sgt[now].mx=max(sgt[sgt[now].lc].mx,sgt[sgt[now].rc].mx);

        sgt[now].sd=sgt[sgt[now].lc].sd+sgt[sgt[now].rc].sd;

        sgt[now].sv=sgt[sgt[now].lc].sv+sgt[sgt[now].rc].sv;

}

void make_plus(int now,int l,int r,qword delta)

{

        sgt[now].sv+=(qword)sgt[now].sd*delta;

        sgt[now].pls+=delta;

        sgt[now].mx.first+=delta;

}

void down(int now,int l,int r)

{

        if (sgt[now].pls)

        {

                make_plus(sgt[now].lc,l,smid,sgt[now].pls);

                make_plus(sgt[now].rc,smid+,r,sgt[now].pls);

                sgt[now].pls=;

        }

}

void Build_sgt(int &now,int l,int r)

{

        now=++topt;

        if (l==r)

        {

                sgt[now].sd=b[l]<?-:;

                sgt[now].sv=abs(b[l]);

                if (b[l]<)

                {

                        sgt[now].mx=make_pair(b[l],l);

                }else

                {

                        sgt[now].mx=make_pair(-INFL,-);

                }

                return ;

        }

        Build_sgt(sgt[now].lc,l,smid);

        Build_sgt(sgt[now].rc,smid+,r);

        update(now);

}

void Add_sgt(int now,int l,int r,int x,int y,int delta)

{

        if (l==x && r==y)

        {

                make_plus(now,l,r,delta);

                return ;

        }

        down(now,l,r);

        if (y<=smid)

                Add_sgt(sgt[now].lc,l,smid,x,y,delta);

        else if (smid<x)

                Add_sgt(sgt[now].rc,smid+,r,x,y,delta);

        else

        {

                Add_sgt(sgt[now].lc,l,smid,x,smid,delta);

                Add_sgt(sgt[now].rc,smid+,r,smid+,y,delta);

        }

        update(now);

}

void Modify_sgt(int now,int l,int r,int pos,qword v)

{

        if (l==r)

        {

                if (v<)

                        sgt[now].mx=make_pair(v,l);

                else

                        sgt[now].mx=make_pair(-INFL,-);

                sgt[now].sd=v<?-:;

                sgt[now].sv=abs(v);

                sgt[now].pls=;

                return ;

        }

        down(now,l,r);

        if (pos<=smid)

                Modify_sgt(sgt[now].lc,l,smid,pos,v);

        else

                Modify_sgt(sgt[now].rc,smid+,r,pos,v);

        update(now);

}

pair<qword,int> Query_sgt_max(int now,int l,int r,int x,int y)

{

        if (l==x && r==y)

        {

                return sgt[now].mx;

        }

        down(now,l,r);

        if (y<=smid)

                return Query_sgt_max(sgt[now].lc,l,smid,x,y);

        else if (smid<x)

                return Query_sgt_max(sgt[now].rc,smid+,r,x,y);

        else

                return max(Query_sgt_max(sgt[now].lc,l,smid,x,smid),

                                Query_sgt_max(sgt[now].rc,smid+,r,smid+,y));

}

qword Query_sgt_sum(int now,int l,int r,int x,int y)

{

        if (l==x && r==y)

                return sgt[now].sv;

        down(now,l,r);

        if (y<=smid)

                return Query_sgt_sum(sgt[now].lc,l,smid,x,y);

        else if (smid<x)

                return Query_sgt_sum(sgt[now].rc,smid+,r,x,y);

        else

                return Query_sgt_sum(sgt[now].lc,l,smid,x,smid)+

                        Query_sgt_sum(sgt[now].rc,smid+,r,smid+,y);

}

struct Edge

{

        int np;

        Edge *next;

}E[MAXE],*V[MAXV];

int tope=-;

void addedge(int x,int y)

{

        E[++tope].np=y;

        E[tope].next=V[x];

        V[x]=&E[tope];

}

int q[MAXN];

int depth[MAXN],top[MAXN],son[MAXN];

int pnt[MAXN],siz[MAXN];

int pos[MAXN],dfstime;

int spos[MAXN],tpos[MAXN];

void bfs(int now)

{

        int head=-,tail=;

        Edge *ne;

        q[]=now;

        depth[now]=;

        while (head<tail)

        {

                now=q[++head];

                for (ne=V[now];ne;ne=ne->next)

                {

                        if (ne->np==pnt[now])continue;

                        pnt[ne->np]=now;

                        depth[ne->np]=depth[now]+;

                        q[++tail]=ne->np;

                }

        }

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

        {

                now=q[i];

                siz[now]=;

                int mxsiz=;

                for (ne=V[now];ne;ne=ne->next)

                {

                        if (ne->np==pnt[now])continue;

                        siz[now]+=siz[ne->np];

                        if (siz[ne->np]>mxsiz)

                        {

                                mxsiz=siz[ne->np];

                                son[now]=ne->np;

                        }

                }

        }

}

int stack[MAXN],tops=-;

void dfs(int now)

{

        Edge *ne;

        memset(spos,0x3f,sizeof(spos));

        memset(tpos,,sizeof(tpos));

        stack[++tops]=now;

        top[now]=now;

        while (~tops)

        {

                now=stack[tops--];

                pos[now]=++dfstime;

                tpos[top[now]]=max(tpos[top[now]],pos[now]);

                spos[top[now]]=min(spos[top[now]],pos[now]);

                for (ne=V[now];ne;ne=ne->next)

                {

                        if (ne->np==pnt[now] || ne->np==son[now])continue;

                        stack[++tops]=ne->np;

                        top[ne->np]=ne->np;

                }

                if (son[now])

                {

                        stack[++tops]=son[now];

                        top[son[now]]=top[now];

                }

        }

}

int troot[MAXN];

int main()

{

        freopen("input.txt","r",stdin);

        int n,m,x,y,z;

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

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

                a[i]=nextInt();

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

        {

                x=nextInt();y=nextInt();

                //scanf("%d%d",&x,&y);

                addedge(x,y);

                addedge(y,x);

        }

        bfs();

        dfs();

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

                b[pos[i]]=a[i];

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

        {

                if (top[i]==i)

                        Build_sgt(troot[i],spos[i],tpos[i]);

                else

                        troot[i]=-;

        }

        int opt;

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

        {

                opt=nextInt();

                //scanf("%d",&opt);

                if (opt==)

                {

                        x=nextInt();y=nextInt();z=nextInt();

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

                        while (true)

                        {

                                if (top[x]==top[y])

                                {

                                        if (pos[x]>pos[y])swap(x,y);

                                        Add_sgt(troot[top[x]],spos[top[x]],tpos[top[x]],pos[x],pos[y],z);

                                        while (true)

                                        {

                                                pair<qword,int> pr;

                                                pr=Query_sgt_max(troot[top[x]],spos[top[x]],tpos[top[x]],pos[x],pos[y]);

                                                if (pr.first<=)break;

                                                Modify_sgt(troot[top[x]],spos[top[x]],tpos[top[x]],pr.second,pr.first);

                                        }

                                        break;

                                }

                                if (depth[top[x]]<depth[top[y]])swap(x,y);

                                Add_sgt(troot[top[x]],spos[top[x]],tpos[top[x]],pos[top[x]],pos[x],z);

                                while (true)

                                {

                                        pair<qword,int> pr;

                                        pr=Query_sgt_max(troot[top[x]],spos[top[x]],tpos[top[x]],pos[top[x]],pos[x]);

                                        if (pr.first<=)break;

                                        Modify_sgt(troot[top[x]],spos[top[x]],tpos[top[x]],pr.second,pr.first);

                                }

                                x=pnt[top[x]];

                        }

                }else

                {

                        //scanf("%d%d",&x,&y);

                        x=nextInt();y=nextInt();

                        qword res=;

                        while (true)

                        {

                                if (top[x]==top[y])

                                {

                                        if (pos[x]>pos[y])swap(x,y);

                                        res+=Query_sgt_sum(troot[top[x]],spos[top[x]],tpos[top[x]],pos[x],pos[y]);

                                        break;

                                }

                                if (depth[top[x]]<depth[top[y]])swap(x,y);

                                res+=Query_sgt_sum(troot[top[x]],spos[top[x]],tpos[top[x]],pos[top[x]],pos[x]);

                                x=pnt[top[x]];

                        }

                        printf("%lld\n",res);

                }

        }

}

巴特西