黑影洞人 @ 2022-04-09 21:08:40
#include<cstdio>
#include<algorithm>
#include<set>
#define int long long
#define ct Chtholly_tree
#define Chtholly set<Chtholly_tree>::iterator
using namespace std;
int n,m;
struct Chtholly_tree{
int l,r;
mutable int val;
ct(int a=-1,int b=-1,int c=0){l=a,r=b,val=c;}
bool operator <(const ct &a)const{return l<a.l;}
};
set<Chtholly_tree> st;
void insert(int p,int x){
st.insert(ct(p,p,x));
}
Chtholly split(int p){
Chtholly it=st.lower_bound(ct(p));
if(it!=st.end()&&it->l==p)return it;
it--;ct tmp=*it;st.erase(it);
st.insert(ct(tmp.l,p-1,tmp.val));
return st.insert(ct(p,tmp.r,tmp.val)).first;//first return iterator
}
void assign(int l,int r,int val){
Chtholly right=split(r+1),left=split(l);
st.erase(left,right);
st.insert(ct(l,r,val));
}
void reverse(int l,int r){
Chtholly right=split(r+1),left=split(l);
for(;left!=right;left++)left->val=!(left->val);
}
int checkone(int l,int r){
int ans=0;
Chtholly right=split(r+1),left=split(l);
for(;left!=right;left++)if(left->val)ans+=left->r-left->l+1;
return ans;
}
int check_continuous_one(int l,int r){
int ans=0,t=0;
Chtholly right=split(r+1),left=split(l);
for(;left!=right;left++){
if(left->val)t+=left->r-left->l+1;
else ans=max(ans,t),t=0;
}
ans=max(ans,t);
return ans;
}
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++){
int x=0;
scanf("%lld",&x);
insert(i,x);
}
insert(n+1,0);
for(int i=1;i<=m;i++){
int op,l,r;
scanf("%lld%lld%lld",&op,&l,&r);l++,r++;
if(op==0)assign(l,r,0);
if(op==1)assign(l,r,1);
if(op==2)reverse(l,r);
if(op==3)printf("%lld\n",checkone(l,r));
if(op==4)printf("%lld\n",check_continuous_one(l,r));
}
return 0;
}
by 黑影洞人 @ 2022-04-09 21:10:11
说实话ChthollyTree很赖皮,但是至少也是一个数据结构呀,给珂学学者们一个信仰吧(悲)
by bsTiat @ 2022-04-09 21:10:33
@黑影洞人 这题ODT被卡了
by 黑影洞人 @ 2022-04-09 21:11:02
@bluespace 哭了,刚写珂朵莉树就被卡
by bsTiat @ 2022-04-09 21:11:03
@黑影洞人 ODT怎么就赖皮了,这叫赖皮吗?注意用词
by 黑影洞人 @ 2022-04-09 21:11:29
@bluespace 大佬推荐几道珂朵莉树的好题呗
by bsTiat @ 2022-04-09 21:11:52
@黑影洞人 可以写这个我做的专门的ODT题单
by 黑影洞人 @ 2022-04-09 21:12:00
@bluespace 抱歉,珂朵莉树暴力
by 黑影洞人 @ 2022-04-09 21:12:14
@bluespace 多谢
by bsTiat @ 2022-04-09 21:13:00
@黑影洞人 不客气,珂学家友谊长存!
by 黑影洞人 @ 2022-04-09 21:13:21
@bluespace 对了,贪婪大陆可以用珂朵莉树吗