这题好弱智啊
裸的珂朵莉树
前置芝士：珂朵莉树
没什么好说的自己看看吧
操作1：把区间内所有数推平成0，珂朵莉树基本操作
操作2：把区间内所有数推平成1，珂朵莉树基本操作
操作3：把区间内所有数取反（异或1），split后扫描一遍，值域取反
操作4：区间和，珂朵莉树基本操作
操作5：区间最长连续的1，暴力扫描累加
就是这样简单
好像跑的比线段树还快？？？喵喵喵
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define IT set<node>::iterator
using namespace std;
inline int read()
{
register int x=0,f=1;register char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline int Max(register int a,register int b)
{
return a>b?a:b;
}
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;
inline IT split(register 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;
}
inline void assign_val(register int l,register int r,register bool val)
{
IT itr = split(r+1),itl = split(l);
s.erase(itl, itr);
s.insert(node(l, r, val));
}
inline void rev(register int l,register int r)
{
IT itr = split(r+1),itl = split(l);
for(; itl != itr; ++itl)
itl->v ^= 1;
}
inline int sum(register int l,register 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;
}
inline int count(register int l,register int r)
{
int res=0,temp=0;
IT itr = split(r+1),itl = split(l);
for(; itl != itr; ++itl)
{
if(itl->v == false)
{
res = Max(res, temp);
temp=0;
}
else
temp += itl->r - itl->l + 1;
}
return Max(res, temp);
}
int main()
{
int n=read(),m=read();
for(register int i=0;i<n;++i)
s.insert(node(i,i,read()));
s.insert(node(n,n,0));
while(m--)
{
int 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",count(a,b));
}
return 0;
}