题目地址：https://www.acwing.com/problem/content/description/1279/
题目描述：
老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。
有长为 N 的数列，不妨设为 a1,a2,…,aN。
有如下三种操作形式：
- 把数列中的一段数全部乘一个值；
- 把数列中的一段数全部加一个值；
- 询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模 PP 的值。
输入格式
第一行两个整数 N 和 P；
第二行含有 NN 个非负整数，从左到右依次为 a1,a2,…,aN；
第三行有一个整数 M，表示操作总数；
从第四行开始每行描述一个操作，输入的操作有以下三种形式：
- 操作 11：
1 t g c，表示把所有满足 t≤i≤g 的 ai 改为 ai×c； - 操作 22：
2 t g c，表示把所有满足 t≤i≤g 的 ai改为 ai+c； - 操作 33：
3 t g，询问所有满足 t≤i≤g 的 ai的和模 P的值。
同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。
输出格式
对每个操作 3，按照它在输入中出现的顺序，依次输出一行一个整数表示询问结果。
数据范围
1≤N,M≤1e5
1≤t≤g≤N,
0≤c,ai≤1e9,
1≤P≤1e9
题解：这是一道典型的线段树问题。但是这里对于区间修改涉及两个操作。我们可以使用一个巧妙的办法来解决。假设一个区间的懒标记：add=a，mult=b.那么又来一个add1,则该区间的变换为sum+=(tr[u].r-tr[u].l+1)*add1,add+=add1.如果来一个mult1,则该区间的变换为sum*=mult1,mult*=mult1,add*=mult1.
剩下的就可以利用线段树直接完成了。
AC代码：
#include<iostream> #include<cstdio> using namespace std; const int N=1e5+10; #define ll long long int ll n,m,p; struct node{ int l,r; ll sum,add,mult; }tr[4*N]; void pushup(int u){ tr[u].sum=(tr[u<<1].sum+tr[u<<1|1].sum)%p; } void build(int u,int l,int r){ tr[u].l=l,tr[u].r=r,tr[u].add=0,tr[u].mult=1; if(l==r){ scanf("%lld",&tr[u].sum); tr[u].sum%=p; return ; } int mid=l+r>>1; build(u<<1,l,mid); build(u<<1|1,mid+1,r); pushup(u); return ; } void pushnow(int u,ll add,ll mult){ tr[u].sum*=mult; tr[u].sum%=p; tr[u].sum+=add*(tr[u].r+1-tr[u].l); tr[u].sum%=p; tr[u].mult*=mult; tr[u].add*=mult; tr[u].add%=p; tr[u].add+=add; tr[u].mult%=p; tr[u].add%=p; } void pushdown(int u){ if(tr[u].add!=0||tr[u].mult!=1){ pushnow(u<<1,tr[u].add,tr[u].mult); pushnow(u<<1|1,tr[u].add,tr[u].mult); tr[u].add=0; tr[u].mult=1; } } void modify(int u,int l,int r,ll add,ll mult){ if(tr[u].l>=l&&tr[u].r<=r){ pushnow(u,add,mult); return ; } pushdown(u); int mid=tr[u].l+tr[u].r>>1; if(l<=mid) modify(u<<1,l,r,add,mult); if(r>mid) modify(u<<1|1,l,r,add,mult); pushup(u); return ; } ll query(int u,int l,int r){ if(tr[u].l>=l&&tr[u].r<=r) { return tr[u].sum%p; } int mid=tr[u].l+tr[u].r>>1; ll sum=0; pushdown(u); if(l<=mid) sum=query(u<<1,l,r); if(r>mid) sum+=query(u<<1|1,l,r); return sum%p; } int main(){ cin>>n>>p; build(1,1,n); cin>>m; ll k,l,r,c; while(m--){ scanf("%lld%lld%lld",&k,&l,&r); if(k==1){ scanf("%lld",&c); modify(1,l,r,0,c%p); } else if(k==2){ scanf("%lld",&c); modify(1,l,r,c%p,1); } else { cout<<query(1,l,r)<<endl; } } return 0; }
写于;202/8/29 22：08