2
\$\begingroup\$

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;

    }


}



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

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.

\$\endgroup\$
7
  • \$\begingroup\$ Why would I use 2D segment tree for an 1D array? My teacher told me that it could be done with a normal segment tree. \$\endgroup\$ – Simon Jachson Dec 24 '19 at 15:20
  • \$\begingroup\$ @SimonJachson because graph of the 1-dimensional array is 2 dimensional and you basically want to know how many points are in one of the rectangles. Or did I misunderstand something? 1 dimensional sieve would be good if you wanted to know what is within a segment. \$\endgroup\$ – ALX23z Dec 24 '19 at 17:16
  • \$\begingroup\$ You cannot say O(something) on average and O(other) in worst case. O(some) is the asymptotic upper limit and thus the worst case. \$\endgroup\$ – slepic Dec 25 '19 at 9:29
  • \$\begingroup\$ @slepic ...you are simply wrong. \$\endgroup\$ – ALX23z Dec 25 '19 at 12:42
  • \$\begingroup\$ Yeah yeah Im kinda sick of Ppl like you WHO keep telling me I am wrong without any reasoning why would that be. I am Always ready to admit i was wrong but if you dont have any arguments you wont convince me. There Is no value to your comment. \$\endgroup\$ – slepic Dec 26 '19 at 7:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.