[AHOI2009]维护序列————标准的线段树问题
老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。 有长为N的数列，不妨设为a1,a2,…,aN 。有如下三种操作形式：
(1)把数列中的一段数全部乘一个值;
(2)把数列中的一段数全部加一个值;
(3)询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模P的值。没有任何掩饰，看完题目，我们就知道这是一道线段树的题。
这道题要求处理区间加，乘即求和，这恰好符合线段树的维护特征。
所以，我们就可以建一颗线段树->
inline void build(int x,int l,int r)
{
tree[x].l=l;
tree[x].r=r;
tree[x].flag=1;
tree[x].tag=0;
if(tree[x].l==tree[x].r)
{
tree[x].tot=a[l];
tree[x].tot%=mods;
return ;
}
int mid=(l+r)>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
tree[x].tot=tree[x<<1].tot+tree[x<<1|1].tot;
tree[x].tot%=mods;
return ;
}由于线段树要处理区间内的加法乘法问题，根据数学知识，我们可以得知乘法对加法有影响，而加法对乘法没影响。so我们用flag作为乘法标记，初始值为1；tag做加法标记，初始值为0；
特别提醒，结构体数组范围一定至少是普通数组的四倍，即
struct node
{
int l;
int r;
int flag;
int tot;
int tag;
}
tree[4*p];
int a[p];否则只有50分。
然后是pushdown，注意乘法标记和加法标记的关系
inline void pushdown(int x,int l,int r)
{
int mid=(l+r)>>1;
tree[x<<1].tot=(tree[x<<1].tot*tree[x].flag+(mid-l+1)*tree[x].tag)%mods;
tree[x<<1|1].tot=(tree[x<<1|1].tot*tree[x].flag+(r-mid)*tree[x].tag)%mods;
tree[x<<1].flag=(tree[x<<1].flag*tree[x].flag)%mods;
tree[x<<1|1].flag=(tree[x<<1|1].flag*tree[x].flag)%mods;
tree[x<<1].tag=(tree[x<<1].tag*tree[x].flag+tree[x].tag)%mods;
tree[x<<1|1].tag=(tree[x<<1|1].tag*tree[x].flag+tree[x].tag)%mods;
tree[x].flag=1;
tree[x].tag=0;
}接下来就是区间修改了。
inline void tree_plus(int x,int l,int r,int ll,int rr,int y)
{
if(ll<=l&&rr>=r)
{
tree[x].tot=(tree[x].tot+y*(r-l+1))%mods;
tree[x].tag=(tree[x].tag+y)%mods;
return ;
}
if(ll>r||rr<l)
return ;
int mid=(r+l)>>1;
pushdown(x,l,r);
tree_plus(x<<1,l,mid,ll,rr,y);
tree_plus(x<<1|1,mid+1,r,ll,rr,y);
tree[x].tot=(tree[x<<1].tot+tree[x<<1|1].tot)%mods;
}
inline void tree_x(int x,int l,int r,int ll,int rr,int y)
{
if(ll<=l&&rr>=r)
{
tree[x].tot=(tree[x].tot*y)%mods;
tree[x].tag=(tree[x].tag*y)%mods;
tree[x].flag=(tree[x].flag*y)%mods;
return ;
}
if(ll>r||rr<l)
return ;
int mid=(r+l)>>1;
pushdown(x,l,r);
tree_x(x<<1,l,mid,ll,rr,y);
tree_x(x<<1|1,mid+1,r,ll,rr,y);
tree[x].tot=(tree[x<<1].tot+tree[x<<1|1].tot)%mods;
}注意，不仅要更新节点tot的值，还要更新tag和flag. 最后是求和->
inline int get_tot(int x,int l,int r,int ll,int rr)
{
int ts=0;
if(l>=ll&&r<=rr)
return tree[x].tot;
else
if(l>rr||r<ll)
return 0;
pushdown(x,l,r);
int mid=(l+r)>>1;
ts+=get_tot(x<<1,l,mid,ll,rr);
ts+=get_tot((x<<1)+1,mid+1,r,ll,rr);
return ts%mods;
}注意一步一%，不然很有可能丢分。
最后上完整代码：
#include<bits/stdc++.h>
#define p 234232
#define h 5001
#define int long long
#define fint register int
using namespace std;
struct node
{
int l;
int r;
int flag;
int tot;
int tag;
}
tree[4*p];
int a[p];
int n,m;
int mods;
inline int read();
inline void build(int x,int l,int r);
inline void pushdown(int x,int l,int r);
inline void tree_plus(int x,int l,int r,int ll,int rr,int y);
inline void tree_x(int x,int l,int r,int ll,int rr,int y);
inline int get_tot(int x,int l,int r,int ll,int rr);
inline void pre();
inline void ask();
signed main()
{
pre();
build(1,1,n);
ask();
return 0;
}
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
inline void build(int x,int l,int r)
{
tree[x].l=l;
tree[x].r=r;
tree[x].flag=1;
tree[x].tag=0;
if(tree[x].l==tree[x].r)
{
tree[x].tot=a[l];
tree[x].tot%=mods;
return ;
}
int mid=(l+r)>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
tree[x].tot=tree[x<<1].tot+tree[x<<1|1].tot;
tree[x].tot%=mods;
return ;
}
inline void pushdown(int x,int l,int r)
{
int mid=(l+r)>>1;
tree[x<<1].tot=(tree[x<<1].tot*tree[x].flag+(mid-l+1)*tree[x].tag)%mods;
tree[x<<1|1].tot=(tree[x<<1|1].tot*tree[x].flag+(r-mid)*tree[x].tag)%mods;
tree[x<<1].flag=(tree[x<<1].flag*tree[x].flag)%mods;
tree[x<<1|1].flag=(tree[x<<1|1].flag*tree[x].flag)%mods;
tree[x<<1].tag=(tree[x<<1].tag*tree[x].flag+tree[x].tag)%mods;
tree[x<<1|1].tag=(tree[x<<1|1].tag*tree[x].flag+tree[x].tag)%mods;
tree[x].flag=1;
tree[x].tag=0;
}
inline void tree_plus(int x,int l,int r,int ll,int rr,int y)
{
if(ll<=l&&rr>=r)
{
tree[x].tot=(tree[x].tot+y*(r-l+1))%mods;
tree[x].tag=(tree[x].tag+y)%mods;
return ;
}
if(ll>r||rr<l)
return ;
int mid=(r+l)>>1;
pushdown(x,l,r);
tree_plus(x<<1,l,mid,ll,rr,y);
tree_plus(x<<1|1,mid+1,r,ll,rr,y);
tree[x].tot=(tree[x<<1].tot+tree[x<<1|1].tot)%mods;
}
inline void tree_x(int x,int l,int r,int ll,int rr,int y)
{
if(ll<=l&&rr>=r)
{
tree[x].tot=(tree[x].tot*y)%mods;
tree[x].tag=(tree[x].tag*y)%mods;
tree[x].flag=(tree[x].flag*y)%mods;
return ;
}
if(ll>r||rr<l)
return ;
int mid=(r+l)>>1;
pushdown(x,l,r);
tree_x(x<<1,l,mid,ll,rr,y);
tree_x(x<<1|1,mid+1,r,ll,rr,y);
tree[x].tot=(tree[x<<1].tot+tree[x<<1|1].tot)%mods;
}
inline int get_tot(int x,int l,int r,int ll,int rr)
{
int ts=0;
if(l>=ll&&r<=rr)
return tree[x].tot;
else
if(l>rr||r<ll)
return 0;
pushdown(x,l,r);
int mid=(l+r)>>1;
ts+=get_tot(x<<1,l,mid,ll,rr);
ts+=get_tot((x<<1)+1,mid+1,r,ll,rr);
return ts%mods;
}
inline void pre()
{
n=read();
mods=read();
for(fint i=1;i<=n;i++)
a[i]=read();
m=read();
build(1,1,n);
return ;
}
inline void ask()
{
int num,t,g,c;
for(fint i=1;i<=m;i++)
{
num=read();
if(num==1)
t=read(),g=read(),c=read(),tree_x(1,1,n,t,g,c);
else
if(num==2)
t=read(),g=read(),c=read(),tree_plus(1,1,n,t,g,c);
else
if(num==3)
t=read(),g=read(),cout<<get_tot(1,1,n,t,g)%mods<<endl;
}
return ;
}最后的最后，推荐大家几道可以迅速了解线段树的题目 P3372 P3373 P1816
如果想细致的学习基础的线段树，可以点我
祝大家ac愉快