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

Persistent Segment Trees - SPOJ - MKTHNUM - YouTube
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.

ur editorial is very nice. Thanks for the resources :smiley:

1 Like