題目大意

鏈接

給定一個(gè)凸 N 邊形，將其頂點(diǎn)按反時(shí)針順序從 1 開(kāi)始依次標(biāo)號(hào)?，F(xiàn)有 M 條連接其兩個(gè)頂點(diǎn) x 和 y 的線(xiàn)段，保證他們?cè)诙噙呅蝺?nèi)部?jī)蓛刹幌嘟弧?wèn)該多邊形在被這 M 條線(xiàn)段劃分以后邊數(shù)最多的一個(gè)組件有多少條邊。

題目保證 N 和 M 不超過(guò) 10000 ，一共有不超過(guò) 20 組測(cè)試點(diǎn)。

分析

這個(gè)題幾乎是我見(jiàn)過(guò)的最巧妙的線(xiàn)段樹(shù)題目了。主要的難點(diǎn)在于它看起來(lái)跟線(xiàn)段樹(shù)沒(méi)有任何關(guān)系... 我也是瞄到了別人題解才往線(xiàn)段樹(shù)的方向想的，但是至于怎么想到線(xiàn)段樹(shù)我還是不知道... 不過(guò)觀(guān)察這個(gè)題的以后應(yīng)該可以得出的結(jié)論大概有兩條

1. 如果用幾何方法的處理不好下手
2. 10000 的數(shù)據(jù)規(guī)?？雌饋?lái)很誘人，但是因?yàn)槎嘟M測(cè)試點(diǎn)的存在，暴力很可能會(huì)超時(shí)

可能可以把這兩條和那個(gè)奇怪的條件 『線(xiàn)段在多邊形內(nèi)部不相交』 作為切入點(diǎn)，然后往線(xiàn)段樹(shù)的方向想

現(xiàn)在假設(shè)我們知道這個(gè)題用線(xiàn)段樹(shù)可解。那么由于被切下來(lái)的部分也是凸多邊形，所以我們可以把問(wèn)題轉(zhuǎn)化為組件的最大頂點(diǎn)數(shù)。從而對(duì)于每次劃分，直接

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

即可。

不過(guò)這樣會(huì)有一個(gè)問(wèn)題，即如果某一片被切下來(lái)的組件還有后續(xù)的修改，那么將很難直接維護(hù)（需要追蹤當(dāng)前時(shí)刻的所有組件）。所幸我們發(fā)現(xiàn)，切割的順序并不影響最終的答案。因此，我們只要先處理兩個(gè)端點(diǎn)相隔較近的線(xiàn)段即可，不管怎么說(shuō)每塊的頂點(diǎn)數(shù)總不會(huì)越分越多。

我們這樣似乎就完美地解決了這個(gè)問(wèn)題。不過(guò)不要忘記最后處理完所有分割線(xiàn)以后對(duì)剩余的部分再做一次詢(xún)問(wèn)。

代碼

總復(fù)雜度為 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';
    }
}