珂学初学者手打ChthollyTreeTLE求助

P2572 [SCOI2010] 序列操作

黑影洞人 @ 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 对了,贪婪大陆可以用珂朵莉树吗


| 下一页