5084. Interval less query

 

An array of n integers is given. You need to answer  queries. For each query, determine how many numbers in the segment [l, r] have values less than x.

 

Input. The first line contains one integer n (1 ≤ n ≤ 105) – the length of the array.

The second line contains n integers – the elements of the array.

The third line contains one integer q (1 ≤ q ≤ 105) – the number of queries.

Each of the following q lines describes a query and contains three integers l, r and x (l ≤ r, 1 ≤ x ≤ 109).

 

Output. For each query, print in a separate line the number of elements in the segment [l, r] that are less than x.

 

Sample input

Sample output

8

1 3 2 4 3 10 5 5

4

1 8 5

1 4 3

5 8 9

2 6 4

5

2

3

3

 

 

SOLUTION

segment tree

 

Algorithm analysis

Merge Tree algorithm. In each vertex of the segment tree store an additional array. The vertex corresponding to the fundamental segment [i; j] contains in its array the sorted sequence of numbers ai, …, aj.

The construction of such a tree takes O(nlog2n) time, since when combining two child vertices their sorted arrays are merged in the same way as in the merge step of the merge sort algorithm.

To find the number of elements in the segment [l, r] that are less than x, the segment is decomposed into a set of fundamental segments of the segment tree. For each of these segments, a binary search is performed in the corresponding sorted array to determine how many elements are less than x.

Since the segment [l, r] can be decomposed into at most O(log2n) fundamental segments, and a binary search in each of them takes O(log2n) time, the processing time for a single query is .

 

Example

 

Algorithm implementation

Let’s declare a segment tree. In each of its nodes, we’ll store an array of numbers.

 

vector<vector<int> > SegTree;

 

The input numbers are stored in the array à.

 

vector<int> a;

 

The function BuildTree constructs the segment tree based on the array à. The sorted array in each node is formed by merging the arrays of its child nodes in O(n) time using the merge function.

 

void BuildTree(int v, int lpos, int rpos)

{

  if (lpos == rpos)

    SegTree[v].push_back(a[lpos]);

  else

  {

    int mid = (lpos + rpos) / 2;

    BuildTree(2*v, lpos, mid);

    BuildTree(2*v+1, mid+1, rpos);

 

    SegTree[v].resize(rpos - lpos + 1);

    merge(SegTree[2*v].begin(), SegTree[2*v].end(),

          SegTree[2*v+1].begin(), SegTree[2*v+1].end(),

          SegTree[v].begin());

  }

}

 

The function Query counts the number of elements in the segment [l, r] that are less than x. For each fundamental segment [left; right], the number of elements less than x is determined using the lower_bound function.

 

int Query(int v, int lpos, int rpos, int left, int right, int x)

{

  if (left > right) return 0;

  if ((lpos == left) && (rpos == right))

    return lower_bound(SegTree[v].begin(), SegTree[v].end(), x) –

           SegTree[v].begin();

 

  int mid = (lpos + rpos) / 2;

  return Query(2*v, lpos, mid, left, min(mid, right), x) +

         Query(2*v+1, mid+1, rpos, max(left, mid+1), right, x);

}

 

The main part of the program. Read the input array of integers.

 

scanf("%d",&n);

a.resize(n + 1);

for(i = 1; i <= n; i++)

  scanf("%d",&a[i]);

 

Build the segment tree based on the array à.

 

SegTree.resize(4*n);

build(1,1,n);

 

Process the q queries sequentially.

 

scanf("%d",&q);

for(i = 0; i < q; i++)

{

  scanf("%d %d %d",&l,&r,&x);

  printf("%d\n",Query(1,1,n,l,r,x));

}

 

Algorithm implementation – SQRT decomposition

 

#include <cstdio>

#include <vector>

#include <set>

#include <algorithm>

#include <cmath>

using namespace std;

 

vector<int> a;

vector<vector<int> > b;

int i, n, q, len, blocks, l, r, x;

 

int main()

{

  scanf("%d", &n);

  a.resize(n);

  len = sqrt(n) + 1;

  blocks = ceil((double)n / len);

  b.resize(len);

 

  for (i = 0;i < n; i++)

  {

    scanf("%d", &a[i]);

    b[i / len].push_back(a[i]);

  }

 

  scanf("%d", &q);

  for (i = 0;i < blocks; i++)

    sort(b[i].begin(), b[i].end());

 

  while (q--)

  {

    scanf("%d %d %d", &l, &r, &x);

    l--; r--;

    int res = 0;

    int c_l = l / len, c_r = r / len;

    if (c_l == c_r)

    {

      for (i = l; i <= r; i++)

        if (a[i] < x) res++;

    }

    else

    {

      for (i = l; i <= (c_l + 1)*len - 1; i++)

        if (a[i] < x) res++;

 

      for (i = c_l + 1; i <= c_r - 1; i++)

        res += lower_bound(b[i].begin(), b[i].end(), x) - b[i].begin();

 

      for (i = c_r * len; i <= r; i++)

        if (a[i] < x) res++;

    }

    printf("%d\n", res);

  }

  return 0;

}