可能\(\operatorname{fhq\ treap}\)能做，但是珂朵莉树显然更好写

珂朵莉树是个很玄学的东西啊，就是直接使用\(\operatorname{std::set}\)维护每一段权值相等的连续段，之后暴力这些连续段就好了

在数据随机的意义下且有区间推平操作的时候，连续段的个数是期望\(\log\)的

核心操作是\(split(pos)\)，就是把\(pos\)分裂出来，返回一个以\(pos\)为开头的连续段的迭代器

具体实现这样就好了

struct node {    int l,r;    mutable int v;    bool operator<(const node &A) const {if(l==A.l) return r
    
      s;inline St split(int pos) {    St it=s.lower_bound((node){pos,-1,0});    if(it!=s.end()&&it->l==pos) return it;    --it;    int L=it->l,R=it->r,v=it->v;    s.erase(it);    s.insert((node){L,pos-1,v});    return s.insert((node){pos,R,v}).first;}
    

我们操作区间\([l,r]\)的时候，只需要\(x=split(l),y=split(r+1)\)，那么对应的\([x,y)\)就是我们要操作的迭代器了

暴力操作这些迭代器即可

一个非常关键的问题，就是我们必须先\(split(r+1)\)，之后再\(split(l)\)，如果先\(split(l)\)的话可能在\(split(r+1)\)的时候会删除\(l\)所在的区间导致迭代器失效

代码

#include
    
     #define re register#define LL long long#define St std::set
     
      ::iteratorinline int read() {    char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;}const int mod=1e9+7;const int maxn=3e5+5;int lx[maxn],ry[maxn],t[maxn],n,m;struct node {    int l,r;    mutable int v;    bool operator<(const node &A) const {if(l==A.l) return r
      
        s;inline St split(int pos) {    St it=s.lower_bound((node){pos,-1,0});    if(it!=s.end()&&it->l==pos) return it;    --it;    int L=it->l,R=it->r,v=it->v;    s.erase(it);    s.insert((node){L,pos-1,v});    return s.insert((node){pos,R,v}).first;}inline void del(int l,int r) {    St itr=split(r+1),itl=split(l);    s.erase(itl,itr);}inline void pia(int l,int r,int v) {    St itr=split(r+1),it=split(l);    s.erase(it,itr);    s.insert((node){l,r,v});}inline void add(int l,int r,int val) {    St itr=split(r+1),it=split(l);    for(;it!=itr;++it) it->v=(it->v+val)%mod;}inline int calc(int l,int r) {    int ans=0;    St itr=split(r+1),it=split(l);    for(;it!=itr;++it) ans=(ans+1ll*it->v*(it->r-it->l+1)%mod)%mod;    return ans;}inline void rev(int l,int r) {    int tot=0,len=r+l;    St itr=split(r+1),it=split(l);    St a=it;    for(;it!=itr;++it) lx[++tot]=(*it).l,ry[tot]=(*it).r,t[tot]=(*it).v;    s.erase(a,itr);    for(re int i=1;i<=tot;i++)        s.insert((node){len-ry[i],len-lx[i],t[i]}); }inline void move(int l1,int r1,int l2,int r2) {    int tot=0;    St itr=split(r1+1),it=split(l1);    for(;it!=itr;++it) lx[++tot]=(*it).l,ry[tot]=(*it).r,t[tot]=(*it).v;    itr=split(r2+1),it=split(l2);    s.erase(it,itr);    for(re int i=1;i<=tot;i++)        s.insert((node){lx[i]+l2-l1,ry[i]+r2-r1,t[i]});}inline void Swap(int l1,int r1,int l2,int r2) {    int tot=0,cnt=0;    St itr=split(r1+1),it=split(l1);    for(;it!=itr;++it) lx[++tot]=(*it).l,ry[tot]=(*it).r,t[tot]=(*it).v;    cnt=tot;itr=split(r2+1),it=split(l2);    for(;it!=itr;++it) lx[++tot]=(*it).l,ry[tot]=(*it).r,t[tot]=(*it).v;    del(l1,r1),del(l2,r2);    for(re int i=1;i<=cnt;i++)        s.insert((node){lx[i]+l2-l1,ry[i]+r2-r1,t[i]});    for(re int i=cnt+1;i<=tot;i++)        s.insert((node){lx[i]-l2+l1,ry[i]-r2+r1,t[i]});    }inline void out() {    St it=s.begin();    for(;it!=s.end();++it)         for(re int j=it->l;j<=it->r;++j)            printf("%d ",it->v);    puts("");}int main() {    n=read(),m=read();    for(re int i=1;i<=n;i++) s.insert((node){i,i,read()});    int op,l,r,x,y,val;    while(m--) {        op=read(),l=read(),r=read();        if(op==1) printf("%d\n",calc(l,r));        if(op==2||op==3) val=read();        if(op==2) pia(l,r,val);        if(op==3) add(l,r,val);        if(op==6) rev(l,r);        if(op==4||op==5) x=read(),y=read();        if(op==4) move(l,r,x,y);        if(op==5) Swap(l,r,x,y);    }    out();    return 0;}