猫树

简介

给出一个某种元素的序列 $a_1,a_2,\cdots, a_n$，要求进行 $m$ 次询问，每次询问是一段区间 $[l,r]$ 的某种支持结合律和快速合并的信息，要求在线

然后猫树大概就是用来处理这种东西的数据结构(?)，利用猫树，我们可以做到 $O(n\log n)$ 的预处理和 $O(1)$ 的询问

大概的思路就是按照线段树的分治处理的做法，但对于线段树上的每个区间，我们不只存储这个区间整个的信息，而是存储这个区间每个位置到中点的这个前缀或者是后缀的信息，注意到对于一般的 $[1,n]$ 的线段树并没有什么太好的性质，但如果是 $[1,2^k]$ 的线段树，对于一个询问的 $[l,r]$，我们可以 $O(1)$ 找到将这区间分成两半的那个分割点，从而 $O(1)$ 完成合并求出 $[l,r]$ 的信息

模板

最大子段和

#include <iostream>
#include <algorithm>
#define maxn 50010
using namespace std;

int n, m, a[maxn * 2];

int N;
#define lc (o << 1)
#define rc (o << 1 | 1)
struct Meow {
    int v, max;
} T[maxn * 4][21]; int Log[maxn * 4], pos[maxn * 4];
void init_Meow(int n) {
    N = 1; while (N < n) N <<= 1;
    Log[0] = -1; for (int i = 1; i <= N * 2; ++i) Log[i] = Log[i >> 1] + 1;
}

void build(int o, int l, int r, int d) {
    if (l == r) return T[l][d].v = T[l][d].max = a[l], pos[l] = o, void();
    int m = l + r >> 1, sum = 0, maxsum = 0;
    
    T[m][d].max = T[m][d].v = sum = a[m]; maxsum = max(a[m], 0);
    for (int i = m - 1; i >= l; --i) {
        sum += a[i]; maxsum += a[i];
        T[i][d].max = max(T[i + 1][d].max, sum);
        T[i][d].v = max(T[i + 1][d].v, maxsum);
        maxsum = max(maxsum, 0);
    }
    
    T[m + 1][d].max = T[m + 1][d].v = sum = a[m + 1]; maxsum = max(a[m + 1], 0);
    for (int i = m + 2; i <= r; ++i) {
        sum += a[i]; maxsum += a[i];
        T[i][d].max = max(T[i - 1][d].max, sum);
        T[i][d].v = max(T[i - 1][d].v, maxsum);
        maxsum = max(maxsum, 0);
    }
    build(lc, l, m, d + 1); build(rc, m + 1, r, d + 1); 
}

inline int query(int l, int r) {
    int d = Log[pos[l]] - Log[pos[l] ^ pos[r]];
    if (l == r) return T[l][d].v;
    return max({ T[l][d].v, T[r][d].v, T[l][d].max + T[r][d].max });
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    init_Meow(n); build(1, 1, N, 1); 
    cin >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y; cin >> x >> y;
        cout << query(x, y) << "\n";
    }
    return 0;
} 

猫树在点分树上的拓展

猫树的核心思想为，将区间分为 $O(\log n)$ 层，每层处理每个点到区间中心点的答案。而点分树正好提供了这样的划分，所以我们只需要在点分治的过程中预处理所有点到子树分治中心（重心）的答案，然后在回答询问时只需要找到对应的点在点分树上的 LCA 即可

模板

简要题意：给一棵大小为 $n$ 的树，每个点有点权，有 $m$ 次询问，每次询问 $(u,v)$ 的路径上不能选相邻的点的最大点权和

$n\le 5\times 10^5,m\le 10^7$

简要题解：用矩阵维护 $dp$ 值

#include <iostream>
#include <algorithm>
#define maxn 500010
#define ll long long
#define INF 1000000000000000000
using namespace std;

const int p = 998244353;

int n, m, seed, a[maxn];

struct Rand{
    unsigned int n,seed;
    Rand(unsigned int n,unsigned int seed)
    :n(n),seed(seed){}
    int get(long long lastans){
        seed ^= seed << 13;
        seed ^= seed >> 17;
        seed ^= seed << 5;
        return (seed^lastans)%n+1;
    }
};

struct Matrix {
    const static int n = 2; 
    ll a[2][2];

    Matrix() { fill(a[0], a[0] + 4, -INF); }

    void setone() { for (int i = 0; i < n; ++i) a[i][i] = 0; }

    void set(ll x, ll y, ll z, ll w) {
        a[0][0] = x; a[0][1] = y;
        a[1][0] = z; a[1][1] = w; 
    }

    friend Matrix operator * (const Matrix &u, const Matrix &v) {
        Matrix w; 
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j) w.a[i][j] = max(u.a[i][1] + v.a[1][j], u.a[i][0] + v.a[0][j]);
        return w; 
    }
} emptyM;

struct Edge {
    int to, next; 
} e[maxn * 2]; int c1, head[maxn];
inline void add_edge(int u, int v) {
    e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}

int R[maxn]; bool vis[maxn];
struct Calc_sz {
    int f[maxn], sz[maxn];
    int sum, rt, maxdp;

    void init() { f[rt = 0] = 1e9; }

    void dfs_sz(int u, int fa) {
        sz[u] = 1; 
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to; if (v == fa || vis[v]) continue;
            dfs_sz(v, u); sz[u] += sz[v]; 
        }
    }

    void dfs(int u, int fa) {
        f[u] = 0;
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to; if (v == fa || vis[v]) continue;
            dfs(v, u); f[u] = max(f[u], sz[v]); 
        } f[u] = max(f[u], sum - sz[u]);
        if (f[u] < f[rt]) rt = u; 
    }

    inline int get_rt(int u) {
        rt = maxdp = 0; dfs_sz(u, 0); sum = sz[u];
        dfs(u, 0); return rt; 
    }
} _;

Matrix f[maxn][21];
void dfs(int u, int fa, int d) {
    f[u][d].set(0, 0, a[u], -INF); f[u][d] = f[fa][d] * f[u][d];
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa || vis[v]) continue;
        dfs(v, u, d);
    }
}

int id[2 * maxn], in[maxn], dep[maxn];
void divide(int u, int d) {
    static int cnt = 0;
    id[++cnt] = u; in[u] = cnt; vis[u] = 1; dep[u] = d;
    f[u][d].set(0, -INF, -INF, 0);
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (vis[v]) continue;
        dfs(v, u, d); divide(_.get_rt(v), d + 1); id[++cnt] = u; 
    }
    f[u][d].set(0, 0, a[u], -INF);
}

inline int st_min(int l, int r) { return in[l] < in[r] ? l : r; }

int st[maxn * 2][21], Log[maxn * 2];
void init_st(int n) { Log[0] = -1;
    for (int i = 1; i <= n; ++i) Log[i] = Log[i >> 1] + 1;
    for (int i = 1; i <= n; ++i) st[i][0] = id[i];
    for (int j = 1; j <= 20; ++j)
        for (int i = 1; i + (1 << j) - 1 <= n; ++i)
            st[i][j] = st_min(st[i][j - 1], st[i + (1 << j - 1)][j - 1]); 
}

inline int get_lca(int l, int r) {
    l = in[l]; r = in[r]; if (l > r) swap(l, r);
    int k = Log[r - l + 1];
    return st_min(st[l][k], st[r - (1 << k) + 1][k]);
}

ll query(int x, int y) {
    int lca = get_lca(x, y), d = dep[lca];
    if (dep[x] > dep[y]) swap(x, y);
    if (lca == x) return max(max(f[y][d].a[0][0], f[y][d].a[1][0]), a[x] + f[y][d].a[0][0]);
    return max(max(f[x][d].a[0][0], f[x][d].a[1][0]) + max(f[y][d].a[0][0], f[y][d].a[1][0]),
               a[lca] + f[x][d].a[0][0] + f[y][d].a[0][0]);
}

int main() { fill(head, head + maxn, -1); 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m >> seed;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 2, x; i <= n; ++i) cin >> x, add_edge(x, i), add_edge(i, x);
    _.init(); divide(_.get_rt(1), 1); init_st(2 * n - 1);
    ll lans = 0, ans = 0; Rand rand(n, seed);
    for (int i = 1; i <= m; ++i) {
        int u = rand.get(lans);
        int v = rand.get(lans);
        int x = rand.get(lans);
        lans = query(u, v);
        ans = (ans + lans % p * x) % p; 
    } cout << ans << "\n";
    return 0;
}