【题解】「AHOI2009」维护序列（线段树）

本文主要是介绍【题解】「AHOI2009」维护序列（线段树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题面

【题目描述】
老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。 有长为$N$的数列，不妨设为$a_1,a_2,\dots ,a_N$。有如下三种操作形式：
$(1)$把数列中的一段数全部乘一个值;
$(2)$把数列中的一段数全部加一个值;
$(3)$询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模$P$的值。
【输入】
第一行两个整数$N$和$P(1\le P\le 1000000000）$。
第二行含有$N$个非负整数,从左到右依次为$a_1,a_2,\dots ,a_N,(0\le a_i\le 1000000000,1\le i\le N)$。
第三行有一个整数$M$，表示操作总数。
从第四行开始每行描述一个操作，输入的操作有以下三种形式：
操作1：“1 t g c”(不含双引号)。表示把所有满足$t\le i\le g$的$a_i$改为$a_i\times c(1\le t\le g\le N,0\le c\le 1000000000)$。
操作2：“2 t g c”(不含双引号)。表示把所有满足$t\le i\le g$的$a_i$改为$a_i+c(1\le t\le g\le N,0\le c\le 1000000000)$。
操作3：“3 t g”(不含双引号)。询问所有满足$t\le i\le g$的$a_i$的和模P的值$(1\le t\le g\le N)$。
同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。
【输出】
对每个操作$3$，按照它在输入中出现的顺序，依次输出一行一个整数表示询问结果。
【样例输入】

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

【样例输出】

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

算法分析

线段树模板题
区间操作只有加法，我们可以使用$lazy$标记区间，例如：【题解】「POJ3468」A Simple Problem with Integers（线段树）
如果存在两种区间操作，怎么办呢？可以用同样的方法，进行lazy标记，使用两个lazy标记即可。
但是，现在有一个问题，如果线段树第$k$个结点，乘法标记$lazy[k]=s$，加法标记$lazy2[k]=t$，如果要计算第$k$个结点的区间值怎么计算呢？先计算乘法，还是先计算加法呢？顺序不一样，结果就不一样。

在这里先计算乘法，再计算加法：
第$k$个结点，乘法标记$lazy[k]=s$，加法标记$lazy2[k]=t$，现在要对第$k$个结点的区间整体乘以$T$，那么可以这样更新标记：
lazy[k]=s*T;
lazy2[k]=t*T;
计算第k个结点区间值时先计算乘法，再计算加法就不会出现错误，因为加数已经提前乘以了$T$。
如果现在要对第k个结点的区间整体加上$P$，那么只需要更新：
lazy2[k]=t+P;
因为加法对乘法是没有影响的。

解决加法和乘法操作，使用两个$lazy$标记，对于乘法，需要同时更新乘法标记和加法标记，对于加法，只需要更新加法标记，计算时，先计算乘法，再计算加法，因为加数提前计算了乘法。

参考程序

#include<bits/stdc++.h>
#define N 100100
using namespace std;
long long s[4*N],lazy[4*N],lazy2[4*N];//s[]表示区间和，lazy[]标记乘法，lazy[]标记加法 
int n,m,M;
void built(int k,int l,int r)
{lazy[k]=1;				//乘法标记默认为1 lazy2[k]=0;if(l==r){scanf("%lld",&s[k]);return;}int mid=(l+r)/2;built(2*k,l,mid);built(2*k+1,mid+1,r);s[k]=s[2*k]+s[2*k+1];
}
void pushdown(int k,int l,int r)
{//先计算乘法，乘法对加法的影响已经处理一次了if(lazy[k]!=1){//左孩子s[2*k]=(s[2*k]*lazy[k])%M;lazy[2*k]=(lazy[2*k]*lazy[k])%M;lazy2[2*k]=(lazy2[2*k]*lazy[k])%M;	//更新乘法对加法的影响 //右孩子 s[2*k+1]=(s[2*k+1]*lazy[k])%M;lazy[2*k+1]=(lazy[2*k+1]*lazy[k])%M;lazy2[2*k+1]=(lazy2[2*k+1]*lazy[k])%M;	//更新乘法对加法的影响//自己清1lazy[k]=1;}	int mid=(l+r)/2;if(lazy2[k]!=0){//左孩子s[2*k]=(s[2*k]+(mid-l+1)*lazy2[k])%M;lazy2[2*k]=(lazy2[2*k]+lazy2[k])%M;//右孩子 s[2*k+1]=(s[2*k+1]+(r-mid)*lazy2[k])%M;lazy2[2*k+1]=(lazy2[2*k+1]+lazy2[k])%M;//自己清0lazy2[k]=0;}return;
} 
void update(int k,int l,int r,int x,int y,int t1,int t2)	//区间修改，加上t1，乘以t2
{if(l>y||r<x) return;if(x<=l&&r<=y){if(t1>=0) 	//区间加法 {s[k]=((s[k]%M)+(r-l+1)*(t1%M))%M;lazy2[k]+=t1;} else		//区间乘法{s[k]=((s[k]%M)*(t2%M))%M;lazy[k]=(lazy[k]*t2)%M;lazy2[k]=(lazy2[k]*t2)%M;		//乘法对加法有影响，相当于加数*t2 }return; }pushdown(k,l,r);			//如果有标记，先更新 int mid=(l+r)/2;update(2*k,l,mid,x,y,t1,t2);update(2*k+1,mid+1,r,x,y,t1,t2);s[k]=((s[2*k]%M)+(s[2*k+1]%M))%M;		//回溯更新区间和 
} 
long long ask(int k,int l,int r,int x,int y)
{if(y<l||x>r) return 0;if(x<=l&&r<=y) return s[k];pushdown(k,l,r);			//未更新的先更新 int mid=(l+r)/2;return (ask(2*k,l,mid,x,y)+ask(2*k+1,mid+1,r,x,y))%M;
}
int main()
{scanf("%d%d",&n,&M);built(1,1,n);int k,t,g;long long c;scanf("%d",&m);while(m--){scanf("%d",&k);if(k==1) 			//区间乘 {scanf("%d%d%lld",&t,&g,&c);update(1,1,n,t,g,-1,c);	}if(k==2)			//区间加 {scanf("%d%d%lld",&t,&g,&c);update(1,1,n,t,g,c,1);}if(k==3){scanf("%d%d",&t,&g);printf("%lld\n",ask(1,1,n,t,g)); }}return 0;
} 

这篇关于【题解】「AHOI2009」维护序列（线段树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---