Problem 1: Subtree Color Dominance

This problem requires finding the most frequent color in each subtree. A naive approach uses Mo's algorithm on the Euler tour of the tree combined with a segment tree tracking color frequencies. The Euler tour flattens the tree into an array where each subtree corresponds to a contiguous range.

However, the optimal solution employs DSU on Tree (small-to-large merging). The key insight is that when processing a node, we can retain the data structure for its heaviest child and only merge information from lighter children, achieving O(n log n) complexity.

const int MAXN = 200005;
vector<int> graph[MAXN];
int color[MAXN], subtreeSize[MAXN], eulerTour[MAXN];
int position[MAXN], currentTime = 0;
int frequency[MAXN], maxFrequency = 0;
long long sumOfDominantColors = 0;
bool isHeavy[MAXN];
vector<int> *storedColors[MAXN];

void computeSubtreeSizes(int node, int parent) {
    position[node] = ++currentTime;
    eulerTour[currentTime] = node;
    subtreeSize[node] = 1;
    for (int neighbor : graph[node]) {
        if (neighbor == parent) continue;
        computeSubtreeSizes(neighbor, node);
        subtreeSize[node] += subtreeSize[neighbor];
    }
}

void addColor(int node) {
    int col = color[node];
    frequency[col]++;
    if (frequency[col] > maxFrequency) {
        maxFrequency = frequency[col];
        sumOfDominantColors = col;
    } else if (frequency[col] == maxFrequency) {
        sumOfDominantColors += col;
    }
}

void removeColor(int node) {
    int col = color[node];
    frequency[col]--;
}

void dfs(int node, int parent, bool keep) {
    int maxChildSize = 0, heavyChild = -1;
    for (int neighbor : graph[node]) {
        if (neighbor == parent) continue;
        if (subtreeSize[neighbor] > maxChildSize) {
            maxChildSize = subtreeSize[neighbor];
            heavyChild = neighbor;
        }
    }
    
    for (int neighbor : graph[node]) {
        if (neighbor == parent || neighbor == heavyChild) continue;
        dfs(neighbor, node, false);
    }
    
    if (heavyChild != -1) {
        dfs(heavyChild, node, true);
        storedColors[node] = storedColors[heavyChild];
    } else {
        storedColors[node] = new vector<int>();
    }
    
    for (int neighbor : graph[node]) {
        if (neighbor == parent || neighbor == heavyChild) continue;
        for (int i = position[neighbor]; i < position[neighbor] + subtreeSize[neighbor]; i++) {
            addColor(eulerTour[i]);
        }
    }
    
    addColor(node);
    answer[node] = sumOfDominantColors;
    
    if (!keep) {
        for (int i = position[node]; i < position[node] + subtreeSize[node]; i++) {
            removeColor(eulerTour[i]);
        }
        maxFrequency = 0;
        sumOfDominantColors = 0;
    }
}

Problem 2: Amphibian Predators and Prey

Given frogs with positions and tongue lengths, and mosquitoes with positions and nutritional values, we need to simulate the eating process efficiently. When a frog eats a mosquito, its tongue length inrceases, potentially allowing it to reach more mosquitoes.

The solution preprocesses frogs to maintain monotonicity in their reachable intervals, enabling binary search. A balanced BST (multiset) stores uneaten mosquitoes.

struct Amphibian {
    int position, tongueLength, originalIndex;
};

struct Insect {
    int position, nutrition;
    bool operator<(const Insect& other) const {
        return position < other.position;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int frogCount, insectCount;
    cin >> frogCount >> insectCount;
    
    vector<Amphibian> frogs(frogCount);
    for (int i = 0; i < frogCount; i++) {
        cin >> frogs[i].position >> frogs[i].tongueLength;
        frogs[i].originalIndex = i;
    }
    
    sort(frogs.begin(), frogs.end(), [](const Amphibian& a, const Amphibian& b) {
        return a.position < b.position;
    });
    
    vector<Amphibian> validFrogs;
    int maxReach = INT_MIN;
    for (const auto& frog : frogs) {
        if (frog.position + frog.tongueLength > maxReach) {
            validFrogs.push_back(frog);
            maxReach = frog.position + frog.tongueLength;
        }
    }
    
    multiset<Insect> remainingInsects;
    vector<int> consumptionCount(frogCount, 0);
    vector<long long> totalNutrition(frogCount, 0);
    
    for (int i = 0; i < insectCount; i++) {
        int pos, nut;
        cin >> pos >> nut;
        remainingInsects.insert({pos, nut});
    }
    
    while (!remainingInsects.empty()) {
        auto it = remainingInsects.begin();
        int pos = it->position;
        
        int left = 0, right = validFrogs.size() - 1, target = -1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (validFrogs[mid].position <= pos) {
                target = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        if (target == -1 || validFrogs[target].position + validFrogs[target].tongueLength < pos) {
            remainingInsects.erase(it);
            continue;
        }
        
        int idx = validFrogs[target].originalIndex;
        consumptionCount[idx]++;
        totalNutrition[idx] += it->nutrition;
        validFrogs[target].tongueLength += it->nutrition;
        remainingInsects.erase(it);
        
        while (true) {
            auto nextIt = remainingInsects.lower_bound({validFrogs[target].position, 0});
            if (nextIt == remainingInsects.end()) break;
            if (validFrogs[target].position + validFrogs[target].tongueLength < nextIt->position) break;
            
            consumptionCount[idx] += 1;
            totalNutrition[idx] += nextIt->nutrition;
            validFrogs[target].tongueLength += nextIt->nutrition;
            remainingInsects.erase(nextIt);
        }
    }
    
    for (int i = 0; i <frogCount; i++) {
        cout << consumptionCount[i] << " " << totalNutrition[i] << "\n";
    }
    return 0;
}

Problem 3: Binary Segment Tree Opitmization

This problem involves a segment tree where each node stores a binary value representing some property of its interval. The solution leverages bitwise operations for efficient updates and queries, typically using lazy propagation for range assignments.

Problem 4: 2D Prefix Counting with Fenwick Trees

Given a binary matrix, we need to count specific patterns. For each cell acting as a corner, we calculate contributions using prefix sums and process queries offline with Fenwick trees.

const int MAXM = 3005;
char grid[MAXM][MAXM];
int horizontalOnes[MAXM][MAXM], diagonalOnes[MAXM][MAXM];

struct FenwickTree {
    int bit[MAXM];
    void update(int idx, int delta) {
        for (; idx < MAXM; idx += idx & -idx) bit[idx] += delta;
    }
    int query(int idx) {
        int sum = 0;
        for (; idx > 0; idx -= idx & -idx) sum += bit[idx];
        return sum;
    }
    int rangeQuery(int l, int r) {
        return query(r) - query(l - 1);
    }
    void clear() {
        memset(bit, 0, sizeof(bit));
    }
};

struct Event {
    int x, y, type, value;
    bool operator<(const Event& other) const {
        return value < other.value;
    }
};

int main() {
    int rows, cols;
    cin >> rows >> cols;
    
    for (int i = 1; i <= rows; i++) {
        for (int j = 1; j <= cols; j++) {
            cin >> grid[i][j];
            horizontalOnes[i][j] = (grid[i][j] == 'z') ? horizontalOnes[i][j-1] + 1 : 0;
        }
    }
    
    for (int i = rows; i >= 1; i--) {
        for (int j = 1; j <= cols; j++) {
            diagonalOnes[i][j] = (grid[i][j] == 'z') ? diagonalOnes[i+1][j-1] + 1 : 0;
        }
    }
    
    vector<Event> addEvents, queryEvents;
    for (int i = 1; i <= rows; i++) {
        for (int j = 1; j <= cols; j++) {
            if (grid[i][j] == 'z') {
                addEvents.push_back({i, j, 0, i - horizontalOnes[i][j] + 1});
                queryEvents.push_back({i, i + min(horizontalOnes[i][j], diagonalOnes[i][j]) - 1, j, 0, i});
            }
        }
    }
    
    sort(addEvents.begin(), addEvents.end());
    sort(queryEvents.begin(), queryEvents.end());
    
    FenwickTree ft[MAXM];
    int eventIdx = 0;
    long long answer = 0;
    
    for (auto& qe : queryEvents) {
        while (eventIdx < addEvents.size() && addEvents[eventIdx].value <= qe.value) {
            ft[addEvents[eventIdx].y].update(addEvents[eventIdx].x, 1);
            eventIdx++;
        }
        answer += ft[qe.y].rangeQuery(qe.x, qe.type);
    }
    
    cout << answer << endl;
    return 0;
}

Problem 5: Dynamic Line Queries with Segment Tree of Li Chao Trees

Handling insertion, deletion, and query operations on linear functions requires segment tree divide and conquer to manage function lifespans, with each node containing a Li Chao tree for maximum evaluation.

const int MAXQ = 200005;
const int INF = 1e9;

struct LinearFunction {
    long long slope, intercept;
    long long eval(long long x) const {
        return slope * x + intercept;
    }
};

struct LiChaoNode {
    int leftChild, rightChild;
    int functionId;
};

struct SegmentTreeNode {
    int liChaoRoot;
};

SegmentTreeNode segTree[MAXQ * 4];
LiChaoNode liChaoNodes[MAXQ * 40];
int liChaoCount = 0;

void insertLine(int& node, int l, int r, int newFuncId, const vector<LinearFunction>& funcs) {
    if (!node) {
        node = ++liChaoCount;
        liChaoNodes[node].functionId = newFuncId;
        return;
    }
    
    int mid = (l + r) / 2;
    int curFunc = liChaoNodes[node].functionId;
    
    if (funcs[newFuncId].eval(mid) > funcs[curFunc].eval(mid)) {
        swap(liChaoNodes[node].functionId, newFuncId);
    }
    
    if (l == r) return;
    
    if (funcs[newFuncId].eval(l) > funcs[liChaoNodes[node].functionId].eval(l)) {
        insertLine(liChaoNodes[node].leftChild, l, mid, newFuncId, funcs);
    } else if (funcs[newFuncId].eval(r) > funcs[liChaoNodes[node].functionId].eval(r)) {
        insertLine(liChaoNodes[node].rightChild, mid+1, r, newFuncId, funcs);
    }
}

void updateSegmentTree(int node, int l, int r, int ql, int qr, int funcId, const vector<LinearFunction>& funcs) {
    if (ql <= l && r <= qr) {
        insertLine(segTree[node].liChaoRoot, -INF, INF, funcId, funcs);
        return;
    }
    
    int mid = (l + r) / 2;
    if (ql <= mid) updateSegmentTree(node*2, l, mid, ql, qr, funcId, funcs);
    if (qr > mid) updateSegmentTree(node*2+1, mid+1, r, ql, qr, funcId, funcs);
}

long long queryLiChao(int node, int l, int r, long long x, const vector<LinearFunction>& funcs) {
    if (!node) return LLONG_MIN;
    
    long long res = funcs[liChaoNodes[node].functionId].eval(x);
    if (l == r) return res;
    
    int mid = (l + r) / 2;
    if (x <= mid) return max(res, queryLiChao(liChaoNodes[node].leftChild, l, mid, x, funcs));
    else return max(res, queryLiChao(liChaoNodes[node].rightChild, mid+1, r, x, funcs));
}

long long querySegmentTree(int node, int l, int r, int idx, long long x, const vector<LinearFunction>& funcs) {
    long long res = queryLiChao(segTree[node].liChaoRoot, -INF, INF, x, funcs);
    if (l == r) return res;
    
    int mid = (l + r) / 2;
    if (idx <= mid) return max(res, querySegmentTree(node*2, l, mid, idx, x, funcs));
    else return max(res, querySegmentTree(node*2+1, mid+1, r, idx, x, funcs));
}

Problem 6: 3D Dominance Counting

Counting pairs of points where one dominates another in three dimensions is solved via CDQ divide and conquer, sorting by one dimension and using Fenwick trees for the other two.

struct Point {
    int x, range, frequency, leftBound, rightBound;
};

struct Fenwick {
    int tree[MAXN * 3];
    void update(int idx, int delta) {
        for (; idx < MAXN * 3; idx += idx & -idx) tree[idx] += delta;
    }
    int query(int idx) {
        int sum = 0;
        for (; idx > 0; idx -= idx & -idx) sum += tree[idx];
        return sum;
    }
    int rangeQuery(int l, int r) {
        return query(r) - query(l - 1);
    }
    void reset() {
        memset(tree, 0, sizeof(tree));
    }
};

vector<Point> points;
int answer = 0;

void cdqDivide(int l, int r) {
    if (l >= r) return;
    int mid = (l + r) / 2;
    cdqDivide(l, mid);
    cdqDivide(mid + 1, r);
    
    sort(points.begin() + l, points.begin() + mid + 1, [](const Point& a, const Point& b) {
        return a.frequency < b.frequency;
    });
    sort(points.begin() + mid + 1, points.begin() + r + 1, [](const Point& a, const Point& b) {
        return a.frequency < b.frequency;
    });
    
    Fenwick ft;
    int i = l, j = mid + 1;
    while (j <= r) {
        while (i <= mid && points[mid].frequency - points[i].frequency <= k) {
            ft.update(points[i].x, 1);
            i++;
        }
        while (j <= r && points[j].frequency - points[mid].frequency > k) j++;
        if (j > r) break;
        answer += ft.rangeQuery(points[j].leftBound, points[j].rightBound);
        j++;
    }
}

Problem 7: Periodic Range Minimum Queries

For an array constructed by repeating a base pattern, we need dynamic updates and RMQ. The solution uses a sparse table for the base pattern and a dynamically allocated segment tree for modifications.

const int LOG = 20;
const int BASE_SIZE = 100005;
int sparseTable[LOG][BASE_SIZE];
int prefixMin[BASE_SIZE], suffixMin[BASE_SIZE];
int globalMin, baseLength, totalLength;

int sparseQuery(int l, int r) {
    int j = log2(r - l + 1);
    return min(sparseTable[j][l], sparseTable[j][r - (1 << j) + 1]);
}

void buildSparseTable() {
    for (int j = 1; (1 << j) <= baseLength; j++) {
        for (int i = 1; i + (1 << j) - 1 <= baseLength; i++) {
            sparseTable[j][i] = min(sparseTable[j-1][i], sparseTable[j-1][i + (1 << (j-1))]);
        }
    }
}

struct DynamicNode {
    int left, right, value, lazy;
};

vector<DynamicNode> dynamicTree;
int root = 1;

void propagate(int node, int l, int r) {
    if (!dynamicTree[node].lazy) return;
    int val = dynamicTree[node].lazy;
    if (l != r) {
        if (!dynamicTree[node].left) dynamicTree[node].left = dynamicTree.size();
        if (!dynamicTree[node].right) dynamicTree[node].right = dynamicTree.size();
        dynamicTree[dynamicTree[node].left].lazy += val;
        dynamicTree[dynamicTree[node].right].lazy += val;
        dynamicTree[dynamicTree[node].left].value += val;
        dynamicTree[dynamicTree[node].right].value += val;
    }
    dynamicTree[node].lazy = 0;
}

void rangeUpdate(int& node, int l, int r, int ql, int qr, int val) {
    if (!node) {
        node = dynamicTree.size();
        dynamicTree.push_back({0, 0, queryPeriodic(l, r), 0});
    }
    if (ql <= l && r <= qr) {
        dynamicTree[node].lazy += val;
        dynamicTree[node].value += val;
        return;
    }
    propagate(node, l, r);
    int mid = (l + r) / 2;
    if (ql <= mid) rangeUpdate(dynamicTree[node].left, l, mid, ql, qr, val);
    if (qr > mid) rangeUpdate(dynamicTree[node].right, mid+1, r, ql, qr, val);
    dynamicTree[node].value = min(dynamicTree[dynamicTree[node].left].value, 
                                   dynamicTree[dynamicTree[node].right].value);
}

Problem 8: Range Assignment and MEX Queries

Maintaining an array with range assign, range flip, and finding the first zero is efficiently handled by an Ordered Set (ODT/Chtholly Tree) when data is random.

struct Interval {
    int left, right;
    mutable int value;
    bool operator<(const Interval& other) const {
        return left < other.left;
    }
};

set<Interval> odt;

auto split(int position) {
    auto it = odt.lower_bound({position, 0, 0});
    if (it != odt.end() && it->left == position) return it;
    it--;
    int l = it->left, r = it->right, v = it->value;
    odt.erase(it);
    odt.insert({l, position - 1, v});
    return odt.insert({position, r, v}).first;
}

void assignRange(int l, int r, int val) {
    auto end = split(r + 1);
    auto start = split(l);
    odt.erase(start, end);
    odt.insert({l, r, val});
}

void flipRange(int l, int r) {
    auto end = split(r + 1);
    for (auto it = split(l); it != end; ++it) {
        it->value ^= 1;
    }
}

int findFirstZero() {
    for (const auto& interval : odt) {
        if (interval.value == 0) return interval.left;
    }
    return -1;
}

Problem 9: Persistent Segment Tree for Functions

Handling multiple versions of line segments requires a persistent segment tree where each update creates a new version, and queries subtract versions to get interval contributions.

struct PersistentNode {
    int left, right;
    long long sumA, sumB;
};

vector<PersistentNode> persistentTree;
int versionRoot[MAXN];

int updateVersion(int prevRoot, int l, int r, int pos, int deltaA, int deltaB) {
    int newRoot = persistentTree.size();
    persistentTree.push_back(persistentTree[prevRoot]);
    persistentTree[newRoot].sumA += deltaA;
    persistentTree[newRoot].sumB += deltaB;
    if (l == r) return newRoot;
    
    int mid = (l + r) / 2;
    if (pos <= mid) {
        persistentTree[newRoot].left = updateVersion(persistentTree[prevRoot].left, l, mid, pos, deltaA, deltaB);
    } else {
        persistentTree[newRoot].right = updateVersion(persistentTree[prevRoot].right, mid+1, r, pos, deltaA, deltaB);
    }
    return newRoot;
}

pair<long long, long long> queryVersion(int root, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
        return {persistentTree[root].sumA, persistentTree[root].sumB};
    }
    int mid = (l + r) / 2;
    pair<long long, long long> res = {0, 0};
    if (ql <= mid) {
        auto leftRes = queryVersion(persistentTree[root].left, l, mid, ql, qr);
        res.first += leftRes.first;
        res.second += leftRes.second;
    }
    if (qr > mid) {
        auto rightRes = queryVersion(persistentTree[root].right, mid+1, r, ql, qr);
        res.first += rightRes.first;
        res.second += rightRes.second;
    }
    return res;
}

Problem 10: Dynamic Segment Tree with Range Operations

A segment tree supporting range addition and range minimum queries on a large coordinate range requires dynamic node creation to manage memory efficiently.

struct DynamicSegNode {
    int leftChild, rightChild;
    int minimum, lazy;
};

vector<DynamicSegNode> segNodes;
int treeRoot = 1;

void applyLazy(int node, int value) {
    segNodes[node].lazy += value;
    segNodes[node].minimum += value;
}

void push(int node) {
    if (!segNodes[node].lazy) return;
    if (!segNodes[node].leftChild) {
        segNodes[node].leftChild = segNodes.size();
        segNodes.push_back({0, 0, 0, 0});
    }
    if (!segNodes[node].rightChild) {
        segNodes[node].rightChild = segNodes.size();
        segNodes.push_back({0, 0, 0, 0});
    }
    applyLazy(segNodes[node].leftChild, segNodes[node].lazy);
    applyLazy(segNodes[node].rightChild, segNodes[node].lazy);
    segNodes[node].lazy = 0;
}

void rangeAdd(int& node, int l, int r, int ql, int qr, int val) {
    if (!node) {
        node = segNodes.size();
        segNodes.push_back({0, 0, 0, 0});
    }
    if (ql <= l && r <= qr) {
        applyLazy(node, val);
        return;
    }
    push(node);
    int mid = (l + r) / 2;
    if (ql <= mid) rangeAdd(segNodes[node].leftChild, l, mid, ql, qr, val);
    if (qr > mid) rangeAdd(segNodes[node].rightChild, mid+1, r, ql, qr, val);
    segNodes[node].minimum = min(segNodes[segNodes[node].leftChild].minimum, 
                                  segNodes[segNodes[node].rightChild].minimum);
}

int rangeMin(int node, int l, int r, int ql, int qr) {
    if (!node) return 0;
    if (ql <= l && r <= qr) return segNodes[node].minimum;
    push(node);
    int mid = (l + r) / 2;
    int res = INT_MAX;
    if (ql <= mid) res = min(res, rangeMin(segNodes[node].leftChild, l, mid, ql, qr));
    if (qr > mid) res = min(res, rangeMin(segNodes[node].rightChild, mid+1, r, ql, qr));
    return res;
}