题解 P1505 【[国家集训队]旅游】
1saunoya
2019-09-03 20:34:28
$\text{很显然这题是个树剖。。。如果您不会树剖 请去模板题}$
$\text{修改1：单点修改。。}$
$\text{修改2：区间乘-1 这样的话最大值需要变成最小值的负数 最小值要变成最大值的负数}$
$\text{查询1：区间求和}$
$\text{查询2：区间最大值}$
$\text{查询3：区间最小值}$
$\text{所以很显然我们可以发现这个就是一个普通的树剖}$
$\text{这题的码量巨大。。我打了20min 但是调了一个小时。。。}$
$\text{问题在于 最小值 最大值的处理 以及 懒标记 我在求最大最小值的时候忘记处理了。。。这些都是比较弱智的问题。。}$
$\huge \mathcal{Code}$
```cpp
//Isaunoya
#include<bits/stdc++.h>
using namespace std ;
inline int read() {
register int x = 0 ;
register int f = 1 ;
register char c = getchar() ;
for( ; ! isdigit(c) ; c = getchar()) if(c == '-') f = -1 ;
for( ; isdigit(c) ; c = getchar()) x = (x << 1) + (x << 3) + (c & 15) ;
return x * f ;
}
int st[105] ;
template < typename T > inline void write(T x , char c = '\n') {
int tp = 0 ;
if(x == 0) return (void) puts("0") ;
if(x < 0) putchar('-') , x = -x ;
for( ; x ; x /= 10) st[++ tp] = x % 10 ;
for( ; tp ; tp --) putchar(st[tp] + '0') ;
putchar(c) ;
}
//#define Online_Judge
//#define int long long
#define swap(x , y) x ^= y ^= x ^= y
int n ;
const static int N = 200000 + 5 ;
int a[N] ;
namespace SegTree {
struct Node {
int mn ; // the min
int mx ; // the max
int add ; // the sum
int lazy ; // the sign
};
Node t[N << 2] ;
inline void Push_down(int rt) {
if(t[rt].lazy) {
t[rt << 1].add = - t[rt << 1].add ;
t[rt << 1 | 1].add = - t[rt << 1 | 1].add ;
t[rt << 1].lazy ^= 1 ;
t[rt << 1 | 1].lazy ^= 1 ;
swap(t[rt << 1].mx , t[rt << 1].mn) ;
swap(t[rt << 1 | 1].mx , t[rt << 1 | 1].mn) ;
t[rt << 1].mx = - t[rt << 1].mx ;
t[rt << 1].mn = - t[rt << 1].mn ;
t[rt << 1 | 1].mx = - t[rt << 1 | 1].mx ;
t[rt << 1 | 1].mn = - t[rt << 1 | 1].mn ;
t[rt].lazy = 0 ;
}
return ;
}
//==============================================push_down
inline void Push_Up(int rt) {
t[rt].add = t[rt << 1].add + t[rt << 1 | 1].add ;
t[rt].mx = max(t[rt << 1].mx , t[rt << 1 | 1].mx) ;
t[rt].mn = min(t[rt << 1].mn , t[rt << 1 | 1].mn) ;
return ;
}
//==============================================push_up
inline void build(int l , int r , int rt) {
if(l == r) {
t[rt].add = t[rt].mn = t[rt].mx = a[l] ;
return ;
}
int mid = l + r >> 1 ;
build(l , mid , rt << 1) ;
build(mid + 1 , r , rt << 1 | 1) ;
Push_Up(rt) ;
}
//==============================================build
inline void Add(int x , int l , int r , int rt , int val) {
if(l == r) {
t[rt].add = t[rt].mn = t[rt].mx = val ;
return ;
}
int mid = l + r >> 1 ;
Push_down(rt) ;
if(x <= mid) Add(x , l , mid , rt << 1 , val) ;
else Add(x , mid + 1 , r , rt << 1 | 1 , val) ;
Push_Up(rt) ;
}
//==============================================change x - > val
inline void Change(int a , int b , int l , int r , int rt) {
if(a > r || b < l) return ;
if(a <= l && r <= b) {
t[rt].add = - t[rt].add ;
t[rt].lazy ^= 1 ;
swap(t[rt].mx , t[rt].mn) ;
t[rt].mx = - t[rt].mx ;
t[rt].mn = - t[rt].mn ;
return ;
}
int mid = l + r >> 1 ;
Push_down(rt) ;
Change(a , b , l , mid , rt << 1) ;
Change(a , b , mid + 1 , r , rt << 1 | 1) ;
Push_Up(rt) ;
}
//===============================================change x - > -x
inline int Sum(int a , int b , int l , int r , int rt) {
if(a > r || b < l) return 0 ;
if(a <= l && r <= b) return t[rt].add ;
int mid = l + r >> 1 ;
Push_down(rt) ;
int ans = 0 ;
ans += Sum(a , b , l , mid , rt << 1 ) ;
ans += Sum(a , b , mid + 1 , r , rt << 1 | 1) ;
Push_Up(rt) ;
return ans ;
}
//====================================================== a - > b sum
inline int Min(int L , int R , int l , int r , int rt) {
if(L > r || R < l) return INT_MAX ;
if(L <= l && r <= R) return t[rt].mn ;
int ans = INT_MAX ;
int mid = l + r >> 1 ;
Push_down(rt) ;
if(L <= mid) ans = min(ans , Min(L , R , l , mid , rt << 1)) ;
if(R > mid) ans = min(ans , Min(L , R, mid + 1 , r , rt << 1 | 1)) ;
Push_Up(rt) ;
return ans ;
}
//====================================================== a - > b min
inline int Max(int L , int R , int l , int r , int rt) {
if(L > r || R < l) return INT_MIN ;
if(L <= l && r <= R) return t[rt].mx ;
int ans = INT_MIN ;
int mid = l + r >> 1 ;
Push_down(rt) ;
if(L <= mid) ans = max(ans , Max(L , R , l , mid , rt << 1)) ;
if(R > mid) ans = max(ans , Max(L , R, mid + 1 , r , rt << 1 | 1)) ;
Push_Up(rt) ;
return ans ;
}
//====================================================== a - > b max
}
//===========================================================SegTree
namespace SLPF {
struct node {
int v ;
int nxt ;
int w ;
};
int fa[N] ; int id[N] ; int son[N] ;
int size[N] ; int d[N] ; int top[N] ;
int fst[N] ;
node e[N << 1] ;
int tot = 0 ;
int head[N] ; int cnt = 0 ;
inline void Add_Edge(int u , int v , int w) {
e[++ cnt].v = v ;
e[cnt].nxt = head[u] ;
e[cnt].w = w ;
head[u] = cnt ;
return ;
}
inline void Dfs1(int u) {
size[u] = 1 ;
for(register int i = head[u] ; i ; i = e[i].nxt) {
int v = e[i].v ;
if(v ^ fa[u]) {
d[v] = d[u] + 1 ;
fa[v] = u ;
fst[v] = e[i].w ;
Dfs1(v) ;
size[u] += size[v] ;
if(size[v] > size[son[u]]) son[u] = v ;
}
}
}
inline void Dfs2(int u , int t) {
id[u] = ++ tot ;
top[u] = t ;
a[tot] = fst[u] ;
if(son[u]) Dfs2(son[u] , t) ;
for(register int i = head[u] ; i ; i = e[i].nxt) {
int v = e[i].v ;
if(v ^ fa[u] && v ^ son[u]) Dfs2(v , v) ;
}
}
//========================================================Dfs1 && Dfs2
inline void Change_Range(int x , int y) {
int fx = top[x] ;
int fy = top[y] ;
while(fx ^ fy) {
if(d[fx] < d[fy]) swap(x , y) , swap(fx , fy) ;
SegTree::Change(id[fx] , id[x] , 1 , tot , 1) ;
x = fa[fx] ;
fx = top[x] ;
}
if(id[x] > id[y]) swap(x , y) ;
SegTree::Change(id[x] + 1 , id[y] , 1 , tot , 1) ;
}
inline int Query_Sum(int x , int y) {
int fx = top[x] ;
int fy = top[y] ;
int ans = 0 ;
while(fx ^ fy) {
if(d[fx] < d[fy]) swap(x , y) , swap(fx , fy) ;
ans += SegTree::Sum(id[fx] , id[x] , 1 , tot , 1) ;
x = fa[fx] ;
fx = top[x] ;
}
if(id[x] > id[y]) swap(x , y) ;
ans += SegTree::Sum(id[x] + 1 , id[y] , 1 , tot , 1) ;
return ans ;
}
inline int Query_Min(int x , int y) {
int fx = top[x] ;
int fy = top[y] ;
int ans = INT_MAX ;
while(fx ^ fy) {
if(d[fx] < d[fy]) swap(x , y) , swap(fx , fy) ;
ans = min(ans , SegTree::Min(id[fx] , id[x] , 1 , tot , 1)) ;
x = fa[fx] ;
fx = top[x] ;
}
if(id[x] > id[y]) swap(x , y) ;
ans = min(ans , SegTree::Min(id[x] + 1 , id[y] , 1 , tot , 1)) ;
return ans ;
}
inline int Query_Max(int x , int y) {
int fx = top[x] ;
int fy = top[y] ;
int ans = INT_MIN ;
while(fx ^ fy) {
if(d[fx] < d[fy]) swap(x , y) , swap(fx , fy) ;
ans = max(ans , SegTree::Max(id[fx] , id[x] , 1 , tot , 1)) ;
x = fa[fx] ;
fx = top[x] ;
}
if(id[x] > id[y]) swap(x , y) ;
ans = max(ans , SegTree::Max(id[x] + 1 , id[y] , 1 , tot , 1)) ;
return ans ;
}
}
using namespace SLPF ;
inline int getopt() {
string s = "" ;
register char c = getchar() ;
while(isspace(c)) c = getchar() ;
while(! isspace(c)) {
s += c ;
c = getchar() ;
}
if(s == "C") return 0 ;
if(s == "N") return 1 ;
if(s == "SUM") return 2 ;
if(s == "MAX") return 3 ;
if(s == "MIN") return 4 ;
}
signed main() {
#ifdef Online_Judge
freopen("testdata.in" , "r" , stdin) ;
freopen("testdata2.out" , "w" , stdout) ;
#endif
n = read() ;
for(register int i = 1 ; i <= n - 1 ; i ++) {
int u = read() , v = read() , w = read() ;
u ++ , v ++ ;
Add_Edge(u , v , w) ;
Add_Edge(v , u , w) ;
}
Dfs1(1) ;
Dfs2(1 , 0) ;
SegTree::build(1 , n , 1) ;
for(register int t = read() ; t -- ; ) {
int opt = getopt() ;
// write(opt) ;
if(opt == 0) {
int x = read() , y = read() ;
x ++ ;
SegTree::Add(id[x] , 1 , n , 1 , y) ;
}
if(opt == 1) {
int x = read() , y = read() ;
x ++ , y ++ ;
Change_Range(x , y) ;
}
if(opt == 2) {
int x = read() , y = read() ;
x ++ , y ++ ;
write(Query_Sum(x , y)) ;
}
if(opt == 3) {
int x = read() , y = read() ;
x ++ , y ++ ;
write(Query_Max(x , y)) ;
}
if(opt == 4) {
int x = read() , y = read() ;
x ++ , y ++ ;
write(Query_Min(x , y)) ;
}
}
return 0 ;
}
```