HDU 6681 Rikka with Cake

Description:

Rikka's birthday is on June 12th. The story of this problem happens on that day.

Today is Rikka's birthday. Yuta prepares a big cake for her: the shape of this cake is a rectangular of $n$ centimeters times $m$ centimeters. With the guidance of a grimoire, Rikka is going to cut the cake.

For simplicity, Rikka firstly builds a Cartesian coordinate system on the cake: the coordinate of the left bottom corner is $(0,0)$ while that of the right top corner is $(n,m)$ . There are $K$ instructions on the grimoire: The ith cut is a ray starting from $(x_i,y_i)$ while the direction is $D_i$ . There are four possible directions: $L$ , passes $(x_i−1,y_i)$ ; $R$ , passes $(x_i+1,y_i)$ ; $U$ , passes $(x_i,y_i+1)$ ; $D$ , passes $(x_i,y_i−1)$ .

Take advantage of the infinite power of Tyrant's Eye, Rikka finishes all the instructions quickly. Now she wants to count the number of pieces of the cake. However, since a huge number of cuts have been done, the number of pieces can be very large. Therefore, Rikka wants you to finish this task.

Input:

The first line of the input contains a single integer $T(1 \le T \le 100)$ , the number of the test cases.

For each test case, the first line contains three positive integers $n,m,K(1 \le n,m \le 10^9,1 \le K \le 10^5)$ , which represents the shape of the cake and the number of instructions on the grimoire.

Then $K$ lines follow, the $ith$ line contains two integers $x_i,y_i(1 \le xi < n,1 \le yi < m)$ and a char $Di \in \{'L','R','U','D'\}$ , which describes the $ith$ cut.

The input guarantees that there are no more than $5$ test cases with $K > 1000$ , and no two cuts share the same $x$ coordinate or y coordinate, i.e., $\forall 1 \le i<j \le K, xi \neq xj$ and $yi \neq yj$ .

Output:

For each test case, output a single line with a single integer, the number of pieces of the cake.

Hint:

The left image and the right image show the results of the first and the second test case in the sample input respectively. Clearly, the answer to the first test case is $3$ while the second one is $5$ .
img

Sample Input:

2
4 4 3
1 1 U
2 2 L
3 3 L
5 5 4
1 2 R
3 1 U
4 3 L
2 4 D

Sample Output:

3
5

题目链接

$n \times m$ 矩形内有 $k$ 条与坐标轴平行的射线,求这些射线将矩形分为了多少个区域

显然区域数量等于射线的交点数量(每多一个个交点代表射线多分出来了一个封闭区间)

对所有坐标点离散化,用两个主席树分别维护左右两侧与 $x$ 轴平行的射线高度(与左右边界的距离)

枚举与 $y$ 轴平行的射线,利用两个主席树求它与其它射线的交点数量

需要注意的点是需要提前在上下边界添加两条与 $x$ 轴平行的射线,因为与边界的交点也会产生封闭区间

AC代码:

#include <bits/stdc++.h>
const int maxn = 4e5 + 5;
struct FuncSegTree {
  int tot;
  int rt[maxn];
  int lson[maxn * 40], rson[maxn * 40];
  int cnt[maxn * 40];
  int Build(int l, int r) {
    int o = ++tot, m = (l + r) / 2;
    cnt[o] = 0;
    if (l != r) {
      lson[o] = Build(l, m);
      rson[o] = Build(m + 1, r);
    }
    return o;
  }
  int Modify(int p, int l, int r, int v) {
    int o = ++tot, m = (l + r) / 2;
    lson[o] = lson[p];
    rson[o] = rson[p];
    cnt[o] = cnt[p] + 1;
    if (l != r) {
      if (v <= m) lson[o] = Modify(lson[o], l, m, v);
      else rson[o] = Modify(rson[o], m + 1, r, v);
    }
    return o;
  }
  long long Query(int u, int v, int s, int t, int l, int r) {
    if (s <= l && t >= r) return cnt[v] - cnt[u];
    int m = (l + r) / 2;
    long long ret = 0;
    if (s <= m) ret += Query(lson[u], lson[v], s, t, l, m);
    if (t > m) ret += Query(rson[u], rson[v], s, t, m + 1, r);
    return ret;
  }
};
int x[maxn], y[maxn];
int xsz, ysz;
struct line { int x, y; char dir; };
line opt[maxn];
FuncSegTree T1, T2;
int GetX(int _x) {
  return std::lower_bound(x + 1, x + xsz + 1, _x) - x;
}
int GetY(int _y) {
  return std::lower_bound(y + 1, y + ysz + 1, _y) - y;
}
int arr1[maxn], arr2[maxn];
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int t;
  std::cin >> t;
  while (t--) {
    int n, m, k;
    std::cin >> n >> m >> k;
    xsz = 0, ysz = 0;
    x[++xsz] = 0; y[++ysz] = 0;
    x[++xsz] = n; y[++ysz] = m;
    for (int i = 1; i <= k; ++i) {
      std::cin >> opt[i].x >> opt[i].y >> opt[i].dir;
      opt[i].y = m - opt[i].y; // 最开始以为左上角是(0,0),所以转换一下
      x[++xsz] = opt[i].x; y[++ysz] = opt[i].y;
    }
    std::sort(x + 1, x + xsz + 1);
    xsz = std::unique(x + 1, x + xsz + 1) - x - 1;
    std::sort(y + 1, y + ysz + 1);
    ysz = std::unique(y + 1, y + ysz + 1) - y - 1;
    long long ans = 1;
    for (int i = 1; i <= ysz; ++i) arr1[i] = 1;
    for (int i = 1; i <= ysz; ++i) arr2[i] = 1;
    arr1[1] = xsz; arr1[ysz] = xsz;
    arr2[1] = xsz; arr2[ysz] = xsz;
    for (int i = 1; i <= k; ++i) {
      int _x = GetX(opt[i].x), _y = GetY(opt[i].y);
      if (opt[i].dir == 'L') {
        arr1[_y] = _x;
        if (_x == xsz) ++ans;
      }
      else if (opt[i].dir == 'R') {
        arr2[_y] = xsz - _x + 1;
        if (_x == 1) ++ans;
      }
    }
    T1.tot = 0; T1.rt[0] = T1.Build(1, ysz);
    T2.tot = 0; T2.rt[0] = T2.Build(1, ysz);
    for (int i = 1; i <= ysz; ++i) {
      T1.rt[i] = T1.Modify(T1.rt[i - 1], 1, xsz, arr1[i]);
      T2.rt[i] = T2.Modify(T2.rt[i - 1], 1, xsz, arr2[i]);
    }
    for (int i = 1; i <= k; ++i) {
      if (opt[i].dir == 'L' || opt[i].dir == 'R') continue;
      int _x = GetX(opt[i].x), _y = GetY(opt[i].y);
      if (opt[i].dir == 'U') {
        ans += T1.Query(T1.rt[0], T1.rt[_y], _x, xsz, 1, xsz);
        ans += T2.Query(T2.rt[0], T2.rt[_y], xsz - _x + 1, xsz, 1, xsz);
        ans -= 2;
      }
      else if (opt[i].dir == 'D') {
        ans += T1.Query(T1.rt[_y - 1], T1.rt[ysz], _x, xsz, 1, xsz);
        ans += T2.Query(T2.rt[_y - 1], T2.rt[ysz], xsz - _x + 1, xsz, 1, xsz);
        ans -= 2;
      }
    }
    printf("%lld\n", ans);
  }
  return 0;
}
Last modification:August 19th, 2019 at 08:55 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment