HDU 6681 树状数组欧拉公式

119 阅读 0 评论 79 点赞

我是靠谱客的博主淡然巨人，这篇文章主要介绍HDU 6681 树状数组欧拉公式，现在分享给大家，希望可以做个参考。

给一个长方形的?, 切k刀, 每一刀是顶点互不重合且在蛋糕内, 平行坐标轴的射线, 问把?切成了几块.
欧拉公式: $V - E + F = 2$ 即 $点数 - 边数 + 面数 = 2$ .
原来欧拉公式对于这样由射线组成的不规则图形也是成立的…
这样, 这个题就由求面数转化为求点数和边数.

用欧拉（欧拉欧拉欧拉）公式 $V - E + F = 2$ 来算蛋糕的块数。
首先考虑点数 $V$ ，蛋糕的四个角以及射线的端点贡献了 $n + 4$ 个顶点，射线和四条边的交点共有 $n$ 个，射线之间的交点有 $c$ 个，因此点数是 $2 n + 4 + c$ 。接着考虑边数，对于每一条射线，假设别的射线和他的交点有 $c [i]$ 个，那么这条射线被切成了 $c [i] + 1$ 段，因此所有射线的边数对应的是 $2 c + n$ （因为每一个交点被用了两次）。同时因为四条边一共和射线交了 $n$ 次，所以四条边界上共有 $n + 4$ 条边，所以 $E = 2 c + 2 n + 4$ 。因此总的区域数为 $F = E + 2 - V = c + 2$ ，因为要去掉外面的无穷区域，所以答案就是 $c + 1$ 。于是问题就变成了求交点个数。这是一个经典的问题，分四个方向讨论一下离散化用树状数组求就行。时间复杂度 $O(nlog{n})$

所求即为: 射线交点个数+1.
考虑一条向左的射线, 它的左下方的向上的射线条数和右上方向下的条数的和就是它能贡献的交点; 同理, 向右的射线它的右下方有多少向上和右上方有多少向下的射线的个数就是总贡献的另一半(因为交点只用了水平方向的射线计算, 所以不会重复).
考虑一个向左射线的左下角. 在这个区域的所有向上的射线会算入答案. 那么对于所有向左的点, 我们都要查询其左下有多少个向上的点. 把这两类点放到一起按照横坐标从小到大排序, 那么排除了横坐标比查询点大的点的贡献, 如何保证纵坐标小于查询点呢? 我们可以离散化纵坐标, 用BIT维护纵坐标小于某值的点的个数. 这样保证了横纵坐标都小于给定点, 答案就是正确的了.
向左射线的左上角: 由横坐标小, 纵坐标大的点贡献, 所以按照横坐标从小到大排序, BIT查询大于当前点纵坐标的点的个数.
向右射线的右下角: 由横坐标大, 纵坐标小的点贡献, 所以按照横坐标从大到小排序, BIT查询小于当前点纵坐标的点的个数.
向右射线的右上角: 由横坐标大, 纵坐标大的点贡献, 所以按照横坐标从大到小排序, BIT查询大于当前点纵坐标的点的个数.
代码:

复制代码

int lowbit(int x) { return x & (-x); }
const int M = 212345;// 2e5+5
ll c[M * 2];
void add(int x, ll t, int n) {while (x <= n) {c[x] += t;x += lowbit(x);}}
ll query(int x) {ll ret = 0;while (x > 0) {ret += c[x];x -= lowbit(x);}return ret;}

struct node {int x, y, type;};
vector<node> cut[5];//   1up 2down 3left 4right

vector<int> lSanY;
int getId(int x) {return lower_bound(all(lSanY), x) - lSanY.begin() + 1;}

vector<node> tmp;
bool cmp(node a, node b) {return a.x < b.x;}
bool cmp2(node a, node b) {return a.x > b.x;}

ll ans;

void cal(int hr, int vr) {
    Mem(c, 0);
    tmp.clear();
    tmp.insert(tmp.end(), all(cut[hr]));
    tmp.insert(tmp.end(), all(cut[vr]));
    if (hr == 3)sort(all(tmp), cmp);//向左, 横坐标从小到大排序
    else sort(all(tmp), cmp2);//向右, 横坐标从大到小排序
    for (auto p:tmp) {
        if (p.type == 3 || p.type == 4) {//水平方向的点 查询
            if (vr == 2)ans += query(lSanY.size() + 100) - query(getId(p.y) - 1);//第2或第3象限应该查纵坐标大的点的个数
            else ans += query(getId(p.y));//第1或第4象限应该查纵坐标小的点的个数
        } else {// 垂直方向的点 更新
            add(getId(p.y), 1, lSanY.size() + 100);
        }
    }
}

void init() {
    int _ = read();
    while (_--) {
        cut[1].clear(), cut[2].clear(), cut[3].clear(), cut[4].clear();
        lSanY.clear();

int n = read(), m = read(), k = read();
        for (int i = 1; i <= k; ++i) {
            int x = read(), y = read();
            lSanY.emplace_back(y);
            char op[3];
            scanf("%s", op);
            int type = op[0] == 'U' ? 1 : op[0] == 'D' ? 2 : op[0] == 'L' ? 3 : 4;
            cut[type].emplace_back((node) {x, y, type});
        }
        sort(all(lSanY));
        lSanY.erase(unique(all(lSanY)), lSanY.end());
        for (int i = 3; i <= 4; ++i) 
            for (int j = 1; j <= 2; ++j) 
                cal(i, j);
        write(ans + 1), enter, ans = 0;
    }
}

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
int lowbit(int x) { return x & (-x); }
const int M = 212345;// 2e5+5
ll c[M * 2];
void add(int x, ll t, int n) {while (x <= n) {c[x] += t;x += lowbit(x);}}
ll query(int x) {ll ret = 0;while (x > 0) {ret += c[x];x -= lowbit(x);}return ret;}


struct node {int x, y, type;};
vector<node> cut[5];//   1up 2down 3left 4right

vector<int> lSanY;
int getId(int x) {return lower_bound(all(lSanY), x) - lSanY.begin() + 1;}


vector<node> tmp;
bool cmp(node a, node b) {return a.x < b.x;}
bool cmp2(node a, node b) {return a.x > b.x;}

ll ans;

void cal(int hr, int vr) {
    Mem(c, 0);
    tmp.clear();
    tmp.insert(tmp.end(), all(cut[hr]));
    tmp.insert(tmp.end(), all(cut[vr]));
    if (hr == 3)sort(all(tmp), cmp);//向左, 横坐标从小到大排序
    else sort(all(tmp), cmp2);//向右, 横坐标从大到小排序
    for (auto p:tmp) {
        if (p.type == 3 || p.type == 4) {//水平方向的点 查询
            if (vr == 2)ans += query(lSanY.size() + 100) - query(getId(p.y) - 1);//第2或第3象限应该查纵坐标大的点的个数
            else ans += query(getId(p.y));//第1或第4象限应该查纵坐标小的点的个数
        } else {// 垂直方向的点 更新
            add(getId(p.y), 1, lSanY.size() + 100);
        }
    }
}


void init() {
    int _ = read();
    while (_--) {
        cut[1].clear(), cut[2].clear(), cut[3].clear(), cut[4].clear();
        lSanY.clear();

        int n = read(), m = read(), k = read();
        for (int i = 1; i <= k; ++i) {
            int x = read(), y = read();
            lSanY.emplace_back(y);
            char op[3];
            scanf("%s", op);
            int type = op[0] == 'U' ? 1 : op[0] == 'D' ? 2 : op[0] == 'L' ? 3 : 4;
            cut[type].emplace_back((node) {x, y, type});
        }
        sort(all(lSanY));
        lSanY.erase(unique(all(lSanY)), lSanY.end());
        for (int i = 3; i <= 4; ++i) 
            for (int j = 1; j <= 2; ++j) 
                cal(i, j);
        write(ans + 1), enter, ans = 0;
    }
}