The kid who learned to count (Editorial)

The kid can choose two passengers on the segment [l; r] if and only if the sum of the two smallest masses of animals on this segment does not exceed $k$. Indeed, if some pair of animals fits, then the pair of the two lightest animals fits all the more.

Therefore, one could build a segment tree in which each vertex stores the two minimums on its segment. However, we are interested not in the minimums themselves, but only in whether there exist two numbers whose sum does not exceed $k$. This allows us to store just one number in each vertex.

Values in the vertices. The leaves of the segment tree store the masses of the animals. Each internal vertex stores:

• $0$ if its segment contains two animals with a total mass not exceeding $k$;

• the minimum mass of an animal on its segment otherwise.

The masses of the animals are positive, so the value $0$ does not coincide with any mass and unambiguously means that a suitable pair has been found.

Merging the children. The value of a vertex is computed from the values $x$ and $y$ of its children. A suitable pair of animals on the segment of the vertex either lies entirely in one of its halves, or consists of an animal from the left half and an animal from the right half. Therefore:

• if x = 0 or y = 0, a suitable pair lies in one of the halves, and the value of the vertex is $0$;

• otherwise, $x$ and $y$ are the minimum masses in the halves, and the best pair of animals from different halves has a total mass of x + y. If x + y \le k, the value of the vertex is $0$, otherwise it is \min(x, y).

With such a merge function, the problem is solved by a standard segment tree with point updates.

For a query of type $1$, the answer is "Yes" if the value on the segment [l; r] equals $0$, and "No" otherwise.

Example

Let us consider the queries from the example, k = 9. Initially, the masses of the animals are 1, 3, 1, 6, 6, 7:

• $116$: the two lightest animals have masses $1$ and $1$, 1 + 1 = 2 \le 9, the answer is "Yes";

• $112$: 1 + 3 = 4 \le 9, the answer is "Yes";

• $247$: the mass of the fourth animal becomes $7$;

• $145$: 7 + 6 = 13 > 9, the answer is "No";

• $156$: 6 + 7 = 13 > 9, the answer is "No";

• $217$ and $238$: the masses of the first and the third animals become $7$ and $8$.

Before the last query $116$, the masses of the animals are 7, 3, 8, 7, 6, 7. The segment tree for them is shown below. Each vertex shows its segment and the stored value. The leaves are highlighted in yellow, and the vertex with the value $0$ in orange.

Let us compute the values in the internal vertices:

• $[1;2]$: 7 + 3 = 10 > 9, the value is \min(7, 3) = 3;

• $[1;3]$: 3 + 8 = 11 > 9, the value is \min(3, 8) = 3;

• $[4;5]$: 7 + 6 = 13 > 9, the value is \min(7, 6) = 6;

• $[4;6]$: 6 + 7 = 13 > 9, the value is \min(6, 7) = 6;

• $[1;6]$: 3 + 6 = 9 \le 9, the value is $0$.

Only the vertex $[1;6]$ contains $0$: the two lightest animals with masses $3$ and $6$ are in different halves of the segment, and their total mass is $9$. Therefore, the answer to the last query is "Yes".

Algorithm implementation

Declare the constants and the working arrays. The array SegTree stores the segment tree, and the masses of the animals are stored in the array $a$. The constant $INF$ is greater than any mass of an animal and is used as the neutral element for an empty segment. The sum of $INF$ and any mass does not exceed 2 \cdot 10^9 + 10 and fits into the $int$ type.

#define MAX 1000001
#define INF 1000000010
int SegTree[4 * MAX];
int a[MAX];

The function f merges the values $x$ and $y$ of the children. If at least one of the children contains $0$, its segment already contains two suitable passengers. If x + y \le k, the lightest animals of the left and right halves form a suitable pair. In both cases, return $0$; otherwise, return the minimum of $x$ and $y$.

int f(int x, int y)
{
  if (x == 0 || y == 0 || x + y <= k) return 0;
  return min(x, y);
}

The function BuildTree builds the segment tree from the array $a$. Vertex $v$ corresponds to the segment [lpos; rpos]. The leaves store the masses of the animals, and the values in the internal vertices are computed by the function $f$.

void BuildTree(int v, int lpos, int rpos)
{
  if (lpos == rpos)
    SegTree[v] = a[lpos];
  else
  {
    int mid = (lpos + rpos) / 2;
    BuildTree(2 * v, lpos, mid);
    BuildTree(2 * v + 1, mid + 1, rpos);
    SegTree[v] = f(SegTree[2 * v], SegTree[2 * v + 1]);
  }
}

The function Query returns the value on the segment [left; right]: $0$ if it contains two passengers with a total mass of at most $k$, and the minimum mass of an animal otherwise. Vertex $v$ corresponds to the segment [lpos; rpos]. For an empty segment, the neutral value $INF$ is returned.

int Query(int v, int lpos, int rpos, int left, int right)
{
  if (left > right) return INF;
  if ((lpos == left) && (rpos == right)) return SegTree[v];
  int mid = (lpos + rpos) / 2;
  return f(Query(2 * v, lpos, mid, left, min(right, mid)),
           Query(2 * v + 1, mid + 1, rpos, max(left, mid + 1), right));
}

The function Update assigns the value $val$ to the element with index $pos$ and recomputes the values in all vertices on the path from the leaf to the root. Vertex $v$ corresponds to the segment [lpos; rpos].

void Update(int v, int lpos, int rpos, int pos, int val)
{
  if (lpos == rpos)
     SegTree[v] = val;
  else
  {
    int mid = (lpos + rpos) / 2;
    if (pos <= mid) Update(2 * v, lpos, mid, pos, val);
    else Update(2 * v + 1, mid + 1, rpos, pos, val);
    SegTree[v] = f(SegTree[2 * v], SegTree[2 * v + 1]);
  }
}

The main part of the program. Read the number of animals $n$ and the remaining capacity $k$. Read the masses of the animals into the array $a$, starting from index $1$.

scanf("%d %d", &n, &k);
for (i = 1; i <= n; i++)
  scanf("%d", &a[i]);

Build the segment tree from the elements of the array a[1 \ldots n].

BuildTree(1, 1, n);

Process the $q$ queries one by one. The animals are numbered starting from $1$, and the elements of the array $a$ are also stored starting from index $1$, so the indices from the queries are used without changes.

scanf("%d", &q);
for (j = 0; j < q; j++)
{
  scanf("%d %d %d", &t, &l, &r);

Query of type $1$: compute the value on the segment [l; r]. If it equals $0$, two passengers have been found.

  if (t == 1)
  {
    int Res = Query(1, 1, n, l, r);
    if (Res == 0) printf("Yes\n"); else printf("No\n");
  }

Query of type $2$: assign the mass $r$ to the animal with index $l$.

  else
    Update(1, 1, n, l, r);
}