P4069 [SDOI2016] 游戏

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5;

struct Edge {
    int to, next;
} edge[maxn << maxn];
int head[maxn], tot;
int color[maxc];
int n, m; // 题目中n为节点数，m可能为颜色数

// 树链剖分
int fa[maxn], depth[maxn], size[maxn], heavy[maxn], top[maxn], pos[maxn], current_pos;
int parent[maxn][20]; // 倍增LCA

// 李超树节点
struct LCTNode {
    int l, r;
    unordered_map<int, int> last; // 颜色到位置的映射
    LCTNode *left, *right;
    LCTNode(int l, int r) : l(l), r(r), left(nullptr), right(nullptr) {}
};

LCTNode* build(int l, int r) {
    LCTNode* node = new LCTNode(l, r);
    if (l == r) return node;
    int mid = (l + r) >> 1;
    node->left = build(l, mid);
    node->right = build(mid + 1, r);
    return node;
}

void update(LCTNode* node, int c, int pos) {
    if (node->l == node->r) {
        if (node->last.find(c) == node->last.end() || node->last[c] < pos) {
            node->last[c] = pos;
        }
        return;
    }
    int mid = (node->l + node->r) >> 1;
    if (c <= mid) {
        update(node->left, c, pos);
    } else {
        update(node->right, c, pos);

C120 树剖+李超树 P4069 [SDOI2016] 游戏