洛谷 P5350 序列 珂朵莉树

• 2020 年 7 月 17 日
• 筆記
• 数据结构--珂朵莉树

题目描述

分析

操作一、二、三为珂朵莉树的基本操作，操作四、五、六稍作转化即可
不会珂朵莉树请移步至这里

求和操作

把每一段区间分别取出，暴力相加

ll qh(ll l,ll r){
    it2=Split(r+1),it1=Split(l);
    ll ans=0;
    for(it=it1;it!=it2;it++){
        ans=(ans+(it->r-it->l+1)*it->val)%mod;
    }
    return ans;
}

赋值操作

直接调用\(Assign\)函数将其推平即可

void Assign(ll l,ll r,ll val){
    it2=Split(r+1),it1=Split(l);
    s.erase(it1,it2);
    s.insert(asd(l,r,val));
}

修改操作

把每一段区间分别取出，暴力修改

void ad(ll l,ll r,ll val){
    it2=Split(r+1),it1=Split(l);
    for(it=it1;it!=it2;it++){
        it->val+=val;
        it->val%=mod;
    }
}

复制操作

将区间\([l1,r1]\)中的元素取出记录一下，加入到区间\([l2,r2]\)中即可

void fz(ll l1,ll r1,ll l2,ll r2){
    it2=Split(r1+1),it1=Split(l1);
    for(tot=0,it=it1;it!=it2;it++){
        a[++tot]=l2+it->l-l1,b[tot]=l2+it->r-l1,c[tot]=it->val;
    }
    for(ll i=1;i<=tot;++i){
	Assign(a[i],b[i],c[i]);
    }
}

交换操作

套用复制操作
我们可以先将区间\([l1,r1]\)复制到区间\([n+1,n+r1-l1+1]\)中
再将区间\([l2,r2]\)复制到区间\([l1,r1]\)中
最后再把区间\([n+1,n+r1-l1+1]\)复制到区间\([l2,r2]\)中

void jh(ll l1,ll r1,ll l2,ll r2) {
	fz(l1,r1,n+1,n+r1-l1+1);
	fz(l2,r2,l1,r1);
	fz(n+1,n+r1-l1+1,l2,r2);
}

翻转操作

把区间中的数取出，再倒序加入

vector<asd> g;
void xz(ll l,ll r){
    g.clear();
    it2=Split(r+1),it1=Split(l);
    aa=r;
    for(it=it1;it!=it2;it++){
        ll l=it->l,r=it->r,val=it->val;
        g.push_back(asd(l,r,val));
    }
    s.erase(it1,it2);
    for(ll i=0;i<g.size();i++){
        s.insert(asd(aa-(g[i].r-g[i].l),aa,g[i].val));
        aa-=(g[i].r-g[i].l+1);
    }
}

完整代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
const ll mod=1e9+7;
ll a[maxn],b[maxn],c[maxn];
struct asd{
    ll l,r;
    mutable ll val;
    bool operator < (const asd& A) const{
        return l<A.l;
    }
    asd(ll aa,ll bb,ll cc){
        l=aa,r=bb,val=cc;
    }
    asd(ll aa){
        l=aa;
    }
};
#define sit set<asd>::iterator
set<asd> s;
ll aa,bb,cc,dd,ee,n,m;
sit it,it1,it2;
sit Split(ll wz){
    it=s.lower_bound(asd(wz));
    if(it!=s.end() && it->l==wz) return it;
    it--;
    ll l=it->l,r=it->r,val=it->val;
    s.erase(it);
    s.insert(asd(l,wz-1,val));
    return s.insert(asd(wz,r,val)).first;
}
ll qh(ll l,ll r){
    it2=Split(r+1),it1=Split(l);
    ll ans=0;
    for(it=it1;it!=it2;it++){
        ans=(ans+(it->r-it->l+1)*it->val)%mod;
    }
    return ans;
}
void Assign(ll l,ll r,ll val){
    it2=Split(r+1),it1=Split(l);
    s.erase(it1,it2);
    s.insert(asd(l,r,val));
}
void ad(ll l,ll r,ll val){
    it2=Split(r+1),it1=Split(l);
    for(it=it1;it!=it2;it++){
        it->val+=val;
        it->val%=mod;
    }
}
vector<asd> g;
void xz(ll l,ll r){
    g.clear();
    it2=Split(r+1),it1=Split(l);
    aa=r;
    for(it=it1;it!=it2;it++){
        ll l=it->l,r=it->r,val=it->val;
        g.push_back(asd(l,r,val));
    }
    s.erase(it1,it2);
    for(ll i=0;i<g.size();i++){
        s.insert(asd(aa-(g[i].r-g[i].l),aa,g[i].val));
        aa-=(g[i].r-g[i].l+1);
    }
}
int tot;
void fz(ll l1,ll r1,ll l2,ll r2){
    it2=Split(r1+1),it1=Split(l1);
    for(tot=0,it=it1;it!=it2;it++){
        a[++tot]=l2+it->l-l1,b[tot]=l2+it->r-l1,c[tot]=it->val;
    }
    for(ll i=1;i<=tot;++i){
		Assign(a[i],b[i],c[i]);
    }
}
void jh(ll l1,ll r1,ll l2,ll r2) {
	fz(l1,r1,n+1,n+r1-l1+1);
	fz(l2,r2,l1,r1);
	fz(n+1,n+r1-l1+1,l2,r2);
}
int main(){
    scanf("%lld%lld",&n,&m);
    for(ll i=1;i<=n;i++){
        scanf("%lld",&aa);
        s.insert(asd(i,i,aa));
    }
    s.insert(asd(n+1,n+1,0));
    for(ll i=1;i<=m;i++){
        scanf("%lld",&aa);
        if(aa==1){
            scanf("%lld%lld",&bb,&cc);
            printf("%lld\n",qh(bb,cc));
        } else if(aa==2){
            scanf("%lld%lld%lld",&bb,&cc,&dd);
            Assign(bb,cc,dd);
        } else if(aa==3){
            scanf("%lld%lld%lld",&bb,&cc,&dd);
            ad(bb,cc,dd);
        } else if(aa==4){
            scanf("%lld%lld%lld%lld",&bb,&cc,&dd,&ee);
            fz(bb,cc,dd,ee);
        } else if(aa==5){
            scanf("%lld%lld%lld%lld",&bb,&cc,&dd,&ee);
            jh(bb,cc,dd,ee);
        } else {
            scanf("%lld%lld",&bb,&cc);
            xz(bb,cc);
        }

    }
    it2=Split(n+1),it1=Split(1);
    for(it=it1;it!=it2;it++){
        for(ll i=it->l;i<=it->r;i++)printf("%lld ",it->val%mod);
    }
    printf("\n");
    return 0;
}