动态开点线段树 | 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 longstruct 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;
}
}}