ZOJ3511 Cake Robbery 解题报告 （线段树）

题目大意

链接

给定一个凸 N 边形，将其顶点按反时针顺序从 1 开始依次标号。现有 M 条连接其两个顶点 x 和 y 的线段，保证他们在多边形内部两两不相交。问该多边形在被这 M 条线段划分以后边数最多的一个组件有多少条边。

题目保证 N 和 M 不超过 10000 ，一共有不超过 20 组测试点。

分析

这个题几乎是我见过的最巧妙的线段树题目了。主要的难点在于它看起来跟线段树没有任何关系... 我也是瞄到了别人题解才往线段树的方向想的，但是至于怎么想到线段树我还是不知道... 不过观察这个题的以后应该可以得出的结论大概有两条

1. 如果用几何方法的处理不好下手
2. 10000 的数据规模看起来很诱人，但是因为多组测试点的存在，暴力很可能会超时

可能可以把这两条和那个奇怪的条件 『线段在多边形内部不相交』 作为切入点，然后往线段树的方向想

现在假设我们知道这个题用线段树可解。那么由于被切下来的部分也是凸多边形，所以我们可以把问题转化为组件的最大顶点数。从而对于每次划分，直接

query(L, R) 再 reset(L + 1, R - 1)

即可。

不过这样会有一个问题，即如果某一片被切下来的组件还有后续的修改，那么将很难直接维护（需要追踪当前时刻的所有组件）。所幸我们发现，切割的顺序并不影响最终的答案。因此，我们只要先处理两个端点相隔较近的线段即可，不管怎么说每块的顶点数总不会越分越多。

我们这样似乎就完美地解决了这个问题。不过不要忘记最后处理完所有分割线以后对剩余的部分再做一次询问。

代码

总复杂度为 O(T×mlog(n))

#include <bits/stdc++.h>

using namespace std;

const int maxn = 11234;

struct Segment {
    int l, r, cnt;
} tree[maxn << 2];

int n, m;

void build(int o, int l, int r) {
    tree[o].l = l;
    tree[o].r = r;
    if (l == r) {
        tree[o].cnt = l <= n;
        return;
    }
    int m = l + r >> 1;
    build(o << 1, l, m);
    build(o << 1 | 1, m + 1, r);
    tree[o].cnt = tree[o << 1].cnt + tree[o << 1 | 1].cnt;
}

void update(int o, int l, int r) {
    if (!tree[o].cnt) return;
    if (l <= tree[o].l && tree[o].r <= r) {
        tree[o].cnt = 0;
        return;
    }
    int m = tree[o].l + tree[o].r >> 1;
    if (l <= m) update(o << 1, l, r);
    if (r > m) update(o << 1 | 1, l, r);
    tree[o].cnt = tree[o << 1].cnt + tree[o << 1 | 1].cnt;
}

int query(int o, int l, int r) {
    if (!tree[o].cnt) return 0;
    if (l <= tree[o].l && tree[o].r <= r) return tree[o].cnt;
    int m = tree[o].l + tree[o].r >> 1, ret = 0;
    if (l <= m) ret += query(o << 1, l, r);
    if (r > m) ret += query(o << 1 | 1, l, r);
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    while (cin >> n >> m) {
        build(1, 1, 1 << 14);
        vector<pair<int, int>> cuts;
        while (m--) {
            int x, y;
            cin >> x >> y;
            if (x > y) swap(x, y);
            if (y - x < 2) continue;
            cuts.emplace_back(x, y);
        }
        sort(cuts.begin(), cuts.end(),
             [](pair<int, int> a, pair<int, int> b) { 
                 return a.second - a.first < b.second - b.first; });
        int ans = 0;
        for (auto now : cuts) {
            ans = max(ans, query(1, now.first, now.second));
            update(1, now.first + 1, now.second - 1);
        }
        ans = max(ans, query(1, 1, n));
        cout << ans << '\n';
    }
}