生活随笔
收集整理的這篇文章主要介紹了
hdu 3966 树链剖分
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
樹鏈剖分模板題目，記錄一下。
總結：
這里我re了 幾次，在于update操作中，應該先判斷頭節(jié)點的深度，優(yōu)先跳轉深度淺的，而不是判斷當前兩個點那個更深，這是沒有意義的。
這里son可以memset成-1，因為dfs的時候會優(yōu)先賦值不會存在數組越界。
head數組也需要復制-1。
其余數組在兩次dfs中會被依次賦值，再多組輸入中不用重復清空，會自動覆蓋掉上次結果。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<stack>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<cstdio>
#define up(i,a,b) for(int i=a;i<b;i++)
#define dw(i,a,b) for(int i=a;i>b;i--)
#define upd(i,a,b) for(int i=a;i<=b;i++)
#define dwd(i,a,b) for(int i=a;i>=b;i--)
typedef long long ll
;
const double esp
= 1e-6;
const double pi
= acos(-1.0);
const int INF
= 0x3f3f3f3f;
const int inf
= 1e9;
using namespace std
;
ll
read()
{char ch
= getchar(); ll x
= 0, f
= 1;while (ch
<'0' || ch
>'9') { if (ch
== '-')f
= -1; ch
= getchar(); }while (ch
>= '0' && ch
<= '9') { x
= x
* 10 + ch
- '0'; ch
= getchar(); }return x
* f
;
}
typedef pair
<int, int> pir
;
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define lrt root<<1
#define rrt root<<1|1
const int N
= 1e5 + 10;
int n
, m
, p
;
int a
[N
];
struct node
{ int to
, next
; }edge
[2 * N
];
int head
[N
];
int dep
[N
], fa
[N
], siz
[N
], id
[N
], neww
[N
], top
[N
], son
[N
], rk
[N
];
ll tree
[N
<< 2], lazy
[N
<< 2];
int cnt
= 0;
int num
= 0;
void addedge(int u
, int v
)
{edge
[cnt
].to
= v
;edge
[cnt
].next
= head
[u
];head
[u
] = cnt
++;
}
void pushup(int root
)
{tree
[root
] = tree
[lrt
] + tree
[rrt
];
}
void pushdown(int root
, int l
, int r
)
{int lrg
= (r
- l
+ 1) - ((r
- l
+ 1) >> 1); int rrg
= (r
- l
+ 1) >> 1;if (lazy
[root
]){lazy
[rrt
] += lazy
[root
]; lazy
[lrt
] += lazy
[root
];tree
[lrt
] += 1ll * lrg
* lazy
[root
]; tree
[rrt
] += 1ll * rrg
* lazy
[root
];lazy
[root
] = 0;}
}
void build(int l
, int r
, int root
)
{lazy
[root
] = 0;if (l
== r
) { tree
[root
] = a
[rk
[l
]]; return; }int mid
= (l
+ r
) >> 1;build(lson
); build(rson
);pushup(root
);
}
void update(int l
, int r
, int root
, int lf
, int rt
, int val
)
{if (lf
<= l
&& r
<= rt
){tree
[root
] += val
* (r
- l
+ 1) * 1ll;lazy
[root
] += val
;return;}pushdown(root
, l
, r
);int mid
= (l
+ r
) >> 1;if (lf
<= mid
)update(lson
, lf
, rt
, val
);if (rt
> mid
)update(rson
, lf
, rt
, val
);pushup(root
);
}
ll
querry(int l
, int r
, int root
, int pos
)
{if (l
== r
){return tree
[root
];}pushdown(root
, l
, r
);int mid
= (l
+ r
) >> 1;ll ans
= 0;if (pos
<= mid
)ans
+= querry(lson
, pos
); else ans
+= querry(rson
, pos
);return ans
;
}
void dfs1(int u
, int pre
, int d
) {dep
[u
] = d
;fa
[u
] = pre
;siz
[u
] = 1;for (int i
= head
[u
]; i
!= -1; i
= edge
[i
].next
) {int v
= edge
[i
].to
;if (v
== pre
) continue;dfs1(v
, u
, d
+ 1);siz
[u
] += siz
[v
];if (son
[u
] == -1 || siz
[v
] > siz
[son
[u
]])son
[u
] = v
;}
}
void dfs2(int u
, int tp
) { top
[u
] = tp
;id
[u
] = ++num
;rk
[num
] = u
;if (son
[u
] == -1) return;dfs2(son
[u
], tp
);for (int i
= head
[u
]; i
!= -1; i
= edge
[i
].next
) {int v
= edge
[i
].to
;if (v
!= son
[u
] && v
!= fa
[u
]) {dfs2(v
, v
);}}
}
void updaterange(int x
, int y
, int val
)
{while (top
[x
] != top
[y
]){if (dep
[top
[x
]] < dep
[top
[y
]])swap(x
, y
);update(1, n
, 1, id
[top
[x
]], id
[x
], val
);x
= fa
[top
[x
]];}if (dep
[x
] < dep
[y
])swap(x
, y
);update(1, n
, 1, id
[y
], id
[x
], val
);
}
ll
rgquerry(int x
)
{return querry(1, n
, 1, id
[x
]);
}
int main()
{while (cin
>> n
>> m
>> p
) {upd(i
, 1, n
)a
[i
] = read();cnt
= num
= 0;int u
, v
;memset(head
, -1, sizeof(head
));memset(son
, -1, sizeof(son
));upd(i
, 1, m
)u
= read(), v
= read(), addedge(u
, v
), addedge(v
, u
);char s
[2];dfs1(1, -1, 1);dfs2(1, 1);build(1, n
, 1);int c1
, c2
, k
;while (p
--){cin
>> s
;if (s
[0] == 'I'){c1
= read(); c2
= read(); k
= read();updaterange(c1
, c2
, k
);}else if (s
[0] == 'D'){c1
= read(), c2
= read(), k
= read();updaterange(c1
, c2
, -k
);}else{c1
= read();printf("%lld\n", rgquerry(c1
));}}}return 0;
}
總結
以上是生活随笔為你收集整理的hdu 3966 树链剖分的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
