HDU 6681 - Rikka with Cake

发表于 更新于 分类于 阅读次数：

题目链接：HDU 6681

根据欧拉定理，推得答案等于交点数量加一。

下面问题变成了二维平面上有一些于坐标轴垂直的线段，求交点个数。这是一个经典的问题。

首先我们要把点的坐标离散化，注意为了加速二分的过程，可以把横坐标和纵坐标分别离散化。

接着我们把这些线段分成两类：与 \(x\) 轴平行的和与 \(y\) 轴平行的。我们需要枚举从左到右（意味着需要排序）每一根垂直于 \(x\) 轴的线段，然后对于每一根线段，在垂直于 \(y\) 轴的线段几何中，将左端点的横坐标小于或等于它的点的右端点的横坐标扔进小根堆（意味着需要排序），并对这些线段的纵坐标所在的位置加一（树状数组或线段树维护）。接着我们需要把小根堆顶部左右的右端点小于当前枚举的 \(x\) 的删掉，并并对这些线段的纵坐标所在的位置减一。那么当前的于 \(x\) 垂直的线段上的交点个数为这个线段的起点纵坐标和重点纵坐标对应的树状数组（或线段树）的一个区间和。

所以我们只需要依次枚举所有的 \(x\)，将区间和叠加到答案上即可。时间复杂度 \(O(n \log n)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_K = 100000 + 5;
int T, n, m, K;
int cx[MAX_K], cy[MAX_K];
char dir[MAX_K];
namespace Disc {
    int x[MAX_K], y[MAX_K];
    int tx, ty;
    void run() {
        tx = ty = 0; x[++tx] = 0; y[++ty] = 0; x[++tx] = n; y[++ty] = m;
        for (int i = 1; i <= K; ++i) x[++tx] = cx[i]; sort(x + 1, x + tx + 1); tx = unique(x + 1, x + tx + 1) - x - 1;
        for (int i = 1; i <= K; ++i) y[++ty] = cy[i]; sort(y + 1, y + ty + 1); ty = unique(y + 1, y + ty + 1) - y - 1;
    }
    inline int xId(int u) {
        return lower_bound(x + 1, x + tx + 1, u) - x;
    }
    inline int yId(int u) {
        return lower_bound(y + 1, y + ty + 1, u) - y;
    }
};
namespace PointSet {
    struct Point {
        int pos, s, e;
        friend bool operator > (const Point &u, const Point &v) {
            return u.e > v.e;
        }
    } px[MAX_K], py[MAX_K];
    // px + x, py + y
    int xNum, yNum;
    void init() {
        xNum = yNum = 0;
    }
    inline void insert(int ux, int uy, int vx, int vy) {
        if (ux == vx) px[++xNum] = {ux, uy, vy};
        if (uy == vy) py[++yNum] = {uy, ux, vx};
    }
    void sortCorX() {
        sort(px + 1, px + xNum + 1, [](const Point &u, const Point &v){ return u.pos < v.pos; });
    }
    void sortCorY() {
        sort(py + 1, py + yNum + 1, [](const Point &u, const Point &v){ return u.s < v.s; });
    }
};
namespace BIT {
    int c[MAX_K];
    int maxPos;
    void init(int maxPosV) {
        maxPos = maxPosV;
        for (int i = 0; i <= maxPos; ++i) c[i] = 0;
    }
    inline int lowbit(const int &u) {
        return u & (-u);
    }
    void add(int pos, int k) {
        while (pos <= maxPos) {
            c[pos] += k; pos += lowbit(pos);
        }
    }
    int sum(int pos) {
        int ret = 0;
        while (pos >= 1) {
            ret += c[pos]; pos -= lowbit(pos);
        }
        return ret;
    }
};
priority_queue <PointSet::Point, vector <PointSet::Point>, greater <PointSet::Point> > q;
void cal() {
    scanf("%d%d%d", &n, &m, &K);
    for (int i = 1; i <= K; ++i) scanf("%d %d %c", cx + i, cy + i, dir + i);
    Disc::run();
    PointSet::init();
    int limL = Disc::xId(0), limR = Disc::xId(n), limD = Disc::yId(0), limU = Disc::yId(m);
    for (int i = 1; i <= K; ++i) {
        int x = Disc::xId(cx[i]), y = Disc::yId(cy[i]);
        switch (dir[i]) {
            case 'L': PointSet::insert(limL, y, x, y); break;
            case 'R': PointSet::insert(x, y, limR, y); break;
            case 'U': PointSet::insert(x, y, x, limU); break;
            case 'D': PointSet::insert(x, limD, x, y); break;
        }
    }
    BIT::init(Disc::ty);
    while (!q.empty()) q.pop();
    PointSet::sortCorX();
    PointSet::sortCorY();
    LL ans = 0;
    int yPtr = 1;
    for (int i = 1; i <= PointSet::xNum; ++i) {
        while (yPtr <= PointSet::yNum && PointSet::py[yPtr].s <= PointSet::px[i].pos) {
            q.push(PointSet::py[yPtr]);
            BIT::add(PointSet::py[yPtr].pos, 1);
            ++yPtr;
        }
        while (!q.empty() && q.top().e < PointSet::px[i].pos) {
            BIT::add(q.top().pos, -1);
            q.pop();
        }
        ans += (BIT::sum(PointSet::px[i].e) - BIT::sum(PointSet::px[i].s - 1));
    }
    printf("%lld\n", ans + 1);
}
int main() {
    scanf("%d", &T);
    for (int cs = 1; cs <= T; ++cs) {
        cal();
    }
    return 0;
}