首页 > 代码库 > 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 树链剖分 在树上任意路径的最大子段和 区间修改点权