Solution

Method 1 – Segment Tree with Lazy Propagation

Intuition

The problem requires efficiently handling range XOR queries and subarray reversals. A segment tree with lazy propagation can efficiently support both range XOR and range reverse operations by maintaining additional information for each segment.

Approach

Build a segment tree where each node stores the XOR of its segment and a flag for pending reversals.
For a range reversal, propagate the reversal flag down the tree and swap children as needed.
For a range XOR query, use the segment tree to get the XOR in O(log n) time, considering any pending reversals.
Use lazy propagation to ensure all operations are efficient.

Code

[{"language":"C++","code":"// This is a template for the solution. Actual implementation may vary based on the problem's API.\nclass Solution {\npublic:\n    // Assume arr is the array, queries is a list of queries\n    // Each query: [type, l, r] where type=1 for reverse, type=2 for xor query\n    // Returns vector<int> for xor queries\n    struct Node {\n        int l, r, x;\n        bool rev;\n        Node *left, *right;\n        Node(int l, int r): l(l), r(r), x(0), rev(false), left(nullptr), right(nullptr) {}\n    };\n    Node* build(vector<int>& arr, int l, int r) {\n        Node* node = new Node(l, r);\n        if (l == r) { node->x = arr[l]; return node; }\n        int m = (l + r) / 2;\n        node->left = build(arr, l, m);\n        node->right = build(arr, m+1, r);\n        node->x = node->left->x ^ node->right->x;\n        return node;\n    }\n    void push(Node* node) {\n        if (node->rev) {\n            swap(node->left, node->right);\n            if (node->left) node->left->rev ^= 1;\n            if (node->right) node->right->rev ^= 1;\n            node->rev = false;\n        }\n    }\n    void reverse(Node* node, int l, int r) {\n        if (node->r < l || node->l > r) return;\n        if (l <= node->l && node->r <= r) { node->rev ^= 1; return; }\n        push(node);\n        reverse(node->left, l, r);\n        reverse(node->right, l, r);\n        node->x = node->left->x ^ node->right->x;\n    }\n    int query(Node* node, int l, int r) {\n        if (node->r < l || node->l > r) return 0;\n        if (l <= node->l && node->r <= r) return node->x;\n        push(node);\n        return query(node->left, l, r) ^ query(node->right, l, r);\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#6A737D;--shiki-dark:#6A737D\">// This is a template for the solution. Actual implementation may va

Related Tags