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

Question

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;

    }


}

Answer 1

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.

To fix it you'll have to redo the whole algo if I am not mistaken.

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.