KQuery - Stuck on this problem for ages! Can you help me?

[tmsm1999]

Hello everybody,

I have been trying to solve the KQuery problem for three days and I can’t get it right. I am using segment trees and offline queries. I know I could find something online but I don’t like to look at the solution. I want to understand what I am doing wrong so I can fix it and hopefully get accepted.

Could you take a look at my could and try to point out what I may possibly be doing wrong?

Thank you for you help.

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <math.h>
using namespace std;

class Node {

public:
	char type;
	int k;
	int i;
	int j;
	int order;
	int ans;
	int posOrg;

	Node(int _k, int p) {
		type = 'E';
		k = _k;
		posOrg = p;
	}

	Node(int _i, int _j, int _k, int _o) {
		type = 'Q';
		i = _i;
		j = _j;
		k = _k;
		order = _o;
		ans = 0;
	}
};

class SegmentTree {
private: 
	vector<pair<int, int> > st;
	int n;

	int left(int p) {
		return p*2;
	}
	int right(int p) {  
		return p*2 + 1;
	}

	int merge(int x, int y) {
		return x + y;
	}

	int query(int p, int l, int r, int i, int j) {
		if(l > j || r < i) {
			return 0; //outside of the query range;
		}
		if(l >= i && r <= j) {
 			if(st[p].second >= i && st[p].second <= j) {
				return st[p].first;
			}
			return 0;
		}
		int m = l + (r-l) / 2;
		int pOne = query(left(p), l, m, i, j);
		int pTwo = query(right(p), m+1, r, i, j);

		return merge(pOne, pTwo);
	}

	void update(int p, int l, int r, int k, int pos) {
		if(l == r && l == k) {
			st[p].first = 1;
			st[p].second = pos;
			return;
		}

		if(l > k || r < k) {
			return;
		}

		int mid = l + (r-l) / 2;
		update(left(p), l, mid, k, pos);
		update(right(p), mid + 1, r, k, pos);
		st[p].first = merge(st[left(p)].first, st[right(p)].first);
	}

	void printSegTree() {
		for(int i = 1; i <= st.size(); i++) {
			cout << "(" << st[i].first << ", " << st[i].second << ") ";
		}
		cout << endl;
	}

public:
	SegmentTree(int _n) {
		//a = seq;
		n = _n;
		st.assign(4*n, make_pair(0, 0));
		//build(1, 1, n);
	}

	int query(int i, int j) {
		return query(1, 1, n, i, j);
	}

	void update(int k, int p) {
		update(1, 1, n, k, p);
	}

	void print() {
		printSegTree();
	}
};

bool compare(Node a, Node b) {
	if(a.k > b.k) {
		return true;
	}
	else if(a.k == b.k) {
		if(a.type == 'Q' && b.type == 'E') {
			return true;
		}
	}
	return false;
}

bool compareAns(pair<int, int> a, pair<int, int> b) {
	if(a.first < b.first) {
		return true;
	}
	return false;
}

int main() {
	vector<Node> v;

	int n;
	int q;
	scanf("%d", &n);

	int elem;
	v.push_back(Node(0, 0));
	for(int i = 1; i <= n; i++) {
		scanf("%d", &elem);
		v.push_back(Node(elem, i));
	}

	sort(v.begin(), v.end(), compare);
	scanf("%d", &q);

	int a, b, k;
	for(int i = 0; i < q; i++) {
		scanf("%d %d %d", &a, &b, &k);
		v.push_back(Node(a, b, k, i));
	}

	sort(v.begin(), v.end(), compare);

	SegmentTree st(n);
	vector<pair<int, int> > queryAns;
	for(int i = 0; i < v.size() - 1; i++) {
		if(v[i].type == 'E') {
			st.update(v[i].k, v[i].posOrg);
			//st.print();
		}
		else {
			v[i].ans = st.query(v[i].i, v[i].j);
			queryAns.push_back(make_pair(v[i].order, v[i].ans));
		}
	}
	sort(queryAns.begin(), queryAns.end(), compareAns);
	for(int i = 0; i < queryAns.size(); i++) {
		cout << queryAns[i].second << endl;
	}
	return 0;
}