Array

Building block arrays¶

Block array is an array divided into several blocks, and the information within the block is stored as a whole. If you encounter incomplete blocks on both sides while handling queries, you can directly query with brute-force. In general, the length of the block is . For detailed analysis, you can read "A Preliminary Study on Unconventional Size Blocking Algorithms" by Xu Mingkuan in the 2017 National Training Team Papers.

The code for building a block array is directly given below.

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;
}

st[i] here ed[i] are the start and end point of the block, and size[i] is the size of the block.

Save and modify information in the block¶

Sample problem 1： Master's Magic (original link in Chinese)¶

We need to query the number of numbers greater than or equal to a number in a block, so we need a t array to sort the blocks. For the modification of the whole block, it is saved in a way similar to making the mark permanent. Time complexity is

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) {
    for (int i = l; i <= r; i++) a[i] += c;
    Sort(x);
    return;
  }
  for (int i = l; i <= ed[x]; i++) a[i] += c;
  for (int i = st[y]; i <= r; i++) a[i] += c;
  for (int i = x + 1; i < y; i++) dlt[i] += c;
  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] + dlt[x] >= c) ans++;
    return ans;
  }
  for (int i = l; i <= ed[x]; i++)
    if (a[i] + dlt[x] >= c) ans++;
  for (int i = st[y]; i <= r; i++)
    if (a[i] + dlt[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 - dlt[i]) - t) + 1;
  return ans;
}

Sample problem 2: Cold Night Ark¶

Two operations:

Every number in the interval is changed into
Query the number of numbers less than or equal to in the interval

Use dlt to save whether the entire block has been assigned. Use a value to indicate no. For corner blocks, you must pushdown before querying, and put the block information on each number. Remember to sort again after assignment. Other aspects are the same as above.

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 (dlt[x] != 0x3f3f3f3f3f3f3f3fll)
    for (int i = st[x]; i <= ed[x]; i++) a[i] = t[i] = dlt[x];
  dlt[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++) dlt[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 == dlt[i])
      ans += Binary_Search(st[i], ed[i], c) - st[i] + 1;
    else if (dlt[i] <= c)
      ans += size[i];
  }
  return ans;
}

Practices¶

The Following problems are written in Chinese.

Last update and/or translate time of this article，Check the history
Found smelly bugs? Translation outdated? Wanna contribute with us? Edit this Page on Github
Contributor of this article OI-wiki
Translator of this article Visit the original article!
The article is available under CC BY-SA 4.0 & SATA ; additional terms may apply.