AIOJ

Building a block array

A block array divides an array into several blocks and stores information for each block as a whole. When a query reaches an incomplete block at either end, it is handled by brute force. In general, the block length is $O(\sqrt{n})$ . For a detailed analysis, see Xu Mingkuan's paper “A Preliminary Study of Unconventional Block Decomposition Algorithms” from the 2017 National Training Team.

The following code directly builds a block array.

Implementation

num = sqrt(n);
for (int i = 1; i <= num; i++)
  st[i] = n / num * (i - 1) + 1, ed[i] = n / num * i;
ed[num] = n;
for (int i = 1; i <= num; i++) {
  for (int j = st[i]; j <= ed[i]; j++) {
    belong[j] = i;
  }
  size[i] = ed[i] - st[i] + 1;
}

Here, st[i] and ed[i] are the start and end of a block, and size[i] is its size.

Storing and modifying block information

Example 1: The Magic of the Cult Master

There are two operations:

Add $z$ to every number in the interval $[x,y]$ .
Query the number of values greater than or equal to $z$ in $[x,y]$ .

We need to count the values in a block that are at least a given number, so we use a t array containing the sorted block values; a is the original unsorted array. For a full-block modification, use a method similar to lazy-tag persistence and record the value added to the entire block in delta. If $q$ is the total number of queries and modifications, the time complexity is $O(q\sqrt{n}\log n)$ .

The delta array records the value added to every block as a whole.

Implementation

void Sort(int k) {
  for (int i = st[k]; i <= ed[k]; i++) t[i] = a[i];
  sort(t + st[k], t + ed[k] + 1);
}

void Modify(int l, int r, int c) {
  int x = belong[l], y = belong[r];
  if (x == y)  // Modify directly when the interval lies within one block
  {
    for (int i = l; i <= r; i++) a[i] += c;
    Sort(x);
    return;
  }
  for (int i = l; i <= ed[x]; i++) a[i] += c;     // Modify the starting segment directly
  for (int i = st[y]; i <= r; i++) a[i] += c;     // Modify the ending segment directly
  for (int i = x + 1; i < y; i++) delta[i] += c;  // Mark the intermediate blocks as a whole
  Sort(x);
  Sort(y);
}

int Answer(int l, int r, int c) {
  int ans = 0, x = belong[l], y = belong[r];
  if (x == y) {
    for (int i = l; i <= r; i++)
      if (a[i] + delta[x] >= c) ans++;
    return ans;
  }
  for (int i = l; i <= ed[x]; i++)
    if (a[i] + delta[x] >= c) ans++;
  for (int i = st[y]; i <= r; i++)
    if (a[i] + delta[y] >= c) ans++;
  for (int i = x + 1; i <= y - 1; i++)
    ans +=
        ed[i] - (lower_bound(t + st[i], t + ed[i] + 1, c - delta[i]) - t) + 1;
  // Use lower_bound to find the first value at least c in each intermediate full block
  return ans;
}

Example 2: Ark in the Cold Night

There are two operations:

Set every number in the interval $[x,y]$ to $z$ .
Query the number of values less than or equal to $z$ in $[x,y]$ .

The delta array records the value assigned to an entire block. When a block has not been assigned as a whole, represent this with a special value such as 0x3f3f3f3f3f3f3f3fll. Before querying a boundary block, call pushdown to propagate the block information to each element. Remember to sort again after an assignment. The other details are the same as in the previous example.

Implementation

void Sort(int k) {
  for (int i = st[k]; i <= ed[k]; i++) t[i] = a[i];
  sort(t + st[k], t + ed[k] + 1);
}

void PushDown(int x) {
  if (delta[x] != 0x3f3f3f3f3f3f3f3fll)  // This value marks that the block has not been assigned as a whole
    for (int i = st[x]; i <= ed[x]; i++) a[i] = t[i] = delta[x];
  delta[x] = 0x3f3f3f3f3f3f3f3fll;
}

void Modify(int l, int r, int c) {
  int x = belong[l], y = belong[r];
  PushDown(x);
  if (x == y) {
    for (int i = l; i <= r; i++) a[i] = c;
    Sort(x);
    return;
  }
  PushDown(y);
  for (int i = l; i <= ed[x]; i++) a[i] = c;
  for (int i = st[y]; i <= r; i++) a[i] = c;
  Sort(x);
  Sort(y);
  for (int i = x + 1; i < y; i++) delta[i] = c;
}

int Binary_Search(int l, int r, int c) {
  int ans = l - 1, mid;
  while (l <= r) {
    mid = (l + r) / 2;
    if (t[mid] <= c)
      ans = mid, l = mid + 1;
    else
      r = mid - 1;
  }
  return ans;
}

int Answer(int l, int r, int c) {
  int ans = 0, x = belong[l], y = belong[r];
  PushDown(x);
  if (x == y) {
    for (int i = l; i <= r; i++)
      if (a[i] <= c) ans++;
    return ans;
  }
  PushDown(y);
  for (int i = l; i <= ed[x]; i++)
    if (a[i] <= c) ans++;
  for (int i = st[y]; i <= r; i++)
    if (a[i] <= c) ans++;
  for (int i = x + 1; i <= y - 1; i++) {
    if (0x3f3f3f3f3f3f3f3fll == delta[i])
      ans += Binary_Search(st[i], ed[i], c) - st[i] + 1;
    else if (delta[i] <= c)
      ans += size[i];
  }
  return ans;
}

Block Array

Building a block array

Storing and modifying block information

Example 1: The Magic of the Cult Master

Example 2: Ark in the Cold Night

Exercises