Editorial- Segment Tree || ECPC10F

PROBLEM LINK:

Contest
Practice

Author and Editorialist: Pankaj Sharma

DIFFICULTY:

MEDIUM - HARD .

PREREQUISITES:

Persistent segment tree

PROBLEM:

Find xor of largest k elements in given subarray of array A

QUICK EXPLANATION:

Check

Use persistent segment tree to answer queries.

EXPLANATION:

Idea of persistence

Create new nodes instead of changing them.

Resources to Learn Persistent Segment Tree

https://www.youtube.com/watch?v=TH9n_HVkjQM
Persistence Made Simple - Tutorial
https://blog.anudeep2011.com/persistent-segment-trees-explained-with-spoj-problems/

Approach

Please go through above resources if you don’t know persistent segment tree.
We will build a persistent segment tree and additionally we will store xor_value in our node as well.
Suppose we have segment tree for all the ranges 1 <= i <= j <= N then we can answer each query in O(logN) easily but we this approach will take O(N^3) Time.

How to improve

We can use below fact .
node for (i, j) = node for (1, j) – node for (1, i-1).

How to improve further

We can use below fact .
Segment tree for prefix i is almost same as segment tree for prefix i-1, except some O( log N ) nodes that will change.
So we can vertex for these log(N) nodes.
Time complexity will be O( N * log N ) and you will be having a O(Q+N) * log N ) solution.
Thus we can query for K^{th} largest element using our segment tree.
Then we can calculate our answer for (l,r,k) can be calculated using root[r] , root[l-1] and above query in O(logN) time. See solution for details.

Time Complexity:

The time complexity is O((N+Q)*log(N)) per test case.
where N=total number of elements in array .
Q = total No of Queries.

SOLUTIONS:

Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;

struct node {
    int freq;
    int xor_value;
    int l;
    int r;
};
const int N = 2e5 + 5;
int last, root[N];
node segt[10*N];

int new_vertex(int i) {
    segt[++last].freq = segt[i].freq;
    segt[last].l = segt[i].l;
    segt[last].r = segt[i].r;
    segt[last].xor_value = segt[i].xor_value;
    return last;
}

int initialize(int l, int r, int i) {
    i = new_vertex(i);
    if (l == r) {
        segt[i].l = segt[i].r = -1;
        return i;
    }
    int mid = (l + r) /2;
    segt[i].l = initialize(l, mid, segt[i].l);
    segt[i].r = initialize(mid + 1, r, segt[i].r);
    return i;
}

int Insert(int l, int r, int x, int v, int i) {
    if (l > x || r < x) return i;
    i = new_vertex(i);
    if (l == r) {
        segt[i].freq++;
        segt[i].xor_value = v;
        return i;
    }
    int mid = (l + r) /2;
    segt[i].l = Insert(l, mid, x, v, segt[i].l);
    segt[i].r = Insert(mid + 1, r, x, v, segt[i].r);
    segt[i].freq = segt[segt[i].l].freq + segt[segt[i].r].freq;
    segt[i].xor_value = (segt[segt[i].l].xor_value ^ segt[segt[i].r].xor_value);
    return i;
}

int query(int id_l, int id_r, int l, int r, int k) {
    if (l == r) return l;
    int freq_left = segt[segt[id_r].l].freq - segt[segt[id_l].l].freq;
    int mid = (l + r) /2;
    if (freq_left >= k)
        return query(segt[id_l].l, segt[id_r].l, l, mid, k);
    else
        return query(segt[id_l].r, segt[id_r].r, mid + 1, r, k - freq_left);
}

int query_xor(int ids, int l, int r, int a, int b) {
    if (l > b || r < a) return 0;
    if (l >= a && r <= b) return segt[ids].xor_value;
    int mid = (l + r) /2;
    return (query_xor(segt[ids].l, l, mid, a, b) ^ query_xor(segt[ids].r, mid + 1, r, a, b)) ;
}
int actual[N], mapped[N];

vector <pair<int, int> > A, Temp;

int main() {
    int n, q , l, r, k;
    cin >> n;
    A = vector<pair<int, int>>(n);
    for (int i = 0; i < n; i++) {
        cin >> A[i].first;
        A[i].second = i;
    }

    Temp = A;
    sort(A.rbegin(), A.rend());
    for (int i = 0; i < n; i++) {
        mapped[A[i].second] = i, actual[i] = A[i].second;
    }
    last = -1;
    root[0] = initialize(0, n - 1, 0);
    A = Temp;
    for (int i = 1; i <= n; i++) {
        //// Build a tree for each prefix using segment tree of previous prefix
        root[i] = Insert(0, n - 1, mapped[A[i - 1].second], A[i - 1].first, root[i - 1]);
    }
    cin >> q;
    while (q--) {
        cin >> l >> r >> k;
        int kth = query(root[l - 1], root[r], 0, n - 1, k);
        int l_part = query_xor(root[l - 1], 0, n - 1, 0, kth);
        int r_part = query_xor(root[r], 0, n - 1, 0, kth);
        int ans = l_part ^ r_part;
        cout << ans << "\n";
    }
    return 0;
}



Similar Problems:

Codechef
Codechef
More Problems

Bonus:

  1. Solve this problem using Mo Algorithm.
  2. Solve this problem using segment tree + Binary Search.

Please give me suggestions if anything is unclear so that I can improve. Thanks :slight_smile:

5 Likes

By segment tree + Binary search do you mean merge sort tree ? If not, you can also use merge sort tree + prefix sum and then binary search on the prefix sum on corresponding node to answer in log2(n) per query.

1 Like

Yes I was talking about this (logN)*(logN) solution using merge sort tree which involves binary search but in sometimes time limit is too tight and you need to answer queries in O(logN) using persistent segment tree.