HDU - 3966?

題意：給一顆樹，3種操作，Q u 查詢u節點的權值，I a b c 對a到b的路徑上每個點的點權增加c，D a b c 對a b 路徑上所有點的點權減少c

思路：樹鏈剖分+線段樹，2個問題，第一，如果是先建樹再輸入點的點權，記錄tip（點映射到線段樹后的位置），如果先輸入點權，再建樹，不僅要記錄tip還要記錄ran（線段樹上某個位置上的點對應的樹上點的序號，與tip是相互映射）；第二，連接起線段樹和樹鏈剖分的是get函數，區間操作才需要用到get函數，單點操作直接在線段樹上操作就可以。上面第一點尤其要注意，最重要的是理解tip和ran的意義 ，還有一點，多組輸入son數組要初始化清空

AC代碼：

#include "iostream" #include "string.h" #include "stack" #include "queue" #include "string" #include "vector" #include "set" #include "map" #include "algorithm" #include "stdio.h" #include "math.h" #define ll long long #define bug(x) cout<<x<<" "<<"UUUUU"<<endl; #define mem(a) memset(a,0,sizeof(a)) #define mp(x,y) make_pair(x,y) #define pb(x) push_back(x) #define lrt (rt*2) #define rrt (rt*2+1) using namespace std; const long long INF = 1e18+1LL; const int inf = 1e9+1e8; const int N=51000; const ll mod=1e9+7;int n,m,q,a[N]; int to[N<<1],nex[N<<1],head[N],tot=1; int lazy[N<<2]; int siz[N],son[N],tip[N],dep[N],top[N],fa[N],ran[N],cnt; void add(int u, int v){to[tot]=v;nex[tot]=head[u];head[u]=tot++; } void dfs1(int u, int f){siz[u]=1;son[u]=0;fa[u]=f;dep[u]=dep[f]+1;for(int i=head[u]; i!=-1; i=nex[i]){int v=to[i];if(v==f) continue;dfs1(v,u);siz[u]+=siz[v];if(siz[son[u]]<siz[v]) son[u]=v;} } void dfs2(int u, int tp){top[u]=tp;tip[u]=++cnt;ran[cnt]=u;if(son[u]) dfs2(son[u],tp);for(int i=head[u]; i!=-1; i=nex[i]){int v=to[i];if(v==fa[u] || v==son[u]) continue;dfs2(v,v);} } void push_down(int rt){lazy[lrt]+=lazy[rt];lazy[rrt]+=lazy[rt];lazy[rt]=0; } void creat(int rt, int l, int r){if(l==r){lazy[rt]=a[ran[l]];return;}int mid=l+r>>1;creat(lrt, l, mid);creat(rrt, mid+1, r); } void up(int rt, int l, int r, int L, int R, int w){if(l==L && r==R){lazy[rt]+=w;return;}push_down(rt);int mid=l+r>>1;if(R<=mid) up(lrt, l, mid, L, R, w);else if(L>mid) up(rrt, mid+1, r, L, R, w);else up(lrt, l, mid, L, mid, w), up(rrt, mid+1, r, mid+1, R, w); } int query(int rt, int l, int r, int p){if(l==r){return lazy[rt];}push_down(rt);int mid=l+r>>1;if(p<=mid) return query(lrt, l, mid, p);else return query(rrt, mid+1, r, p); } void update(int u, int v, int w){while(top[u] != top[v]){if(dep[top[u]]<dep[top[v]]) swap(u,v);up(1,1,n,tip[top[u]],tip[u],w);u=fa[top[u]];}if(dep[u]>dep[v]) swap(u,v);up(1,1,n,tip[u],tip[v],w); } int main(){//ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);while(scanf("%d%d%d",&n,&m,&q)!=EOF){memset(head,-1,sizeof(head));mem(lazy),tot=1,cnt=0,dep[1]=0;int u,v,t;char c[10];for(int i=1; i<=n; ++i){scanf("%d",&a[i]);}for(int i=1; i<=m; ++i){scanf("%d%d",&u, &v);add(u,v);add(v,u);}dfs1(1,1);dfs2(1,1);creat(1,1,n);while(q--){scanf("%s%d", c, &u);if(c[0]=='I' || c[0]=='D' ){scanf("%d%d",&v, &t);if(c[0]=='D') t=-t;update(u,v,t);}else printf("%d\n",query(1,1,n,tip[u]));}}return 0; }

?

轉載于:https://www.cnblogs.com/max88888888/p/7250189.html

總結

以上是生活随笔為你收集整理的hdu3966 树链剖分+线段树 裸题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。