Subtree Interval Operations and Linear Transformations

Problem Analysis

In scenarios where operations target entire subtrees, a common technique is to linearize the tree into a DFS order sequence. This transformation maps a subtree rooted at node $v$ to a contiguous range $[dfn[v], dfn[v] + sz[v] - 1]$. Once linearized, range udpate and point query problems can be efficiently managed using a Segment Tree.

Consider the transformation formula: $(x + k \cdot (depth_u - depth_v)) \times (-1)^{depth_u + depth_v}$. This can be expanded and rearranged as follows:

$$(-1)^{depth_u} \times {(-1)^{depth_v} \times [x - k \cdot depth_v + k \cdot depth_u]}$$

To manage this in a Segment Tree, we maintain two coefficients for a range:

1. $A = (-1)^{depth_v} \times (x - k \cdot depth_v)$
2. $B = (-1)^{depth_v} \times k$

When querying a node $u$, the value is calculated as $(-1)^{depth_u} \times (A + B \cdot depth_u)$. For operation 3, which effectively undoes operation 1, we can iterate through the modified nodes within the DFS range. By maintaining a list of active operations, we ensure that the complexity remains bounded by $O(m \log n)$ since each operation is added and potentially removed only once.

Implementation

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long long const MOD = 1e9 + 7;
int const MAXN = 200005;

struct Node {
    long long val_a, val_b;
} tree[MAXN << 2];

vector<int> adj[MAXN];
int dfn[MAXN], sz[MAXN], depth[MAXN], node_at_dfn[MAXN], timer;
long long op_a[MAXN], op_b[MAXN];

void run_dfs(int u, int d) {
    depth[u] = d;
    dfn[u] = ++timer;
    node_at_dfn[timer] = u;
    sz[u] = 1;
    for (int v : adj[u]) {
        run_dfs(v, d + 1);
        sz[u] += sz[v];
    }
}

void update_range(int i, int l, int r, int ql, int qr, long long a, long long b) {
    if (l > qr || r < ql) return;
    if (l >= ql && r <= qr) {
        tree[i].val_a = (tree[i].val_a + a) % MOD;
        tree[i].val_b = (tree[i].val_b + b) % MOD;
        return;
    }
    int mid = (l + r) >> 1;
    update_range(i << 1, l, mid, ql, qr, a, b);
    update_range(i << 1 | 1, mid + 1, r, ql, qr, a, b);
}

pair<long long, long long> query_point(int i, int l, int r, int pos) {
    if (l == r) return {tree[i].val_a, tree[i].val_b};
    int mid = (l + r) >> 1;
    pair<long long, long long> res = (pos <= mid) ? query_point(i << 1, l, mid, pos) : query_point(i << 1 | 1, mid + 1, r, pos);
    res.first = (res.first + tree[i].val_a) % MOD;
    res.second = (res.second + tree[i].val_b) % MOD;
    return res;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 2; i <= n; ++i) {
        int p; scanf("%d", &p);
        adj[p].push_back(i);
    }
    run_dfs(1, 1);

    while (m--) {
        int type, v; scanf("%d %d", &type, &v);
        if (type == 1) {
            long long x, k;
            scanf("%lld %lld", &x, &k);
            long long parity = (depth[v] % 2 == 1) ? -1 : 1;
            long long base_a = (x - k * depth[v] % MOD + MOD) % MOD * parity % MOD;
            long long base_b = k * parity % MOD;
            update_range(1, 1, n, dfn[v], dfn[v] + sz[v] - 1, base_a, base_b);
            op_a[v] = (op_a[v] + base_a) % MOD;
            op_b[v] = (op_b[v] + base_b) % MOD;
        } else if (type == 2) {
            pair<long long, long long> res = query_point(1, 1, n, dfn[v]);
            long long parity = (depth[v] % 2 == 1) ? -1 : 1;
            long long ans = (res.first + res.second * depth[v]) % MOD * parity % MOD;
            printf("%lld\n", (ans + MOD) % MOD);
        } else {
            for (int i = dfn[v]; i < dfn[v] + sz[v]; ++i) {
                int curr = node_at_dfn[i];
                if (op_a[curr] || op_b[curr]) {
                    update_range(1, 1, n, dfn[curr], dfn[curr] + sz[curr] - 1, (MOD - op_a[curr]) % MOD, (MOD - op_b[curr]) % MOD);
                    op_a[curr] = op_b[curr] = 0;
                }
            }
        }
    }
    return 0;
}

Validating Ordered Points on a Convex Hull

Algorithm Strategy

A sequence of points forms a valid polygon equivalent to its convex hull if two conditions are met:

1. All provided points must lie on the boundary of the convex hull.
2. The input order of the points must match a monotonic traversal (either clockwise or counter-clockwise) of the hull's boundary.

We utilize Andrew's monotone chain algorithm to construct the convex hull. First, we sort points by their coordinates to build the upper and lower chains. During construction, if any input point is not included in the hull, the shape is not strictly convex or contains internal points. Furthermore, we check for duplicate points and collinearity that might violate the simplicity of the polygon.

Implementation

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

struct Vector2D {
    long long x, y;
    bool operator<(const Vector2D& other) const {
        return x < other.x || (x == other.x && y < other.y);
    }
};

long long cross_product(Vector2D a, Vector2D b, Vector2D c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

int main() {
    int n; scanf("%d", &n);
    vector<Vector2D> pts(n), original(n);
    map<pair<long long, long long>, bool> exists;
    
    for (int i = 0; i < n; ++i) {
        scanf("%lld %lld", &pts[i].x, &pts[i].y);
        if (exists[{pts[i].x, pts[i].y}]) {
            printf("No"); return 0;
        }
        exists[{pts[i].x, pts[i].y}] = true;
        original[i] = pts[i];
    }

    sort(pts.begin(), pts.end());
    vector<int> hull_indices;
    vector<bool> on_hull(n, false);

    for (int i = 0; i < n; ++i) {
        while (hull_indices.size() >= 2) {
            int last = hull_indices.back();
            int prev = hull_indices[hull_indices.size() - 2];
            if (cross_product(pts[prev], pts[last], pts[i]) < 0) hull_indices.pop_back();
            else break;
        }
        hull_indices.push_back(i);
    }

    int lower_size = hull_indices.size();
    for (int i = n - 2; i >= 0; --i) {
        while (hull_indices.size() > lower_size) {
            int last = hull_indices.back();
            int prev = hull_indices[hull_indices.size() - 2];
            if (cross_product(pts[prev], pts[last], pts[i]) < 0) hull_indices.pop_back();
            else break;
        }
        hull_indices.push_back(i);
    }

    if (hull_indices.size() <= n) {
        printf("No"); return 0;
    }

    // Check if the order matches original sequence
    bool clockwise = true, counter = true;
    for (int i = 0; i < n; ++i) {
        int next = (i + 1) % n;
        int prev = (i - 1 + n) % n;
        if (cross_product(original[prev], original[i], original[next]) < 0) counter = false;
        if (cross_product(original[prev], original[i], original[next]) > 0) clockwise = false;
    }

    if (clockwise || counter) printf("Yes");
    else printf("No");

    return 0;
}