【LGP5350】序列

深藏阁楼爱情的钟 2023-10-11 11:18 19阅读 0赞

[题目][Link 1]

可能\\(\\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<A.r;return l<A.l;}
    };
    std::set<node> 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<bits/stdc++.h>
    #define re register
    #define LL long long
    #define St std::set<node>::iterator
    inline 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<A.r;return l<A.l;}
    };
    std::set<node> 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;
    }

转载于:https://www.cnblogs.com/asuldb/p/11366273.html

[Link 1]: https://www.luogu.org/problem/P5350