# Permutation 1...N. Answer queries "How many numbers between [X,Y] position are in the interval [L,K]"?

So I am solving this task: We have an permutation of the numbers 1..n. I need to answer m queries: -How many numbers between X-th and Y-th position are in the interval [L,K] (<=k and >= L)?

So my solution is simple: I create a segment tree and in every node i keep an map -> which numbers are in this interval and the position (when they are sorted).

For example ( 98, 14 , 22, 45, 33) the map for this interval is (14,1)(22,2),(33,3),(45,5).. Then when i recieve a query (X,Y,l,k) I find the interval in the tree,then I use lower bound (to the map in the node (so i get Log(n) time complexity)) to find the closest element to l and the closest element to k and substract their positions. The solution works, but i exceed the time for some test. Any tips how can i make it faster ? Maybe faster way to create the maps in the nodes ? Or faster search in the tree?

#include <iostream>
#include <map>
using namespace std;

#define IntervalsIntersect(left,right,X, Y)  (left <= Y && right >= X)

struct node
{
map<int, int> m;
};

int getNextIndRight(int ind, int n) // By going right how does the interval changes
{
int diff = n - ind;
if (diff % 2 == 0)
return n - diff / 2;
return n - diff / 2 - 1;

}
int getNextIndLeft(int ind, int n)
{
int diff = n - ind;
if (diff % 2 == 0)
return ind + 1 + diff / 2;
return (ind + diff / 2) + 1;
}
void build(int* a, node* t, int v, int tl, int tr, int left, int right)
{
if (tl == tr)
{
t[v].m.insert(pair<int, int>(a[tl], 1));
}
else
{
int tm = (tl + tr) / 2;
build(a, t, v * 2, tl, tm, left, getNextIndRight(left, right));
build(a, t, v * 2 + 1, tm + 1, tr, getNextIndLeft(left, right), right);
t[v].m = t[v * 2].m;
t[v].m.insert(t[v * 2 + 1].m.begin(), t[v * 2 + 1].m.end());
int i = 1;
for (auto &p : t[v].m)
{
p.second = i++;
}

}
}

int countInInterval(map<int, int>& m, int k, int l)
{

//for (auto &p : m)
//    cout<<p.first<<" "<<p.second<<endl;
auto it = m.lower_bound(k);
auto it2 = m.lower_bound(l);

bool firstOK = it != m.end();
bool secondOK = it2 != m.end();
if (!firstOK && !secondOK)
return 0;
else if (firstOK && !secondOK)
return m.size() - it->second + 1;

if (it == it2)
{
if (k <= it->first&&it->first <= l)
return 1;
return 0;
}

int res= (it2->second - it->second);
if (k <= it2->first && it2->first <= l)
res++;
return res;

}
bool hasIntersection(int left, int right, int X, int Y)
{
return left <= Y && right >= X;
}
int f(node* t, int* a, int left, int right, int n, int v, int X, int Y, int k, int l)
{
if (left >= X && right <= Y)
return countInInterval(t[v].m, k, l);
int leftFirst = left;
int rightFirst = getNextIndRight(left, right);
int res = 0;
if (IntervalsIntersect(leftFirst, rightFirst, X, Y))
res += f(t, a, left, getNextIndRight(left, right), n, v * 2, X, Y, k, l);

int leftsecond = getNextIndLeft(left, right);
int rightsecond = right;
if (IntervalsIntersect(leftsecond, rightsecond, X, Y))
res += f(t, a, getNextIndLeft(left, right), right, n, v * 2 + 1, X, Y, k, l);;
return res;
}

int main()
{

int n, m;
cin >> n >> m;
int* a = new int[n];
for (int i = 0; i < n; i++)
cin >> a[i];

node* t = new node[4 * n + 1];

build(a, t, 1, 0, n - 1, 1, n);

for (int i = 0; i < m; i++)
{
int x, y, k, l;
cin >> x >> y >> k >> l;
cout << f(t, a, 1, n, n, 1, x, y, k, l) << endl;

}

}


• Do you have some test cases? I don't understand why you can't use binary search here. Dec 24, 2019 at 14:07
• map is implemented like a BST. I use segment tree, because i need an interval of the permutation, not the whole permutation. Dec 24, 2019 at 14:11
• I would suggest expanding all the variables with single letters to meaningful names. This is a total mess trying examine your code.
– user33306
Dec 24, 2019 at 14:12
• Welcome to code review, if this is a programming challenge, can you please add a linke to the website. Dec 24, 2019 at 14:58

I believe the problem lies in the initialization time. If I am not wrong it is like O(n^2 log n) which might be a problem for tests with large n and small sample size.
There is a method that doesn't have the same long initialization problem while retaining the same O(log n) (at least on average, O(log^2 n) at worst) time per iteration - simply build a two dimensional segment tree. Since we work with a permutation it will be rather sparse.