Scanline

Introduction

Scanline is generally applied in graphics. As its name suggests, it involves a line sweeping across the entire graph. It is commonly used to solve problems such as area of shapes, perimeter, and two-dimensional point counting.

2D Rectangle Area Union Problem

In a 2D coordinate system, given the lower-left and upper-right coordinates of multiple rectangles, find the total area formed by all rectangles.

Process

As shown in the image, the total area can be directly calculated by brute force. But what if the data is large? This is where the scanline algorithm comes in.

Now suppose we have a line sweeping from bottom to top:

As shown, the entire rectangle is divided into small rectangles of different colors. The height of each small rectangle is the distance swept, while the horizontal width keeps changing.

Mark each rectangle's top and bottom edges: mark the bottom edge as 1 and the top edge as -1. Whenever a horizontal edge is encountered, add the mark of this edge to the weight of the interval (its projection on the horizontal axis).

Note

This operation is similar to traversing a bracket sequence: an opening bracket adds 1, a closing bracket subtracts 1. The "weight" corresponds to the current depth, and whether the "weight" is greater than 0 corresponds to whether we are currently inside brackets, i.e., whether this interval should be counted in the width of the small rectangle.

The width of the small rectangle(s) (there may be more than one) is the total length of intervals on the number axis where the weight is greater than 0.

Implementation

Use a segment tree to maintain the length of the rectangle, i.e., the points on the entire number axis where the coverage count is greater than 0. The requirements are as follows:

• Add 1 or subtract 1 to the weight of an interval.
• Count the total "interval length sum" on the entire number axis where the interval weight is greater than 0.

If you try to implement this directly using a standard segment tree template, you might encounter some difficulties. Specifically, during interval addition, even if the modification interval overlaps with the node's managed interval, we cannot know in constant time how the coverage count changes. This is because we cannot directly know: within the managed range, how long an interval changes from 1 to 0 (or from 0 to 1).

This problem can be implemented with a simple divide-and-conquer approach: maintain two pieces of information for each node's managed interval: "the number of times the interval is completely covered v[]" (similar to a lazy tag that is not pushed down) and "the covered length w[]".

Discretization is required.

Luogu P5490【Template】Scanline & Rectangle Area Union Reference Code

#include <algorithm>
#include <iostream>

using ll = long long;
constexpr int N = 1e5 + 1;

int n, a[N * 2], tot;   // a[] and tot are used for discretizing x
ll v[N * 8], w[N * 8];  // Count of fully covered intervals, length already covered

struct St {
  ll x1, x2, y, o;
} b[N * 2];  // Upper and lower edges of rectangles

int f(int y) {  // Discretization, map coordinate to index in a
  return std::lower_bound(a, a + tot, y) - a;
}

void up(int u, int ul, int ur) {  // pushup
  if (v[u]) w[u] = a[ur] - a[ul];
  // If calling w[u*2+1] on a leaf node, then the segment tree needs 8 times space
  // Multiplying by the upper and lower edges of rectangles gives 16 times
  else if (ul + 1 == ur)
    w[u] = 0;
  else
    w[u] = w[u * 2 + 1] + w[u * 2 + 2];
}

void add(int lf, int rg, ll o, int u = 0, int ul = 0, int ur = tot - 1) {
  // Interval addition
  if (lf == ul && rg == ur) return v[u] += o, up(u, ul, ur), void();
  int um = (ul + ur) / 2;
  if (lf < um) add(lf, std::min(rg, um), o, u * 2 + 1, ul, um);
  if (um < rg) add(std::max(lf, um), rg, o, u * 2 + 2, um, ur);
  up(u, ul, ur);
}

int main() {
  std::cin >> n;
  for (int i = 0, x1, x2, y1, y2; i < n; i++) {
    // y1 is a local variable, won't cause name conflict
    std::cin >> x1 >> y1 >> x2 >> y2;
    b[i] = {x1, x2, y1, 1};
    b[i + n] = {x1, x2, y2, -1};
    a[i] = x1, a[i + n] = x2;
  }

  std::sort(a, a + n * 2), tot = 1;
  for (int i = 1; i < n * 2; i++)
    if (a[i] != a[tot - 1]) a[tot++] = a[i];  // Discretization

  std::sort(b, b + n * 2,
            [](St &i, St &j) -> bool { return i.y < j.y; });  // Sort operations

  ll sum = 0;
  add(f(b[0].x1), f(b[0].x2), 1);
  for (int i = 1; i < n * 2; i++) {
    int x1 = f(b[i].x1), x2 = f(b[i].x2);
    sum += (b[i].y - b[i - 1].y) * w[0];  // Sum area of each small rectangle
    add(x1, x2, b[i].o);
  }
  std::cout << sum << '\n';
}

「POJ 1151」Atlantis Reference Code

#include <algorithm>
#include <cstdio>
#include <cstring>
constexpr int MAXN = 300;
using namespace std;

int lazy[MAXN << 3];  // Marks the number of times this segment appears
double s[MAXN << 3];

struct node1 {
  double l, r;
  double sum;
} cl[MAXN << 3];  // Segment tree

struct node2 {
  double x, y1, y2;
  int flag;
} p[MAXN << 3];  // Coordinates

// Define sort comparison
bool cmp(node2 a, node2 b) { return a.x < b.x; }

// Push up
void pushup(int rt) {
  if (lazy[rt] > 0)
    cl[rt].sum = cl[rt].r - cl[rt].l;
  else
    cl[rt].sum = cl[rt * 2].sum + cl[rt * 2 + 1].sum;
}

// Build tree
void build(int rt, int l, int r) {
  if (r - l > 1) {
    cl[rt].l = s[l];
    cl[rt].r = s[r];
    build(rt * 2, l, (l + r) / 2);
    build(rt * 2 + 1, (l + r) / 2, r);
    pushup(rt);
  } else {
    cl[rt].l = s[l];
    cl[rt].r = s[r];
    cl[rt].sum = 0;
  }
  return;
}

// Update
void update(int rt, double y1, double y2, int flag) {
  if (cl[rt].l == y1 && cl[rt].r == y2) {
    lazy[rt] += flag;
    pushup(rt);
    return;
  } else {
    if (cl[rt * 2].r > y1) update(rt * 2, y1, min(cl[rt * 2].r, y2), flag);
    if (cl[rt * 2 + 1].l < y2)
      update(rt * 2 + 1, max(cl[rt * 2 + 1].l, y1), y2, flag);
    pushup(rt);
  }
}

int main() {
  int temp = 1, n;
  double x1, y1, x2, y2, ans;
  while (scanf("%d", &n) && n) {
    ans = 0;
    for (int i = 0; i < n; i++) {
      scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);
      p[i].x = x1;
      p[i].y1 = y1;
      p[i].y2 = y2;
      p[i].flag = 1;
      p[i + n].x = x2;
      p[i + n].y1 = y1;
      p[i + n].y2 = y2;
      p[i + n].flag = -1;
      s[i + 1] = y1;
      s[i + n + 1] = y2;
    }
    sort(s + 1, s + (2 * n + 1));  // Discretization
    sort(p, p + 2 * n, cmp);  // Sort the x-coordinates of the rectangle edges from small to large
    build(1, 1, 2 * n);       // Build tree
    memset(lazy, 0, sizeof(lazy));
    update(1, p[0].y1, p[0].y2, p[0].flag);
    for (int i = 1; i < 2 * n; i++) {
      ans += (p[i].x - p[i - 1].x) * cl[1].sum;
      update(1, p[i].y1, p[i].y2, p[i].flag);
    }
    printf("Test case #%d\nTotal explored area: %.2lf\n\n", temp++, ans);
  }
  return 0;
}

Exercises

• 「POJ1177」Picture
• 「POJ3832」Posters
• Luogu P1856 [IOI1998] [USACO5.5] Rectangle Perimeter Picture
  • The contribution of horizontal edges is the change in covered length.
  • Calculating in two directions separately avoids discussion of vertical edges.
  • When sorting operations, consider the case where two rectangle edges coincide.
  • The data range allows simulation in quadratic time without using a segment tree.

B-Dimensional Orthogonal Range

A B-dimensional orthogonal range refers to a set of points within a B-dimensional Cartesian coordinate system where the \(i\)-th coordinate lies in an integer range \([l_i,r_i]\).

Generally, a one-dimensional orthogonal range is called an interval, a two-dimensional orthogonal range is called a rectangle, and a three-dimensional orthogonal range is called a cuboid (what we often call 2D point counting is a 2D orthogonal range).

For a static 2D problem, we can use a scanline to sweep one dimension and a data structure to maintain the other dimension. As the scanline sweeps from left to right, it generates some modifications and queries on the dimension maintained by the data structure. If the queried information is differentiable, use difference directly; otherwise, use divide and conquer. Differences are usually maintained with a Fenwick tree or segment tree, but because Fenwick trees are easier to write and have smaller constants, most people choose to use a Fenwick tree. Divide and conquer usually refers to CDQ divide and conquer (but that is not covered here).

Another easier way to view the problem is from the sequence perspective rather than the 2D plane perspective. From this angle, the scanline essentially enumerates the right endpoint \(r=1\cdots n\), maintaining a data structure that supports queries: for the current \(r\), given a value \(l\), what is the answer from \(l\) to \(r\). That is, the scanline sweeps the query right endpoints, and the data structure maintains answers for all left endpoints, or traverses one dimension while the data structure maintains the other.

Complexity is generally \(O((n+m)\log n)\).

2D Point Counting

Given a sequence of length \(n\), there are \(m\) queries. Each query asks for the number of elements in the interval \([l,r]\) whose values are in \([x,y]\).

This problem is called 2D point counting. We can see it is equivalent to querying the number of points inside a rectangle on a 2D plane. Here we describe the simplest approach: scanline + Fenwick tree.

Clearly, this is a static 2D problem. We can convert it into a dynamic 1D problem via scanline. To maintain the dynamic 1D problem, we use a data structure to maintain the sequence; here we can use a Fenwick tree.

First discretize all queries. Use a Fenwick tree to maintain the values. For each query's \(l\) and \(r\), when enumerating to \(l-1\), count the current number of values in \([x,y]\), denoted \(a\). Continue enumerating; when reaching \(r\), count the current number of values in \([x,y]\), denoted \(b\). Then \(b-a\) is the answer for that query.

Example Problems

Luogu P2163 [SHOI2007] Gardener's Troubles

First discretize. Let \(ans_{x, y}\) be the number of points contained in a rectangle with lower-left corner \((0, 0)\) and upper-right corner \((x, y)\). Then the answer to a query can be expressed via difference as \(ans_{c, d} - ans_{a - 1, d} - ans_{c, b - 1} + ans_{a - 1, b - 1}\).

Code

#include <algorithm>
#include <iostream>

int n, m;
int x[500010], y[500010], ans[500010];
int ax[1500010], ay[1500010], tx, ty;  // Discretization

struct query {
  int a, b, c, d;
} q[500010];  // Save query operations for discretization

struct ope {
  int type, x, y, id;

  ope(int type = 0, int x = 0, int y = 0, int id = 0) {
    this->type = type, this->x = x, this->y = y, this->id = id;
  }

  bool operator<(const ope& rhs) const {
    if (x == rhs.x) return type < rhs.type;
    return x < rhs.x;
  }
};

ope op[2500010];
int tot;  // Total number of operations

int sum[1500010];  // Fenwick tree

int lowbit(int x) { return x & (-x); }

void add(int x, int k) {
  while (x <= 1500000) {
    sum[x] = sum[x] + k;
    x = x + lowbit(x);
  }
}

int getsum(int x) {
  int ret = 0;
  while (x > 0) {
    ret = ret + sum[x];
    x = x - lowbit(x);
  }
  return ret;
}

using std::cin;
using std::cout;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m, tx = n, ty = n;
  for (int i = 1; i <= n; i++) cin >> x[i] >> y[i], ax[i] = x[i], ay[i] = y[i];
  for (int i = 1, l, r; i <= m; i++) {
    cin >> q[i].a >> q[i].b >> q[i].c >> q[i].d;
    ax[++tx] = q[i].a, ay[++ty] = q[i].b, ax[++tx] = q[i].c, ay[++ty] = q[i].d;
  }
  std::sort(ax + 1, ax + tx + 1), std::sort(ay + 1, ay + ty + 1);
  tx = std::unique(ax + 1, ax + tx + 1) - ax - 1;
  ty = std::unique(ay + 1, ay + ty + 1) - ay - 1;
  for (int i = 1; i <= n; i++) {
    x[i] = std::lower_bound(ax + 1, ax + tx + 1, x[i]) - ax;
    y[i] = std::lower_bound(ay + 1, ay + ty + 1, y[i]) - ay;
    op[++tot] = ope(0, x[i], y[i], i);  // Add point operation
  }
  for (int i = 1; i <= m; i++) {
    q[i].a = std::lower_bound(ax + 1, ax + tx + 1, q[i].a) - ax;
    q[i].b = std::lower_bound(ay + 1, ay + ty + 1, q[i].b) - ay;
    q[i].c = std::lower_bound(ax + 1, ax + tx + 1, q[i].c) - ax;
    q[i].d = std::lower_bound(ay + 1, ay + ty + 1, q[i].d) - ay;
    op[++tot] = ope(1, q[i].c, q[i].d, i);  // Apply difference to the query
    op[++tot] = ope(1, q[i].a - 1, q[i].b - 1, i);
    op[++tot] = ope(2, q[i].a - 1, q[i].d, i);
    op[++tot] = ope(2, q[i].c, q[i].b - 1, i);
  }
  std::sort(op + 1, op + tot + 1);  // Sort operations by x-coordinate, with add point operations prioritized
  for (int i = 1; i <= tot; i++) {
    if (op[i].type == 0)
      add(op[i].y, 1);
    else if (op[i].type == 1)
      ans[op[i].id] += getsum(op[i].y);
    else
      ans[op[i].id] -= getsum(op[i].y);
  }
  for (int i = 1; i <= m; i++) cout << ans[i] << '\n';
  return 0;
}

Luogu P1908 Reverse Pairs

Indeed, reverse pairs can also be solved using scanline thinking. Consider transforming the problem of counting reverse pairs into: for each position \(i\) from back to front, count the number of points in the interval \([i+1,n]\) whose values are in \([0,a_i]\). The data range in the problem is \(10^9\), so discretization is necessary. We can traverse the array from back to front, updating the Fenwick tree (segment tree) each time we encounter a number, then count how many numbers are less than the current enumerated number. Since we traverse from back to front, the number of values smaller than the current one is exactly the number of reverse pairs for that element. This can be done with point update and range query on a Fenwick tree or segment tree.

Code

#include <algorithm>
#include <iostream>
using ll = long long;
using namespace std;

struct node {
  ll data;
  ll num;
} f[500010];

ll n, ans, a[500010];

bool cmp(node a, node b) {
  if (a.data == b.data) {
    return a.num < b.num;
  }
  return a.data < b.data;
}

ll sum[500010];

int lowbit(int x) { return x & (-x); }

void add(int x, int k) {
  while (x <= n) {
    sum[x] = sum[x] + k;
    x = x + lowbit(x);
  }
}

int getsum(int x) {
  int ret = 0;
  while (x > 0) {
    ret = ret + sum[x];
    x = x - lowbit(x);
  }
  return ret;
}

int main() {
  cin >> n;
  for (ll i = 1; i <= n; i++) {
    cin >> f[i].data;
    f[i].num = i;
  }
  sort(f + 1, f + 1 + n, cmp);
  for (int i = 1; i <= n; i++) {
    a[f[i].num] = i;
  }
  for (ll i = n; i > 0; i--) {
    ans += getsum(a[i]);
    add(a[i], 1);
  }
  cout << ans;
  return 0;
}

Luogu P1972 [SDOI2009] HH's Necklace

Brief description: Given a sequence, answer multiple queries: how many distinct numbers are in the interval \([l,r]\).

For such problems, we can derive properties and then use scanline to enumerate all right endpoints, with a data structure maintaining the answer for each left endpoint. We can also transform the problem onto a 2D plane, turning it into a rectangle query problem.

In this problem, let \(pre_i\) be the previous occurrence position of \(a_i\) in the sequence. If \(a_i\) has not appeared before, set \(pre_i = 0\). According to the problem, if a number appears multiple times in an interval, it only contributes once. We can assume that the contribution of each number comes from its first occurrence position in the interval. Then it can be seen that the total contribution equals the number of positions where \(pre_x \le l - 1\). This can be proven by contradiction.

Now the problem becomes: Given a sequence \(pre\), answer multiple queries: how many \(pre_i \le l - 1\) are in the interval \([l,r]\).

We can treat \(pre_i\) as a point on a 2D plane: \(i\) is the x-coordinate, \(pre_i\) is the y-coordinate. The problem transforms into a 2D point counting problem: each query asks for the number of points in the rectangle with lower-left corner \((l,0)\) and upper-right corner \((r,l - 1)\).

Note that this query is differentiable. We can split the query into the difference between the rectangle with lower-left \((0,0)\) and upper-right \((r,l - 1)\) and the rectangle with lower-left \((0,0)\) and upper-right \((l - 1,l - 1)\). This facilitates using scanline.

Single operation complexity is \(O(\log n)\). There are \(n\) point addition operations and \(2m\) query operations, so total time complexity is \(O((n + m) \log n)\).

Code

#include <algorithm>
#include <iostream>

int n, m, a[1000010], ans[1000010];
int pre[1000010], lst[1000010];  // Process pre

struct ope {
  int type, x, y, id;

  ope(int type = 0, int x = 0, int y = 0, int id = 0) {
    this->type = type, this->x = x, this->y = y, this->id = id;
  }

  bool operator<(const ope& rhs) const {
    if (x == rhs.x) return type < rhs.type;
    return x < rhs.x;
  }
};

ope op[2500010];
int tot;  // Total number of operations

int sum[1000010];  // Fenwick tree

int lowbit(int x) { return x & (-x); }

void add(int x, int k) {
  x++;  // Position 0 also needs modification, so all Fenwick tree indices are incremented by 1
  while (x <= n) {
    sum[x] = sum[x] + k;
    x = x + lowbit(x);
  }
}

int getsum(int x) {
  x++;
  int ret = 0;
  while (x > 0) {
    ret = ret + sum[x];
    x = x - lowbit(x);
  }
  return ret;
}

using std::cin;
using std::cout;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    pre[i] = lst[a[i]], lst[a[i]] = i;  // Process pre
    op[++tot] = ope{0, i, pre[i], i};   // Add point operation
  }
  cin >> m;
  for (int i = 1, l, r; i <= m; i++) {
    cin >> l >> r;
    op[++tot] = ope{1, r, l - 1, i};  // Difference the query
    op[++tot] = ope{2, l - 1, l - 1, i};
  }
  std::sort(op + 1, op + tot + 1);  // Sort operations by x-coordinate, with add point operations prioritized
  for (int i = 1; i <= tot; i++) {
    if (op[i].type == 0)
      add(op[i].y, 1);
    else if (op[i].type == 1)
      ans[op[i].id] += getsum(op[i].y);
    else
      ans[op[i].id] -= getsum(op[i].y);
  }
  for (int i = 1; i <= m; i++) cout << ans[i] << '\n';
  return 0;
}

Exercises

• Luogu P8593「KDOI-02」A Bullet's Throw Application of reverse pairs.
• AcWing 4709. Triple Weaker version of the above, also an application of reverse pairs.
• Luogu P8773 [Blue Bridge Cup 2022 Provincial A] Select Number XOR Modified version of HH's Necklace.
• Luogu P8844 [Chuanzhi Cup #4 Preliminary] Little Card and Fallen Leaves Transform tree problem into sequence problem and then perform 2D point counting.

In summary, the main idea of 2D point counting is to maintain one dimension with a data structure while enumerating the other dimension.

References

• cnblogs/Yang1208: Scanline Explanation, Dynamic Opening Segment Tree
• csdn/riba2534: POJ1151 Atlantis Solution
• csdn/刀刀狗 0102: POJ1151 Atlantis Solution
• A Brief Discussion on Scanline

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用