xiaoMa
"Bye Bye Baby Blue"
一些树链剖分的题目(1)

手残党的噩梦😏

SPOJ-QTREE

这道题把边权转化成点权,单点修改就行

#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 &amp; 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
int n ;

//============================================SegTree
struct SegTree {
	int val ;
	int max ;
};
const int N = 2e5 + 10 ;
SegTree t[N << 2] ;
int a[N] ;
inline void build(int l , int r , int rt) {
	if( l == r ) {
		t[rt].max = t[rt].val = a[l] ;
		return ;
	}
	int mid = l + r >> 1 ;
	build(l , mid , rt << 1) ;
	build(mid + 1 , r , rt << 1 | 1) ;
	t[rt].max = max(t[rt << 1].max , t[rt << 1 | 1].max) ;
}
inline void Change(int x , int l , int r , int rt , int val) {
	if(l == r) {
		t[rt].max = t[rt].val = val ;
		return ;
	}
	int mid = l + r >> 1 ;
	if(x <= mid) Change(x , l , mid , rt << 1 , val) ;
	else Change(x , mid + 1 , r , rt << 1 | 1 ,val ) ;
	t[rt].max = max(t[rt << 1].max , t[rt << 1 | 1].max) ;
}
inline int Query_Max(int a , int b , int  l, int r , int rt) {
	if(a > b) return 0 ;
	if(a <= l &amp;&amp; r <= b) return t[rt].max ;
	int ans = 0 ;
	int mid = l + r >> 1 ;
	if(a <= mid) ans = max(ans , Query_Max(a , b , l , mid , rt << 1)) ;
	if(b > mid) ans = max(ans , Query_Max(a , b , mid + 1 , r , rt << 1 | 1)) ;
	return ans ;
}
//========================================================================

struct node {
	int v ;
	int nxt ;
	int w ;
};
node e[N << 1] ;
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 ;
}
int size[N] ;
int son[N] ;
int d[N] ;
int fst[N] ;
int id[N] ;
int top[N] ;
int fa[N] ;
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]) continue ;
		d[v] = d[u] + 1 ;
		fst[v] = e[i].w ;
		fa[v] = u ;
		Dfs1(v) ;
		size[u] += size[v] ;
		if(size[v] > size[son[u]]) son[u] = v ;
	}
}
int idx = 0 ;
inline void Dfs2(int u , int t) {
	id[u] = ++ idx ;
	a[idx] = fst[u] ;
	top[u] = t ; 
	if(! son[u]) return ;
	Dfs2(son[u] , t) ;
	for(register int i = head[u] ; i ; i = e[i].nxt) {
		int v = e[i].v ;
		if(v ^ fa[u] &amp;&amp; v ^ son[u]) {
			Dfs2(v , v) ;
		}
	}
}
inline int Query_Range(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 = max(ans , Query_Max(id[fx] , id[x] , 1 , n , 1)) ;
		x = fa[fx] ;
		fx = top[x] ;
	}
	if(id[x] > id[y]) swap(x , y) ;
	ans = max(ans , Query_Max(id[x] + 1 , id[y] , 1 , n , 1)) ;
	return ans ;
}
inline int getopt() {
	string s ;
	register char c = getchar() ;
	while(isspace(c)) c = getchar() ;
	while(! isspace(c)) {
		s += c ;
		c = getchar() ;
	}
	if(s == "DONE") return -1 ;
	if(s == "QUERY") return 0 ;
	return 1 ;
}
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 ; i ++) {
		int u = read() , v = read() , w = read() ;
		Add_Edge(u , v , w) ;
		Add_Edge(v , u , w) ;
	}
	Dfs1(1) ;
	Dfs2(1 , 1) ;
	build(1 , n , 1) ;
	while(1) {
		int opt = getopt() ;
		if(opt == -1) {
			return 0 ;
		}
		if(opt == 0) {
			int x = read() , y = read() ;
			if(x == y) {
				puts("0") ;
				continue ;
			}
			else {
				write(Query_Range(x , y)) ;
			}
		}
		else {
			int x = read() , y = read() ;
			int u = e[x * 2 - 1].v ;
			int v = e[x * 2].v ;
			if(u == fa[v]) swap(u , v) ;
			Change(id[u] , 1 , n , 1 , y) ;
		}
	}
	return 0 ;
}

P1505 [国家集训队]旅游

  • 修改一:单点修改
  • 修改二:区间乘-1,意味着,最大值变成最小值的负数,最小值变成最大值的负数
  • 查询一 :区间求和
  • 查询二:区间最小值
  • 查询二:区间最大值

所以明显就是树剖

#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 &amp; 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 &amp;&amp; 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 &amp;&amp; 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 &amp;&amp; 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 &amp;&amp; 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] &amp;&amp; v ^ son[u]) Dfs2(v , v) ;
        }
    }
    //========================================================Dfs1 &amp;&amp; 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 ;
}

P3950 【部落冲突】

存在操作:  区间修改 区间查询

把每个加法操作加到vector里,结束就直接查询

#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 &amp; 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
int n ;
vector < pair < int , int > > v ;
const int N = 3e5 + 10 ;
int a[N] ;
struct node {
    int v ;
    int nxt ;
};
node e[N << 1] ; int head[N] ;
int cnt = 0 ;
inline void Add(int u , int v) {
    e[++ cnt].v = v ;
    e[cnt].nxt = head[u] ;
    head[u] = cnt ;
    return ;
} 
int size[N] ;
int top[N] , son[N] ;
int fa[N] ; int id[N] ; int d[N] ;
int idx = 0 ;
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]) {
            fa[v] = u ;
            d[v] = d[u] + 1 ;
            Dfs1(v) ;
            size[u] += size[v] ;
            if(size[son[u]] < size[v]) son[u] = v ;
        }
    }
}
inline void Dfs2(int u , int t) {
    id[u] = ++ idx ;
    top[u] = t ;
    a[idx] = 0 ;
    if(! son[u]) return ;
    Dfs2(son[u] , t) ;
    for(register int i = head[u] ; i ; i = e[i].nxt) {
        int v = e[i].v ;
        if(v ^ fa[u] &amp;&amp; v ^ son[u]) {
            Dfs2(v , v) ;
        }
    }
}
int sum[N << 2] ;
int tag[N << 2] ;
inline void build(int l , int r , int rt) {
    if(l == r) {
        sum[rt] = a[l] ; 
        tag[rt] = 0 ;
        return ;
    }
    int mid = l + r >> 1 ;
    build(l , mid , rt << 1) ;
    build(mid + 1 , r , rt << 1 | 1) ;
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1] ;
    return ;
}
inline void Push_down(int rt , int l , int r) {
    if(tag[rt]) {
        tag[rt << 1] += tag[rt] ;
        tag[rt << 1 | 1] += tag[rt] ;
        int mid = l + r >> 1 ;
        sum[rt << 1] += tag[rt] * (mid - l + 1) ;
        sum[rt << 1 | 1] += tag[rt] * (r - mid) ;
        tag[rt] = 0 ;
        return ;
    }
}
inline void Change(int a , int b , int l , int r , int rt , int val) {
    if(a <= l &amp;&amp; r <= b) {
        sum[rt] += val * (r - l + 1) ;
        tag[rt] += val ;
        return ;
    }
    int mid = l + r >> 1 ;
    Push_down(rt , l , r) ;
    if(a <= mid) Change(a , b , l , mid , rt << 1 , val) ;
    if(b > mid) Change(a , b , mid + 1 , r , rt << 1 | 1 , val) ;
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1] ;
    return ;
}
inline int Query(int a , int b , int l , int r , int rt) {
    if(a <= l &amp;&amp; r <= b) return sum[rt] ;
    int mid = l + r >> 1 ;
    int ans = 0 ;
    Push_down(rt , l , r) ;
    if(a <= mid) ans += Query(a , b , l , mid , rt << 1) ;
    if(b > mid) ans += Query(a , b , mid + 1 , r , rt << 1 | 1) ;
    return ans ;
}
inline int Query_Range(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 += Query(id[fx] , id[x] , 1 , n , 1) ;
        x = fa[fx] ;
        fx = top[x] ;
    }
    if(id[x] > id[y]) swap(x , y) ;
    ans += Query(id[x] + 1 , id[y] , 1 , n , 1) ;
    return ans ;
}
inline void Change_Range(int x , int y , int val) {
    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) ;
        Change(id[fx] , id[x] , 1 , n , 1 , val) ;
        x = fa[fx] ;
        fx = top[x] ;
    }
    if(id[x] > id[y]) swap(x , y) ;
    Change(id[x] + 1 , id[y] , 1 , n , 1 , val) ;
}
signed main() {
#ifdef Online_Judge
    freopen("testdata.in" , "r" , stdin) ;
    freopen("testdata2.out" , "w" , stdout) ;
#endif
    n = read() ; int q = read() ;
    for(register int  i = 1 ; i <= n - 1 ; i ++) {
        int u = read() ;
        int v = read() ;
        Add(u , v) ;
        Add(v , u) ;
    }
    Dfs1(1) ;
    Dfs2(1 , 1) ;
    build(1 , n , 1) ;
    for(register int i = 1 ; i <= q ; i ++) {
        register char c = getchar() ;
        for( ; c != 'C' &amp;&amp; c != 'Q' &amp;&amp; c != 'U' ; c = getchar()) ;
        if(c == 'Q') {
            int x = read() , y = read() ;
            if(Query_Range(x , y)) puts("No") ;
            else puts("Yes") ;
        }
        if(c == 'C') {
            int x = read() , y = read() ;
            Change_Range(x , y , 1) ;
            v.push_back(make_pair(x , y)) ;
        }
        if(c == 'U') {
            int num = read() - 1 ;
            int x = v[num].first ;
            int y = v[num].second ;
            Change_Range(x , y , - 1) ;
        }
    }
    return 0 ;
}

[NOI2015]软件包管理器

  • 操作一: 把根节点到$X$软件之间的路径上的值变为1
  • 操作二:卸载软件就把$X$和它子树的值变为0

也是一道很裸的题目

#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 &amp; 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

struct node {
	int l ; int r ;
	mutable int val ;
	bool operator < (const node &amp; x) const {
		return l < x.l ;
	}
};
set < node > s ;

#define slt set < node > :: iterator
inline slt Split(int pos) {
	slt it = s.lower_bound((node) {pos}) ;
	if(it != s.end() &amp;&amp; it -> l == pos) return it ;
	-- it ;
	int l = it -> l ;
	int r = it -> r ;
	int val = it -> val ;
	s.erase(it) ;
	s.insert({l , pos - 1 , val}) ;
	return s.insert({pos , r , val}).first ;
}
inline int Assign(int l , int r , int val) {
	slt it2 = Split(r + 1) ;
	slt it1 = Split(l) ;
	int sum = 0 ;
	int sum2 = (r - l + 1) * val  ;
	for(slt it = it1 ; it != it2 ; it ++) sum += (it -> r - it -> l + 1) * it -> val ;
	s.erase(it1 , it2) ;
	s.insert({l , r , val}) ;
	return abs(sum - sum2) ;
}
int n ;
struct Node {
	int v ;
	int nxt ;
};
const int N = 1e5 + 10 ;
Node e[N << 1] ;
int cnt = 0 ;
int head[N] ;
inline void Add(int u , int v) {
	e[++ cnt].v = v ;
	e[cnt].nxt = head[u] ;
	head[u] = cnt ;
	return ;
}
int top[N] ;
int id[N] ; int size[N] ;
int d[N] ; int idx = 0 ;
int fa[N] ; int son[N] ;
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]) continue ;
		d[v] = d[u] + 1 ;
		fa[v] = u ;
		Dfs1(v) ;
		size[u] += size[v] ;
		if(size[v] > size[son[u]]) son[u] = v ;
	}
	return ;
}
inline void Dfs2(int u , int t) {
	id[u] = ++ idx ;
	top[u] = t ;
	if(! son[u]) return ;
	Dfs2(son[u] , t) ;
	for(register int i = head[u] ; i ; i = e[i].nxt) {
		int v = e[i].v ;
		if((v ^ fa[u]) &amp;&amp; (v ^ son[u])) Dfs2(v , v) ;
	}
}
inline int getopt() { string s = "" ;
	register char c = getchar() ;
	while(isspace(c)) c = getchar() ;
	while(! isspace(c)) {
		s += c ;
		c = getchar() ;
	}
	if(s == "install") return 1 ;
	if(s == "uninstall") return 0 ;
}
inline int Change_Range(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 += Assign(id[fx] , id[x] , 1) ;
		x = fa[fx] ;
		fx = top[x] ;
	}
	if(id[x] > id[y]) swap(x , y) ;
	ans += Assign(id[x] , id[y] , 1) ;
	return ans ;
}
inline int Uninstall(int x) {
	return Assign(id[x] , id[x] + size[x] - 1 , 0) ;
}
signed main() {
#ifdef Online_Judge
	freopen("testdata.in" , "r" , stdin) ;
	freopen("testdata2.out" , "w" , stdout) ;
#endif
	n = read() ;
	s.insert({1 , n + 1 , 0}) ;
	for(register int i = 2 ; i <= n ; i ++) {
		int u = read() ; u ++ ;
		Add(u , i) ;
		Add(i , u) ;
	}
	Dfs1(1) ;
	Dfs2(1 , 1) ;
	for(register int t = read() ; t -- ; ) {
		int opt = getopt() ;
		if(opt == 1) {
			int x = read() ; x ++ ;
			write(Change_Range(x , 1)) ;
		}
		if(opt == 0) {
			int x = read() ; x ++ ;
			write(Uninstall(x)) ;
		}
	}
	return 0 ;
}

Count on a tree

给定一棵$N$个节点的树,每个点有一个权值,对于$M$个询问$(u,v,k)$,你需要回答$u xor lastans$和$v$这两个节点间第$K$小的点权。其中$lastans$是上一个询问的答案,初始为$0$,即第一个询问的$u$是明文。

因为是强制在线,所以用主席树求静态区间第$K$大

#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 &amp; 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
const int N = 1e5 + 10 ;
const int M = N << 5 ;
int n , q ; int m ;
int sum[M] , L[M] , R[M] ;
int a[N] , b[N] , rt[N] ;
struct node{
	int v ;
	int nxt ;
};
node e[N << 1] ;
int head[N] ;
int fa[N] , size[N] , d[N] , son[N] , top[N] ;
int cnt =  0 ; 
inline void Add(int u , int v) {
	e[ ++ cnt] . v = v ;
	e[ cnt] . nxt = head[u] ;
	head[u] = cnt ;
	return ;
}
int tot = 0 ;
inline void Update(int last , int &amp; now , int l , int r , int x) { // 动态开点 主席树基操
	sum[now = ++ tot] = sum[last] + 1 ;
	if(l == r) return ;
	int mid = l + r >> 1 ;
	if(x <= mid) R[now] = R[last] , Update(L[last] , L[now] , l , mid , x) ;
	else L[now] = L[last] , Update(R[last] , R[now] , mid + 1 , r , x) ;
	return ;
}
inline int Query(int a , int b , int lca ,int lca_fa , int l , int r , int k) { // 求 k 小…
	if(l >= r) return l ;
	int x = sum[L[a]] + sum[L[b]] - sum[L[lca]] - sum[L[lca_fa]] ;
	int mid = l + r >> 1 ;
	if(x >= k) return Query(L[a] , L[b] , L[lca] , L[lca_fa] , l , mid , k) ;
	else return Query(R[a] , R[b] , R[lca] , R[lca_fa] , mid + 1 , r , k - x) ;
}

inline void Dfs(int u) {
	size[u] = 1 ;
	Update(rt[fa[u]] , rt[u] , 1 , m , a[u]) ;
	for(register int i = head[u] ; i ; i = e[i].nxt) {
		int v = e[i].v ;
		if(v == fa[u]) continue ;
		fa[v] = u  ;
		d[v] = d[u] + 1 ;
		Dfs(v) ;
		size[u] += size[v] ;
		if(size[v] > size[son[u]]) son[u] = v ;
	}
}
inline void Dfs2(int u , int t) {
	top[u] = t ;
	if(! son[u]) return ;
	Dfs2(son[u] , t) ;
	for(register int i = head[u] ; i ; i = e[i].nxt) {
		int v = e[i].v ;
		if(v ^ fa[u] &amp;&amp; v ^ son[u]) Dfs2(v , v) ;
	}
}
inline int Lca(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) ;
		x = fa[fx] ;
		fx = top[x] ;
	}
	if(d[x] > d[y]) swap(x , y) ;
	return x ;
}
signed main() {
#ifdef Online_Judge
	freopen("testdata.in" , "r" , stdin) ;
	freopen("testdata2.out" , "w" , stdout) ;
#endif
	n = read() , q = read() ;
	for(register int i = 1 ; i <= n ; i ++) a[i] = read() ;
	for(register int i = 1 ; i <= n ; i ++) b[i] = a[i] ;
	sort(b + 1 , b + n + 1) ;
	m = unique(b + 1 , b + 1 + n) - b - 1 ;
	for(register int i = 1 ; i <= n ; i ++) 
		a[i] = lower_bound(b + 1 , b + m + 1 , a[i]) - b ;
	for(register int i = 1 ; i <= n - 1 ; i ++) {
		int u = read() , v = read() ;
		Add(u , v) ;
		Add(v , u) ;
	}
	Dfs(1) ;
	Dfs2(1 , 1) ;
	int ans = 0 ;
	for(register int i = 1 ; i <= q ; i ++) {
		int x = read() ^ ans , y = read() ;
		int lca = Lca(x , y) ;
		int z = read() ;
		write(ans = b[Query(rt[x] , rt[y] , rt[lca] , rt[fa[lca]] , 1 , m , z)]) ;
	}
	return 0 ;
}

发表评论

textsms
account_circle
email

一些树链剖分的题目(1)
手残党的噩梦😏 SPOJ-QTREE 这道题把边权转化成点权,单点修改就行 #include<bits/stdc++.h> using namespace std ; inline int read() { register int x = 0 ; register i…
扫描二维码继续阅读
2020-04-18