珂朵莉树

适用题目特征

在数据随机条件下，维护包含区间整体赋值的操作。（即推平一段区间）

原理

珂朵莉树会将一段相同的区间用一个三元组表示。因此当数据随即时，若干次操作后，期望的三元组数量会在级别。此时对于每次区间赋值操作，只需要将对应区间分离出来，拆成两部分修改后在拼回去即可。

例题

Luogu P2572
PS：目前该题数据已不再随机生成，以下代码并无法通过所有测试点。
代码如下

/*
Luogu P2572
*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1e5+5;
const int INF=0x3f3f3f3f;
int n,m;
struct node{
    int l,r;mutable int val;
    bool operator<(const node &h)const{return l<h.l;}
};
set<node>tr;
#define IT set<node>::iterator
IT split(int pos){
    IT it=tr.lower_bound((node){pos});
    if(it!=tr.end()&&it->l==pos) return it;
    it--;
    int nl=it->l,nr=it->r,nval=it->val;
    tr.erase(it);
    tr.insert((node){nl,pos-1,nval});
    return tr.insert((node){pos,nr,nval}).first;
}
void assign(int l,int r,int val){
    IT itr=split(r+1),itl=split(l);
    tr.erase(itl,itr);
    tr.insert((node){l,r,val});
}
void reverse(int l,int r){
    IT itr=split(r+1),itl=split(l);
    for(;itl!=itr;++itl) itl->val^=1;
}
int ask1(int l,int r){
    int res=0;
    IT itr=split(r+1),itl=split(l);
    for(;itl!=itr;++itl) res+=(itl->r-itl->l+1)*itl->val;
    return res;
}
int ask2(int l,int r){
    int mx=0,sum=0;
    IT itr=split(r+1),itl=split(l);
    for(;itl!=itr;++itl) if(itl->val==1) sum+=itl->r-itl->l+1; else mx=max(mx,sum),sum=0;
    return max(mx,sum);
}
void solve(){
    int op,l,r;
    scanf("%d%d%d",&op,&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("%d\n",ask1(l,r));
    if(op==4) printf("%d\n",ask2(l,r));
}
int main() {
//  ios::sync_with_stdio(false);
//  freopen("序列操作.in","r",stdin);
    scanf("%d%d",&n,&m);
    int x;
    rep(i,1,n) scanf("%d",&x),tr.insert((node){i-1,i-1,x});
    tr.insert((node){n,n,0});
    while(m--) solve();
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif