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;
}