首页 > 代码库 > Spoj 6779 Can you answer these queries VII 树链剖分 在树上任意路径的最大子段和 区间修改点权
Spoj 6779 Can you answer these queries VII 树链剖分 在树上任意路径的最大子段和 区间修改点权
题目链接：点击打开链接
题意：
rt。。
在询问时，两端向上爬时记录从深度浅的到深度深的方向上的 （也就是左最大连续子段和）
最后两个点在同一条重链上时合并。
合并时要注意有4种情况， 详见代码。
线段树部分和5相似。
#include <cstdio>
#include <iostream>
#include <string.h>
#include <vector>
using namespace std;
inline void rd(int &n){
n = 0;
bool tmp = 0;
char c = getchar();
while((c < '0' || c > '9') && c != '-' ) c = getchar();
if(c == '-') c = getchar(), tmp = 1;
while(c >= '0' && c <= '9') n *= 10, n += (c - '0'),c = getchar();
if(tmp) n = -n;
}
#define N 100100
#define hehe 10001
#define L(x) tree[x].l
#define R(x) tree[x].r
#define Lson(x) (x<<1)
#define Rson(x) (x<<1|1)
#define Sum(x) tree[x].sum
#define Max(x) tree[x].max
#define Lmax(x) tree[x].lmax
#define Rmax(x) tree[x].rmax
#define Lazy(x) tree[x].lazy
#define Siz(x) tree[x].siz()
struct node{
int l, r;
int mid(){return (l+r)>>1;}
int siz(){return r-l+1;}
int lmax, rmax, max, sum, lazy;
}tree[N<<2];
int n, a[N], Q, fw[N];
void updata_point(int val, int id){Lmax(id) = Rmax(id) = Max(id) = Sum(id) = val * Siz(id);}
void push_down(int id){
if(L(id) == R(id))return ;
if(Lazy(id)!=hehe) {
updata_point(Lazy(id), Lson(id));
updata_point(Lazy(id), Rson(id));
Lazy(Lson(id)) = Lazy(Rson(id)) = Lazy(id);
Lazy(id) = hehe;
}
}
void push_up(int id){
if(L(id)==R(id))return ;
Lmax(id) = max(Lmax(Lson(id)), Sum(Lson(id)) + Lmax(Rson(id)));
Rmax(id) = max(Rmax(Rson(id)), Sum(Rson(id)) + Rmax(Lson(id)));
Sum(id) = Sum(Lson(id)) + Sum(Rson(id));
Max(id) = max(max(Max(Lson(id)), Max(Rson(id))), Rmax(Lson(id)) + Lmax(Rson(id)));
}
void build(int l, int r, int id){
L(id) = l; R(id) = r;
Lazy(id) = hehe;
if(l == r)
{
updata_point(a[fw[l]], id);
return;
}
int mid = tree[id].mid();
build(l, mid, Lson(id));
build(mid+1, r, Rson(id));
push_up(id);
}
void updata(int l, int r, int val, int id){
push_down(id);
if(l == L(id) && R(id) == r)
{
Lazy(id) = val;
updata_point(val, id);
return ;
}
int mid = tree[id].mid();
if(mid < l)
updata(l, r, val, Rson(id));
else if(r <= mid)
updata(l, r, val, Lson(id));
else {
updata(l, mid, val, Lson(id));
updata(mid+1, r, val, Rson(id));
}
push_up(id);
}
int query_sum(int l, int r, int id){
push_down(id);
if(l == L(id) && R(id) == r) return Sum(id);
int mid = tree[id].mid();
if(mid < l)
return query_sum(l, r, Rson(id));
else if(r <= mid)
return query_sum(l, r, Lson(id));
else
return query_sum(l, mid, Lson(id)) + query_sum(mid+1, r, Rson(id));
}
int query_L(int l, int r, int id){
if(l == L(id) && R(id) == r) return Lmax(id);
int mid = tree[id].mid();
if(mid < l)
return query_L(l, r, Rson(id));
else if(r <= mid)
return query_L(l, r, Lson(id));
int lans = query_L(l, mid, Lson(id)), rans = query_L(mid+1, r, Rson(id));
return max(lans, query_sum(l, mid, id) + rans);
}
int query_R(int l, int r, int id){
if(l == L(id) && R(id) == r) return Rmax(id);
int mid = tree[id].mid();
if(mid < l)
return query_R(l, r, Rson(id));
else if(r <= mid)
return query_R(l, r, Lson(id));
int lans = query_R(l, mid, Lson(id)), rans = query_R(mid+1, r, Rson(id));
return max(rans, query_sum(mid+1, r, id) + lans);
}
int query_l(int l, int r, int id){
push_down(id);
if(l == L(id) && R(id) == r) return Lmax(id);
int mid = tree[id].mid();
if(mid < l)
return query_l(l, r, Rson(id));
else if(r <= mid)
return query_l(l, r, Lson(id));
int lans = query_l(l, mid, Lson(id)), rans = query_l(mid+1, r, Rson(id));
return max(lans, Sum(Lson(id)) + rans);
}
int query_r(int l, int r, int id){
push_down(id);
if(l == L(id) && R(id) == r) return Rmax(id);
int mid = tree[id].mid();
if(mid < l)
return query_r(l, r, Rson(id));
else if(r <= mid)
return query_r(l, r, Lson(id));
int lans = query_r(l, mid, Lson(id)), rans = query_r(mid+1, r, Rson(id));
return max(rans, Sum(Rson(id)) + lans);
}
int query(int l, int r, int id){
push_down(id);
if(l == L(id) && R(id) == r)return Max(id);
int mid = tree[id].mid();
if(mid < l)
return query(l, r, Rson(id));
else if(r<=mid)
return query(l, r, Lson(id));
int lans = query(l, mid, Lson(id)), rans = query(mid+1, r, Rson(id));
int ans = max(lans, rans);
return max(ans, query_r(l, mid, Lson(id)) + query_l(mid+1, r, Rson(id)));
}
vector<int>G[N];
int fa[N], son[N], siz[N], dep[N], tree_id;
//父节点 重儿子 子树节点数 深度 线段树标号
int w[N], p[N];
//父边在线段树中的标号 节点顶端的点
void dfs(int u, int Father, int deep){
fa[u] = Father; son[u] = 0; dep[u] = deep; siz[u] = 1;
for(int i = 0; i < G[u].size(); i++) {
int v = G[u][i]; if(v == Father) continue;
dfs(v, u, deep+1);
siz[u] += siz[v];
if(siz[v] > siz[son[u]])son[u] = v;
}
}
void Have_p(int u, int Father){
w[u] = ++ tree_id; fw[tree_id] = u; p[u] = Father;
if(son[u])
Have_p(son[u], Father);
else return ;
for(int i = 0; i < G[u].size(); i++) {
int v = G[u][i]; if(v == fa[u] || v == son[u])continue;
Have_p(v, v);
}
}
void Updata(int l, int r, int val){
int f1 = p[l], f2 = p[r];
while(f1 != f2) {
if(dep[f1] < dep[f2])
swap(f1, f2), swap(l, r);
updata(w[f1], w[l], val, 1);
l = fa[f1]; f1 = p[l];
}
if(dep[l] > dep[r]) swap(l, r);
updata(w[l], w[r], val, 1);
}
int Query(int l, int r){
int ans = 0;
int f1 = p[l], f2 = p[r], lmax = 0, rmax = 0;
while(f1 != f2) {
if(dep[f1] < dep[f2])
swap(f1, f2), swap(l, r), swap(lmax, rmax);
ans = max(ans, query(w[f1], w[l], 1));
ans = max(ans, max(0,query_R(w[f1], w[l], 1)) + lmax);
lmax = max(query_sum(w[f1], w[l], 1) + lmax, query_L(w[f1], w[l], 1));
lmax = max(0, lmax);
l = fa[f1]; f1 = p[l];
}
if(dep[l] > dep[r]) swap(l, r), swap(lmax, rmax);
ans = max(ans, query(w[l], w[r], 1));
ans = max(ans, query_L(w[l], w[r], 1) + lmax);
ans = max(ans, query_R(w[l], w[r], 1) + rmax);
ans = max(ans, query_sum(w[l], w[r], 1) + lmax + rmax);
return ans;
}
void solve(){
siz[0] = tree_id = 0;
dfs(1, 1, 1);
Have_p(1, 1);
build(1, n, 1);
rd(Q); int op, a, b, c;
while(Q--)
{
rd(op); rd(a); rd(b);
if(op == 1)
printf("%d\n", Query(a, b));
else
{
rd(c);
Updata(a, b, c);
}
}
}
void input(){
for(int i = 1; i <= n; i++)rd(a[i]), G[i].clear();
for(int u, v, i = 1; i < n; i++) {
rd(u); rd(v);
G[u].push_back(v); G[v].push_back(u);
}
}
int main(){
while(~scanf("%d",&n)){
input();
solve();
}
return 0;
}
/*
7
-5 7 4 3 -5 8 -3
1 2
1 3
2 4
2 5
5 6
5 7
8
1 4 3
2 1 1 -3
1 3 4
1 2 6
1 6 2
1 2 7
1 7 5
1 4 7
ans :
10
11
10
10
7
0
10
*/
Spoj 6779 Can you answer these queries VII 树链剖分 在树上任意路径的最大子段和 区间修改点权
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。