起因是发现自己脑子并不好使老忘。

DSU on Tree

先树剖。

Func Modify = [] (int cur ,int op) -> void {
    if (op) max = std :: max (max ,tr.Query (a[cur]).first) ,tr.Insert (a[cur] ,0) ;
    else tr.Del (a[cur]) ;
    for (int i = head[cur] ; i ; i = e[i].nxt) {
        int nex = e[i].to ; 
        if (nex == fa[cur] || nex == son) continue ;
        Modify (nex ,op) ;
    }
} ;

Func Solve = [] (int cur ,int op) -> void {
    for (int i = head[cur] ; i ; i = e[i].nxt) {
        int nex = e[i].to ;
        if (nex == fa[cur] || nex == hson[cur]) continue ;
        Solve (nex ,0) ;
    } if (hson[cur]) Solve (hson[cur] ,1) ,son = hson[cur] ;
    Modify (cur ,1) ,ans2[cur] = max ,son = 0 ;
    if (!op) Modify (cur ,0) ,max = 0 ;
} ;

题目：P6072 『MdOI R1』Path – 洛谷

Chtholly Tree

#include "bits/stdc++.h"
#define int long long 
#define f(i ,m ,n ,x) for (int i = (m) ; i <= (n) ; i += (x))

template < typename T > inline void read ( T &x ) {
    x = 0 ; 
    bool flag (0) ; char ch = getchar () ;
    while (! isdigit (ch)) {
        flag = ch == '-' ;
        ch = getchar () ;
    } while (isdigit (ch)) {
        x = (x << 1) + (x << 3) + (ch ^ 48) ;
        ch = getchar () ;
    } flag ? x = - x : 0 ;
} template < typename T ,typename ...Args >
inline void read ( T &x ,Args &...tmp ) {
    read (x) ,read (tmp...) ;
}

int n ,m ,seed ,vmax ;

struct node {
    int l ,r ;
    mutable int v ;
    node (int l ,int r ,int v) : l (l) ,r (r) ,v (v) {}
    bool operator < (const node &cmp) const { return l < cmp.l ;}
} ;

namespace ChthollyTree {
    std :: set < node > s ;
     
    auto split = [] (int x) -> decltype (s.begin ()) {
        auto it = s.lower_bound (node (x ,0 ,0)) ;
        if (it != s.end () && it -> l == x) return it ;
        it -- ;
        int l = it -> l ,r = it -> r ,v = it -> v ;
        s.erase (it) ,s.insert (node (l ,x - 1 ,v)) ;
        return s.insert (node (x ,r ,v)).first ;
    } ;
    
    auto modify = [] (int l ,int r ,int x) -> void {
        auto it2 = split (r + 1) ,it1 = split (l) ;
        for (; it1 != it2 ; it1 ++) it1 -> v += x ;
        return ;
    } ;
    
    auto cover = [] (int l ,int r ,int x) -> void {
        auto it2 = split (r + 1) ,it1 = split (l) ;
        s.erase (it1 ,it2) ;
        s.insert (node (l ,r ,x)) ;
    } ;
    
    auto rank = [] (int l ,int r ,int x) -> int {
        static std :: vector < std :: pair < int ,int > > v ; v.clear () ;
        auto it2 = split (r + 1) ,it1 = split (l) ;
        for (; it1 != it2 ; it1 ++) 
            v.emplace_back (std :: make_pair (it1 -> v ,it1 -> r - it1 -> l + 1)) ;
        std :: sort (v.begin () ,v.end ()) ;
        for (auto it = v.begin () ; it != v.end () ; it ++) {
            x -= it -> second ;
            if (x <= 0) return it -> first ;
        }
    } ;
    
    auto qpow = [] (int bs ,int p ,int mod) -> int {
        int ans = 1ll ; bs %= mod ;
        for (; p ; p >>= 1 ,bs = bs * bs % mod)
            ((p & 1) && (ans = ans * bs % mod)) ;
        return ans ;	
    } ;
    
    auto query = [] (int l ,int r ,int x ,int y) -> int {
        int ans = 0ll ;
        auto it2 = split (r + 1) ,it1 = split (l) ;
        for (; it1 != it2 ; it1 ++)
            (ans += qpow (it1 -> v ,x ,y) * (it1 -> r - it1 -> l + 1) % y) %= y ;
        return ans ; 
    } ; 
}

auto rnd = [] () -> int {
    int res = seed ; 
    seed = (seed * 7 + 13) % 1000000007 ; return res ;
} ;

signed main () {
    read (n ,m ,seed ,vmax) ;
    f (i ,1 ,n ,1) {
        int a = rnd () % vmax + 1 ;
        ChthollyTree :: s.insert (node (i ,i ,a)) ;
    } 
    while (m --) {
        int op = rnd () % 4 + 1 ,l = rnd () % n + 1 ,r = rnd () % n + 1 ,x ,y ;
        if (l > r) std :: swap (l ,r) ;
        if (op == 3) x = rnd () % (r - l + 1) + 1 ;
        else x = rnd () % vmax + 1 ;
        if (op == 4) y = rnd () % vmax + 1 ;
        switch (op) {
            case 1 : { ChthollyTree :: modify (l ,r ,x) ; break ;}
            case 2 : { ChthollyTree :: cover (l ,r ,x) ; break ;}
            case 3 : { std :: cout << ChthollyTree :: rank (l ,r ,x) << '\n' ; break ;}
            case 4 : { std :: cout << ChthollyTree :: query (l ,r ,x ,y) << '\n' ; break ;}
        }
    }
    return 0 ;
}

题目：CF896C