【線分木】基礎版
20439 ワード
1>区間加算+区間と問合せ
2>区間加算+区間乗算+区間と問合せ
カスタム:d[i]*mul+add
#include
#include
#define int long long
using namespace std;
int n,m;
const int N=1e6+3;
int d[N];
struct node
{
int son1,son2;
int sum,laz,len;
}tr[N<<2];
int root,cnt;
void updata(int rt)
{
int a=tr[rt].son1 ,b=tr[rt].son2 ;
tr[rt].sum =tr[a].sum +tr[b].sum ;
}
void build(int &rt,int l,int r)
{
rt=++cnt;
tr[rt].len =r-l+1;
if(l==r)
{
tr[rt].sum =d[l];
return ;
}
int mid=(l+r)>>1;
build(tr[rt].son1 ,l,mid);
build(tr[rt].son2 ,mid+1,r);
updata(rt);
}
void push_down(int rt)
{
int a=tr[rt].son1 ,b=tr[rt].son2 ,v=tr[rt].laz ;
tr[a].laz +=v,tr[b].laz +=v;
tr[a].sum +=v*tr[a].len ,tr[b].sum +=v*tr[b].len ;
tr[rt].laz =0;
}
void change(int rt,int l,int r,int ll,int rr,int vv)
{
if(ll<=l && r<=rr)
{
tr[rt].laz +=vv,tr[rt].sum +=tr[rt].len *vv;
return ;
}
if(tr[rt].laz ) push_down(rt);
int mid=(l+r)>>1;
if(rr<=mid) change(tr[rt].son1 ,l,mid,ll,rr,vv);
else if(ll>mid) change(tr[rt].son2 ,mid+1,r,ll,rr,vv);
else change(tr[rt].son1 ,l,mid,ll,mid,vv),change(tr[rt].son2 ,mid+1,r,mid+1,rr,vv);// ???
updata(rt);
}
int query(int rt,int l,int r,int ll,int rr)
{
if(ll<=l && r<=rr)
return tr[rt].sum ;
if(tr[rt].laz ) push_down(rt);
int mid=(l+r)>>1;
if(rr<=mid) return query(tr[rt].son1 ,l,mid,ll,rr);
else if(ll>mid) return query(tr[rt].son2 ,mid+1,r,ll,rr);
return query(tr[rt].son1 ,l,mid,ll,rr)+query(tr[rt].son2 ,mid+1,r,ll,rr);
}
signed main()
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)
scanf("%lld",&d[i]);
build(root,1,n);
int op,ll,rr,vv;
while(m--)
{
scanf("%lld%lld%lld",&op,&ll,&rr);
if(op==1)
{
scanf("%lld",&vv);
change(1,1,n,ll,rr,vv);
}
else
printf("%lld
",query(1,1,n,ll,rr));
}
return 0;
}
2>区間加算+区間乗算+区間と問合せ
カスタム:d[i]*mul+add
#include
#include
#define int long long
using namespace std;
int n,m,mod;
const int N=1e5+3;
int d[N],root,cnt;
struct node
{
int son1,son2,len;
int sum,laz,LAZ;
// , , d*LAZ+laz
//add ,
//mul , laz!=0, push_down
//push_down , LAZ!=1 =》 laz,LAZ,sum *mul
// laz
}tr[N*3];
void updata(int rt)
{
tr[rt].sum=(tr[tr[rt].son1].sum +tr[tr[rt].son2].sum)%mod;
}
void build(int &rt,int l,int r)
{
rt=++cnt;
tr[rt].LAZ =1,tr[rt].len =r-l+1;
if(l==r)
{
tr[rt].sum=d[l]%mod;
return ;
}
int mid=(l+r)>>1;
build(tr[rt].son1 ,l,mid);
build(tr[rt].son2 ,mid+1,r);
updata(rt);
}
void push_down(int rt)
{
int a=tr[rt].son1 ,b=tr[rt].son2 ;
if(tr[rt].LAZ !=1)
{
int t=tr[rt].LAZ ;
tr[a].sum =(tr[a].sum *t)%mod;
tr[a].LAZ =(tr[a].LAZ *t)%mod;
tr[a].laz =(tr[a].laz *t)%mod;
tr[b].sum =(tr[b].sum *t)%mod;
tr[b].LAZ =(tr[b].LAZ *t)%mod;
tr[b].laz =(tr[b].laz *t)%mod;
tr[rt].LAZ =1;
}
if(tr[rt].laz )
{
int t=tr[rt].laz ;
tr[a].sum =(tr[a].sum +t*tr[a].len )%mod;
tr[a].laz =(tr[a].laz +t)%mod;
tr[b].sum =(tr[b].sum +t*tr[b].len )%mod;// len...
tr[b].laz =(tr[b].laz +t)%mod;
tr[rt].laz =0;
}
}
void add(int rt,int l,int r,int ql,int qr,int v)
{
if(ql<=l && r<=qr)
{
tr[rt].sum =(tr[rt].sum + v*tr[rt].len%mod)%mod;
tr[rt].laz =(tr[rt].laz + v)%mod;
return ;
}
push_down(rt);
int mid=(l+r)>>1;
if(qr<=mid) add(tr[rt].son1 ,l,mid,ql,qr,v);
else if(ql>mid) add(tr[rt].son2 ,mid+1,r,ql,qr,v);
else add(tr[rt].son1 ,l,mid,ql,mid,v),add(tr[rt].son2 ,mid+1,r,mid+1,qr,v);
updata(rt);
}
void mul(int rt,int l,int r,int ql,int qr,int v)
{
if(ql<=l && r<=qr)
{
tr[rt].sum =(tr[rt].sum *v)%mod;
tr[rt].laz =(tr[rt].laz *v)%mod;
tr[rt].LAZ =(tr[rt].LAZ *v)%mod;
return ;
}
push_down(rt);
int mid=(l+r)>>1;
if(qr<=mid) mul(tr[rt].son1 ,l,mid,ql,qr,v);
else if(ql>mid) mul(tr[rt].son2 ,mid+1,r,ql,qr,v);
else mul(tr[rt].son1 ,l,mid,ql,qr,v),mul(tr[rt].son2 ,mid+1,r,ql,qr,v);
updata(rt);
}
int query(int rt,int l,int r,int ql,int qr)
{
if(ql<=l && r<=qr)
return tr[rt].sum ;
push_down(rt);
int mid=(l+r)>>1;
if(qr<=mid) return query(tr[rt].son1 ,l,mid,ql,qr);
else if(ql>mid) return query(tr[rt].son2 ,mid+1,r,ql,qr);
else return (query(tr[rt].son1 ,l,mid,ql,mid)+query(tr[rt].son2 ,mid+1,r,mid+1,qr))%mod;
}
signed main()
{
scanf("%lld%lld%lld",&n,&m,&mod);
for(int i=1;i<=n;i++)
scanf("%lld",&d[i]);
build(root,1,n);
int op,x,y,k;
for(int i=1;i<=m;i++)
{
scanf("%lld%lld%lld",&op,&x,&y);
if(op==3)
printf("%lld
",query(1,1,n,x,y));
else if(op==1)
scanf("%lld",&k),mul(1,1,n,x,y,k%mod);
else if(op==2)
scanf("%lld",&k),add(1,1,n,x,y,k%mod);
}
return 0;
}