【数据结构】动态开点线段树

动态开点线段树 | henrytb's blog (henrytbtrue.github.io) 

算法学习笔记(49): 线段树的拓展 - 知乎 (zhihu.com)

星际旅行 终于拿到80pts啦

计算机软件能力认证考试系统

#include<iostream>
using namespace std;
#define ll long long
const ll N=100010;
const ll mod=1e9+7;
#define ll long long

struct Tree{
ll ls,rs;
ll len;
ll s[3];
ll k;ll mul[3];ll add[3];
}tr[4*3*N];ll idx=0;





void rotatee(ll a[]){
ll temp=a[0];
a[0]=a[1];a[1]=a[2];a[2]=temp;

}

void eval(Tree& u,ll k){
k%=3;for(ll i=1;i<=k;i++){
rotatee(u.s);rotatee(u.mul);rotatee(u.add);
}
u.k=(u.k+k)%3;
}
void eval(Tree& u,ll a[],ll b[]){
for(ll i=0;i<3;i++){
    u.s[i]=(u.s[i]*a[i]%mod+b[i]*u.len%mod)%mod;
    u.mul[i]=(u.mul[i]*a[i])%mod;
    u.add[i]=(u.add[i]*a[i]%mod+b[i])%mod;
}

}




void pushup(Tree& u,Tree& l,Tree& r){
for(ll i=0;i<3;i++)u.s[i]=(l.s[i]+r.s[i])%mod;

}void pushup(ll u){
pushup(tr[u],tr[tr[u].ls],tr[tr[u].rs]);
}

void pushdown(Tree& u,Tree& l,Tree& r){
eval(l,u.k);eval(r,u.k);
eval(l,u.mul,u.add);eval(r,u.mul,u.add);
u.k=0;for(ll i=0;i<3;i++)u.mul[i]=1,u.add[i]=0;
}
void pushdown(ll u){pushdown(tr[u],tr[tr[u].ls],tr[tr[u].rs]);
}






ll add(ll l,ll r){
ll u=++idx;
tr[u].ls=tr[u].rs=0;
tr[u].len=r-l+1;
tr[u].s[0]=tr[u].s[1]=tr[u].s[2]=0;
tr[u].k=0;for(ll i=0;i<3;i++)tr[u].mul[i]=1,tr[u].add[i]=0;
return u;
}


void modify(ll& u,ll l,ll r,ll x,ll y,ll k,ll a[],ll b[]){
if(!u)u=add(l,r);
if(x<=l&&r<=y){
    eval(tr[u],k);
    eval(tr[u],a,b);
    return ;
}

ll mid=(l+r)>>1;
if(!tr[u].ls)tr[u].ls=add(l,mid);
if(!tr[u].rs)tr[u].rs=add(mid+1,r);
pushdown(u);
if(x<=mid)modify(tr[u].ls,l,mid,x,y,k,a,b);
if(y>=mid+1)modify(tr[u].rs,mid+1,r,x,y,k,a,b);
pushup(u);
}

Tree query(ll& u,ll l,ll r,ll x,ll y){
if(!u)u=add(l,r);
if(x<=l&&r<=y){
    return tr[u];
}

ll mid=(l+r)>>1;
if(!tr[u].ls)tr[u].ls=add(l,mid);
if(!tr[u].rs)tr[u].rs=add(mid+1,r);
pushdown(u);
if(y<=mid)return query(tr[u].ls,l,mid,x,y);
else if(x>=mid+1)return query(tr[u].rs,mid+1,r,x,y);
else {
    Tree leftt=query(tr[u].ls,l,mid,x,y);
    Tree rightt=query(tr[u].rs,mid+1,r,x,y);
    Tree root;
    pushup(root,leftt,rightt);
    return root;
}

}



ll get_ans(ll s[]){
    ll res=0;
for(ll i=0;i<3;i++){
    res=(res+s[i]*s[i]%mod)%mod;
}
return res;
}
int  main(){
    ll n,m;
cin>>n>>m;

ll root=0;
ll L=1;ll R=n+10;
while(m--){
        ll op;ll x,y;cin>>op>>x>>y;
        ll a[3]={1,1,1};ll b[3]={0,0,0};
if(op==1){
    cin>>b[0]>>b[1]>>b[2];
    modify(root,L,R,x,y,0,a,b);
}
else if(op==2){
    cin>>a[0];a[1]=a[2]=a[0];
    modify(root,L,R,x,y,0,a,b);
}
else if(op==3){
    modify(root,L,R,x,y,1,a,b);
}
else {
    cout<<get_ans(query(root,L,R,x,y).s)%mod<<endl;
}
}

}