4127: Abs
Time Limit: 40 Sec Memory Limit: 256 MBSubmit: 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
-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
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=0; register bool f=false; while (ch=getchar(),ch<'0' || ch>'9')f|=ch=='-'; while (x=x*10+ch-'0',ch=getchar(),ch<='9' && ch>='0'); return x*(f?-1:1); } struct sgt_node { int lc,rc; int sd; qword sv; qword pls; pair<qword,int> mx; }sgt[MAXT]; int topt=0; 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+1,r,sgt[now].pls); sgt[now].pls=0; } } void Build_sgt(int &now,int l,int r) { now=++topt; if (l==r) { sgt[now].sd=b[l]<0?-1:1; sgt[now].sv=abs(b[l]); if (b[l]<0) { sgt[now].mx=make_pair(b[l],l); }else { sgt[now].mx=make_pair(-INFL,-1); } return ; } Build_sgt(sgt[now].lc,l,smid); Build_sgt(sgt[now].rc,smid+1,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+1,r,x,y,delta); else { Add_sgt(sgt[now].lc,l,smid,x,smid,delta); Add_sgt(sgt[now].rc,smid+1,r,smid+1,y,delta); } update(now); } void Modify_sgt(int now,int l,int r,int pos,qword v) { if (l==r) { if (v<0) sgt[now].mx=make_pair(v,l); else sgt[now].mx=make_pair(-INFL,-1); sgt[now].sd=v<0?-1:1; sgt[now].sv=abs(v); sgt[now].pls=0; return ; } down(now,l,r); if (pos<=smid) Modify_sgt(sgt[now].lc,l,smid,pos,v); else Modify_sgt(sgt[now].rc,smid+1,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+1,r,x,y); else return max(Query_sgt_max(sgt[now].lc,l,smid,x,smid), Query_sgt_max(sgt[now].rc,smid+1,r,smid+1,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+1,r,x,y); else return Query_sgt_sum(sgt[now].lc,l,smid,x,smid)+ Query_sgt_sum(sgt[now].rc,smid+1,r,smid+1,y); } struct Edge { int np; Edge *next; }E[MAXE],*V[MAXV]; int tope=-1; 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=-1,tail=0; Edge *ne; q[0]=now; depth[now]=1; 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]+1; q[++tail]=ne->np; } } for (int i=tail;i>=0;i--) { now=q[i]; siz[now]=1; int mxsiz=0; 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=-1; void dfs(int now) { Edge *ne; memset(spos,0x3f,sizeof(spos)); memset(tpos,0,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=1;i<=n;i++) a[i]=nextInt(); for (int i=1;i<n;i++) { x=nextInt();y=nextInt(); //scanf("%d%d",&x,&y); addedge(x,y); addedge(y,x); } bfs(1); dfs(1); for (int i=1;i<=n;i++) b[pos[i]]=a[i]; for (int i=1;i<=n;i++) { if (top[i]==i) Build_sgt(troot[i],spos[i],tpos[i]); else troot[i]=-1; } int opt; for (int i=0;i<m;i++) { opt=nextInt(); //scanf("%d",&opt); if (opt==1) { 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<=0)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<=0)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=0; 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 ",res); } } }