【学习笔记】带区间乘的线段树([AHOI2009]维护序列 题解)
点击量:467
这个题是好久的坑了,一直不知道怎么填,后来发现把层次搞清楚了就OK了。先贴题面
题目描述
老师交给小可可一个维护数列的任务,现在小可可希望你来帮他完成。
有长为\(N\)的数列,不妨设为\(a_1,a_2,\dots ,a_N\)。有如下三种操作形式:
(1)把数列中的一段数全部乘一个值;
(2)把数列中的一段数全部加一个值;
(3)询问数列中的一段数的和,由于答案可能很大,你只需输出这个数模\(P\)的值。
输入输出格式
输入格式:
第一行两个整数\(N\)和\(P(1≤P≤1000000000)\)。
第二行含有\(N\)个非负整数,从左到右依次为\(a_1,a_2,\dots,a_N,(0≤a_i≤1000000000,1≤i≤N)\)。
第三行有一个整数\(M\),表示操作总数。
从第四行开始每行描述一个操作,输入的操作有以下三种形式:
操作1:“1 t g c”(不含双引号)。表示把所有满足\(t≤i≤g\)的\(a_i\)改为\(a_i\times c (1≤t≤g≤N,0≤c≤1000000000)\)。
操作2:“2 t g c”(不含双引号)。表示把所有满足\(t≤i≤g\)的\(a_i\)改为\(a_i+c (1≤t≤g≤N,0≤c≤1000000000)\)。
操作3:“3 t g”(不含双引号)。询问所有满足\(t≤i≤g\)的\(a_i\)的和模\(P\)的值\((1≤t≤g≤N)\)。 同一行相邻两数之间用一个空格隔开,每行开头和末尾没有多余空格。
输出格式:
对每个操作3,按照它在输入中出现的顺序,依次输出一行一个整数表示询问结果。
输入输出样例
输入样例#1:7 43 1 2 3 4 5 6 7 5 1 2 5 5 3 2 4 2 3 7 9 3 1 3 3 4 7输出样例#1:2 35 8说明
【样例说明】
初始时数列为(1,2,3,4,5,6,7)。
经过第1次操作后,数列为(1,10,15,20,25,6,7)。
对第2次操作,和为10+15+20=45,模43的结果是2。
经过第3次操作后,数列为(1,10,24,29,34,15,16}
对第4次操作,和为1+10+24=35,模43的结果是35。
对第5次操作,和为29+34+15+16=94,模43的结果是8。
测试数据规模如下表所示
数据编号 1 2 3 4 5 6 7 8 9 10 N 10 1000 1000 10000 60000 70000 80000 90000 100000 100000 M 10 1000 1000 10000 60000 70000 80000 90000 100000 100000
题解/做法:
这题和普通的线段树不一样的地方在于,它需要支持区间乘操作。因为加法和乘法存在先后顺序的差异,所以懒标记不能直接维护两个。
但是在线段树中,如果要对区间做乘法,那么就要知道它的确切值是多少,可以在每次加法和乘法冲突时都先下传一次。但是这样多次下传懒标记对常数会有很大的影响,我们可以试图换一种方式思考:如何不下传懒标记就完成区间乘呢?
假设我们线段树中一个节点的信息为\(t[k].v,t[k].lazy\),它的实际权值是\(t[k].v+t[k].lazy\times (r-l+1)\)。如果要修改的区间覆盖满了\(t[k]\)的\(l\sim r\),就可以认为新权值是\((t[k].v+t[k].lazy\times (r-l+1))\times x\)。看来我们只需要把\(v\times x\),和\(lazytag\times x\)即可。
不过这时我们可以对乘法和加法维护两个懒标记,只要保证它们是先执行乘法再执行加法就可以了。每次下传也要注意这一点。
Code:
#include<cstdio>
#include<cstring>
#define ls (k<<1)
#define rs (k<<1|1)
#define mid (l+r>>1)
#define Mid (t[k].l+t[k].r>>1)
struct node
{
int l,r;
long long ad,mu,v;
node(int l,int r)
{
this->l=l;
this->r=r;
ad=0,mu=1;
v=0;
}
node()
{
ad=0,mu=1;
v=0;
}
}t[400000];
long long a[100100],p;
void build(int k,int l,int r)
{
t[k]=node(l,r);
if(l==r)
{
t[k].v=a[l];
return;
}
build(ls,l,mid);
build(rs,mid+1,r);
t[k].v=(t[ls].v+t[rs].v)%p;
return;
}
void pushdown(int k)
{
if(t[k].l==t[k].r||(t[k].ad==0&&t[k].mu==1))
return;
long long x=t[k].ad;
long long y=t[k].mu;
t[k].ad=0;
t[k].mu=1;
t[ls].v=t[ls].v*y%p;
t[ls].mu=t[ls].mu*y%p;
t[ls].ad=t[ls].ad*y%p;
t[ls].v=(t[ls].v+(t[ls].r-t[ls].l+1)*x)%p;
t[ls].ad=(t[ls].ad+x)%p;
t[rs].v=t[rs].v*y%p;
t[rs].mu=t[rs].mu*y%p;
t[rs].ad=t[rs].ad*y%p;
t[rs].v=(t[rs].v+(t[rs].r-t[rs].l+1)*x)%p;
t[rs].ad=(t[rs].ad+x)%p;
return;
}
void mul(int k,int l,int r,int x)
{
if(t[k].l==l&&t[k].r==r)
{
t[k].v=t[k].v*x%p;
t[k].ad=t[k].ad*x%p;
t[k].mu=t[k].mu*x%p;
return;
}
pushdown(k);
if(r<=Mid)
mul(ls,l,r,x);
else if(l>Mid)
mul(rs,l,r,x);
else
{
mul(ls,l,Mid,x);
mul(rs,Mid+1,r,x);
}
t[k].v=(t[ls].v+t[rs].v)%p;
}
void add(int k,int l,int r,long long x)
{
t[k].v=(t[k].v+x*(r-l+1))%p;
if(t[k].l==l&&t[k].r==r)
{
t[k].ad=(t[k].ad+x)%p;
return;
}
pushdown(k);
if(r<=Mid)
return add(ls,l,r,x);
else if(l>Mid)
return add(rs,l,r,x);
add(ls,l,Mid,x);
return add(rs,Mid+1,r,x);
}
long long ask(int k,int l,int r)
{
if(t[k].l==l&&t[k].r==r)
return t[k].v;
pushdown(k);
if(r<=Mid)
return ask(ls,l,r);
if(l>Mid)
return ask(rs,l,r);
else
return (ask(ls,l,Mid)+ask(rs,Mid+1,r))%p;
}
int main()
{
int n,m,op,x,y;
long long z;
scanf("%d%lld",&n,&p);
for(int i=1;i<=n;++i)
scanf("%lld",&a[i]);
build(1,1,n);
scanf("%d",&m);
for(int i=1;i<=m;++i)
{
scanf("%d",&op);
if(op==2)
{
scanf("%d%d%lld",&x,&y,&z);
add(1,x,y,z);
}
else if(op==1)
{
scanf("%d%d%lld",&x,&y,&z);
mul(1,x,y,z);
}
else
{
scanf("%d%d",&x,&y);
printf("%lld\n",ask(1,x,y));
}
}
return 0;
}
说点什么