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