题解 P2572 【[SCOI2010]序列操作】
SuperJvRuo
2018-10-03 19:14:10
三个月之前我第一次尝试这道题的时候，我写了将近4KB的线段树，WA得只有10分。
今天突然想起这道题，十几分钟就用[珂朵莉树](https://www.luogu.org/blog/ACdreamer/chtholly-tree)水过去了。当然由于这题数据不是随机的，珂朵莉树的复杂度是错的。五种操作中有两种是区间赋值，一种是反转，另外两种是查询。都可以用珂朵莉树```split```一波然后暴力搞定。
开O2之后475ms，速度和大多数线段树差不多吧。
```
#include<cstdio>
#include<cctype>
#include<set>
#include<vector>
#include<utility>
#include<algorithm>
#define IT set<node>::iterator
int Read()
{
int x=0;char c=getchar();
while(!isdigit(c))
{
c=getchar();
}
while(isdigit(c))
{
x=x*10+(c^48);
c=getchar();
}
return x;
}
using std::set;
using std::vector;
using std::pair;
typedef long long LL;
const int MOD7 = 1e9 + 7;
const int MOD9 = 1e9 + 9;
const int imax_n = 1e5 + 7;
struct node
{
int l,r;
mutable bool v;
node(int L, int R=-1, bool V=0):l(L), r(R), v(V) {}
bool operator<(const node& o) const
{
return l < o.l;
}
};
set<node> s;
//split(pos)操作是指将原来含有pos位置的节点分成两部分：[l,pos−1]和[pos,r]
IT split(int pos)
{
IT it = s.lower_bound(node(pos));
if (it != s.end() && it->l == pos) return it;
--it;
int L = it->l, R = it->r;
bool V = it->v;
s.erase(it);
s.insert(node(L, pos-1, V));
return s.insert(node(pos, R, V)).first;
//这里利用了pair<iterator,bool> insert (const value_type& val)的返回值
}
//ass♂ign操作迅速减小set的规模
void assign_val(int l, int r, bool val)
{
IT itr = split(r+1), itl = split(l);
s.erase(itl, itr);
//void erase (iterator first, iterator last)可删除[first,last)区间
s.insert(node(l, r, val));
}
void rev(int l, int r)
{
IT itr = split(r+1), itl = split(l);
for(; itl != itr; ++itl)
{
itl->v ^= 1;
}
}
int sum(int l, int r)
{
IT itr = split(r+1),itl = split(l);
int res = 0;
for (; itl != itr; ++itl)
res += itl->v ? itl->r - itl->l + 1 : 0;
return res;
}
int conti(int l,int r)
{
int res=0,temp=0;
IT itr = split(r+1),itl = split(l);
for(; itl != itr; ++itl)
{
if(itl->v == false)
{
res = std::max(res, temp);
temp=0;
}
else
{
temp += itl->r - itl->l + 1;
}
}
return std::max(res, temp);
}
LL a[imax_n];
int main()
{
int n=Read(), m=Read();
for (int i=0; i<n; ++i)
{
s.insert(node(i,i,Read()));
}
s.insert(node(n, n, 0));
int op, a, b;
for (int i =1; i <= m; ++i)
{
op=Read(), a=Read(), b=Read();
if(op == 0)
{
assign_val(a, b, 0);
}
else if(op == 1)
{
assign_val(a, b, 1);
}
else if(op == 2)
{
rev(a, b);
}
else if(op == 3)
{
printf("%d\n",sum(a, b));
}
else
{
printf("%d\n",conti(a,b));
}
}
return 0;
}
```