I am trying to do this problem using Persistent Segment Tree.
Please help me figure out why does my code give a Runtime error, and how to rectify it.
cur->right = prev->right; //code gives RE on this statement
My Solution
//https://www.spoj.com/problems/MKTHNUM/
#include <bits/stdc++.h>
using namespace std;
const long long N = 1e5 + 10;
long long a[N];
map<long long, long long> Sorted;
struct Node {
Node *left, *right;
long long val;
Node(Node* l, Node* r, int v) {
left = l;
right = r;
val = v;
}
};
Node *Versions[N];
void Build(Node *cur, long long l, long long r) {
cur->val = 0;
if(l == r)
return;
cur->left = new Node(NULL, NULL, 0);
cur->right = new Node(NULL, NULL, 0);
long long mid = (l + r) / 2;
Build(cur->left, l, mid);
Build(cur->right, mid + 1, r);
}
void Insert(Node *prev, Node *cur, long long l, long long r, long long pos) {
if(l == r) {
cur->val = 1;
return;
}
long long mid = (l + r) / 2;
if(pos <= mid) {
cur->right = prev->right;
cur->left = new Node(NULL, NULL, 0);
Insert(prev->left, cur->left, l, mid, pos);
}
else {
cur->left = prev->left;
cur->right = new Node(NULL, NULL, 0);
Insert(prev->right, cur->right, mid + 1, r, pos);
}
cur->val = cur->right->val + cur->left->val;
}
long long Query(Node *Left, Node *Right, long long k, long long l, long long r) {
if(l == r)
return Sorted[l];
long long mid = (l + r) / 2;
if(Right->left->val - Left->left->val < k) {
return Query(Left->right, Right->right, k - (Right->left->val - Left->left->val), mid + 1, r);
}
else {
return Query(Left->left, Right->left, k, l, mid);
}
}
void Solve() {
long long n, q;
cin >> n >> q;
for(long long i = 1; i <= n; i++) {
cin >> a[i];
Sorted[a[i]] = i;
}
Node *root = new Node(NULL, NULL, 0);
Versions[0] = root;
Build(Versions[0], 1, n);
for(long long i = 1; i <= n; i++) {
Insert(Versions[i - 1], Versions[i], 1, n, Sorted[a[i]]);
}
for(long long i = 1; i <= q; i++) {
long long ql, qr, k;
cin >> ql >> qr >> k;
cout << Query(Versions[ql - 1], Versions[qr], k, 1, n) << endl;
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
Solve();
return 0;
}
What does my code do before the RE:
- Takes a as the input array, and the map Sorted sorts it and stores it in the pair [a[i], i] (value, index)
- The value of a position x in the ith version of the Segment tree is the count of the number of elements encountered in the range of position x (i.e [l, r] or the bounds of position x)
