题解：P6492 [COCI 2010/2011 #6] STEP
提供一种不是线段树的做法，不需要手写数据结构，就是判断稍微有点多……然后可能是我写的比较麻烦吧。
还是挺好理解的，我们使用 std::set<std::pair<int,int>>seg 这样的结构存储每一个连续的段（的左右端点），使用一个 std::multiset<int>len 这样的结构去存储所有的段长。
所以初始的情况就是每个元素对应一个独立的段。
我们注意到一次更新可能有四种情况，我们可以分别这么处理：
- 原先该元素是一个段（长度大于
1 ）的右端：修改这个元素为原先右侧段的左端点，修改这个元素的左边的元素为原先该元素所在段的右端点； - 原先该元素是一个段（长度大于
1 ）的左端：类似于上述情况，只是方向不同； - 原先该元素是一个独立的段：把左侧段、这个独立段、右侧段合成一个段；
- 原先该元素在一个段中间（既不是左端也不是右端）：与上述情况相反，删除掉这个段，并用三个段取而代之。
那么如何快速查询段长最大值呢？简单，再使用一个
std::multiset<int>就解决了嘛。
另外不要忘了同时在这个 multiset<int> 里面处理一下段的变化。
贴代码，思路不难，但是貌似代码不短。
#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;
}