珂学初学者手打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:13:43

@bluespace 珂!


by bsTiat @ 2022-04-09 21:16:18

@黑影洞人 贪婪大陆不行吧,你一个区间会被多次覆盖,但是每次操作都对答案有影响


by 幽云蓝 @ 2022-04-09 21:16:45

建议在使用珂朵莉树前先了解相关原理,比如珂朵莉树的复杂度证明


by 黑影洞人 @ 2022-04-09 21:19:56

@bluespace 哦哦,多谢


by 黑影洞人 @ 2022-04-09 21:20:14

@八云蓝 好的,我比较初学


by 幽云蓝 @ 2022-04-09 21:30:46

@黑影洞人 那建议先学一下颜色段均摊和相关原理,这样至少能知道在除了操作随机的题外什么样的题中可以使用珂朵莉树(


by 黑影洞人 @ 2022-04-09 21:33:42

@八云蓝 好的,谢谢


上一页 |