题解：P6492 [COCI 2010/2011 #6] STEP

提供一种不是线段树的做法，不需要手写数据结构，就是判断稍微有点多……然后可能是我写的比较麻烦吧。

还是挺好理解的，我们使用 std::set<std::pair<int,int>>seg 这样的结构存储每一个连续的段（的左右端点），使用一个 std::multiset<int>len 这样的结构去存储所有的段长。

所以初始的情况就是每个元素对应一个独立的段。

我们注意到一次更新可能有四种情况，我们可以分别这么处理：

原先该元素是一个段（长度大于 $1$ ）的右端：修改这个元素为原先右侧段的左端点，修改这个元素的左边的元素为原先该元素所在段的右端点；
原先该元素是一个段（长度大于 $1$ ）的左端：类似于上述情况，只是方向不同；
原先该元素是一个独立的段：把左侧段、这个独立段、右侧段合成一个段；
原先该元素在一个段中间（既不是左端也不是右端）：与上述情况相反，删除掉这个段，并用三个段取而代之。那么如何快速查询段长最大值呢？简单，再使用一个 std::multiset<int> 就解决了嘛。

另外不要忘了同时在这个 multiset<int> 里面处理一下段的变化。

贴代码，思路不难，但是貌似代码不短。

CPP

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0),cin.tie(0);
    int n, q;
    cin>>n>>q;
    vector<int> a(n+1, 0);
    set<pair<int, int>> seg;
    multiset<int> len;
    for (int i = 1; i <= n; i++) {
        seg.insert({i, i});
        len.insert(1);
    }
    while (q--) {
        int x;
        cin>>x;
        a[x] = 1 - a[x];

        auto it = seg.upper_bound({x, n+5});
        if (it == seg.begin()) {
            if (len.empty()) printf("0\n");
            else {
                auto it_max = len.end();
                it_max--;
                printf("%d\n", *it_max);
            }
            continue;
        }
        it--;
        int l = it->first, r = it->second;
        if (l > x || r < x) {
            if (len.empty()) printf("0\n");
            else {
                auto it_max = len.end();
                it_max--;
                printf("%d\n", *it_max);
            }
            continue;
        }
        seg.erase(it);
        auto it_len = len.find(r - l + 1);
        if (it_len != len.end()) len.erase(it_len);
        vector<pair<int, int>> to_add;
        if (l <= x - 1) to_add.push_back({l, x - 1});
        to_add.push_back({x, x});
        if (x + 1 <= r) to_add.push_back({x + 1, r});

        for (auto &p : to_add) {
            seg.insert(p);
            len.insert(p.second - p.first + 1);
        }
        if (x > 1 && a[x - 1] != a[x]) {
            auto it_left = seg.upper_bound({x - 1, n + 5});
            if (it_left != seg.begin()) {
                it_left--;
                if (it_left->first <= x - 1 && it_left->second >= x - 1) {
                    auto it_cur = seg.upper_bound({x, n + 5});
                    if (it_cur != seg.begin()) {
                        it_cur--;
                        if (it_cur->first <= x && it_cur->second >= x)
                            if (it_left->second == x - 1 && it_cur->first == x) {
                                int l1 = it_left->first, r1 = it_left->second;
                                int l2 = it_cur->first, r2 = it_cur->second;
                                seg.erase(it_left);
                                seg.erase(it_cur);
                                auto it1 = len.find(r1 - l1 + 1);
                                if (it1 != len.end()) len.erase(it1);
                                auto it2 = len.find(r2 - l2 + 1);
                                if (it2 != len.end()) len.erase(it2);
                                pair<int, int> new_seg = {l1, r2};
                                seg.insert(new_seg);
                                len.insert(r2 - l1 + 1);
                            }
                    }
                }
            }
        }
        if (x < n && a[x] != a[x + 1]) {
            auto it_cur = seg.upper_bound({x, n + 5});
            if (it_cur != seg.begin()) {
                it_cur--;
                if (it_cur->first <= x && it_cur->second >= x) {
                    auto it_right = seg.upper_bound({x + 1, n + 5});
                    if (it_right != seg.begin()) {
                        it_right--;
                        if (it_right->first <= x + 1 && it_right->second >= x + 1)
                            if (it_cur->second == x && it_right->first == x + 1) {
                                int l1 = it_cur->first, r1 = it_cur->second;
                                int l2 = it_right->first, r2 = it_right->second;
                                seg.erase(it_cur);
                                seg.erase(it_right);
                                auto it1 = len.find(r1 - l1 + 1);
                                if (it1 != len.end()) len.erase(it1);
                                auto it2 = len.find(r2 - l2 + 1);
                                if (it2 != len.end()) len.erase(it2);
                                pair<int, int> new_seg = {l1, r2};
                                seg.insert(new_seg);
                                len.insert(r2 - l1 + 1);
                            }
                    }
                }
            }
        }
        if (len.empty())cout<<0<<'\n';
        else {
            auto it_max = len.end();
            it_max--;
            cout<<*it_max<<'\n';
        }
    }
    return 0;
}

题解：P6492 [COCI 2010/2011 #6] STEP

文章操作

相关推荐

评论

题解：P6492 [COCI 2010/2011 #6] STEP