BZOJ 5039: [Jsoi2014]序列维护 线段树

5039: [Jsoi2014]序列维护

Time Limit: 20 Sec  Memory Limit: 256 MB Submit: 56  Solved: 39 [Submit][Status][Discuss]

Description

JYY 有一个维护数列的任务。 他希望你能够来帮助他完成。 JYY 现在有一个长度为 N 的序列 a1,a2,…,aN，有如下三种操作： 1、 把数列中的一段数全部乘以一个值； 2、 把数列中的一段数全部加上一个值； 3、 询问序列中的一段数的和。 由于答案可能很大，对于每个询问，你只需要告诉 JYY 这个询问的答案对 P 取模的结果即可。

Input

第一行包含两个正整数， N 和 P； 第二行包含 N 个非负整数，从左到右依次为 a1,a2,…,aN。 第三行有一个整数 M，表示操作总数。 接下来 M 行，每行满足如下三种形式之一： 1、“ 1 t g c”（不含引号）。表示把所有满足 t ≤ i ≤ g 的 ai 全部乘以 c； 2、“ 2 t g c”（不含引号）。表示把所有满足 t ≤ i ≤ g 的 ai 全部加上 c； 3、“ 3 t g”（不含引号）。表示询问满足 t ≤ i ≤ g 的 ai 的和对 P 取模的值。 1 ≤ N,M ≤ 10^5， 1 ≤ P, c, ai ≤ 2*10^9， 1 ≤ t ≤ g ≤ N

Output

对于每个以 3 开头的操作，依次输出一行，包含对应的结果。

Sample Input

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

Sample Output

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。

需要维护乘法的线段树

由于运算的优先级关系

必须保证在进行加法前，所有的乘法都进行完毕

所以

修改/pushdown时

先把乘法的lazy标记传给所有维护的值

最后把加法的lazy标记下传

#include<cmath> #include<ctime> #include<cstdio> #include<cstring> #include<cstdlib> #include<complex> #include<iostream> #include<algorithm> #include<iomanip> #include<vector> #include<string> #include<bitset> #include<queue> #include<map> #include<set> using namespace std; typedef long long ll; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f; } void print(ll x) {if(x<0)putchar('-'),x=-x;if(x>=10)print(x/10);putchar(x+'0');} const int N=100100; int n,mod,a[N]; struct seg_tree{ll p,m,sum;}tr[N<<2]; inline void pushup(int k) {tr[k].sum=(tr[k<<1].sum+tr[k<<1|1].sum)%mod;} inline void pushdown(int l,int r,int k) { int mid=(l+r)>>1; (tr[k<<1].sum*=tr[k].m)%=mod; (tr[k<<1|1].sum*=tr[k].m)%=mod; (tr[k<<1].sum+=tr[k].p*(mid-l+1))%=mod; (tr[k<<1|1].sum+=tr[k].p*(r-mid))%=mod; (tr[k<<1].m*=tr[k].m)%=mod; (tr[k<<1|1].m*=tr[k].m)%=mod; (tr[k<<1].p*=tr[k].m)%=mod; (tr[k<<1|1].p*=tr[k].m)%=mod; (tr[k<<1].p+=tr[k].p)%=mod; (tr[k<<1|1].p+=tr[k].p)%=mod; tr[k].p=0,tr[k].m=1; } void build(int k,int l,int r) { tr[k].m=1; if(l==r){tr[k].sum=a[l]%mod;return ;} int mid=(l+r)>>1; build(k<<1,l,mid);build(k<<1|1,mid+1,r); pushup(k); } void modify_p(int k,int l,int r,int x,int y,ll val) { if(l>=x&&r<=y) { (tr[k].sum+=(r-l+1)*val)%=mod;(tr[k].p+=val)%=mod; return ; } int mid=(l+r)>>1;pushdown(l,r,k); if(x<=mid)modify_p(k<<1,l,mid,x,y,val); if(y>mid)modify_p(k<<1|1,mid+1,r,x,y,val); pushup(k); } void modify_m(int k,int l,int r,int x,int y,ll val) { if(l>=x&&r<=y) { (tr[k].sum*=val)%=mod;(tr[k].m*=val)%=mod;(tr[k].p*=val)%=mod; return ; } int mid=(l+r)>>1;pushdown(l,r,k); if(x<=mid)modify_m(k<<1,l,mid,x,y,val); if(y>mid)modify_m(k<<1|1,mid+1,r,x,y,val); pushup(k); } ll query(int k,int l,int r,int x,int y) { if(l>=x&&r<=y){return tr[k].sum;} int mid=(l+r)>>1;pushdown(l,r,k); if(y<=mid)return query(k<<1,l,mid,x,y); else if(x>mid)return query(k<<1|1,mid+1,r,x,y); else return (query(k<<1|1,mid+1,r,x,y)+query(k<<1,l,mid,x,y))%mod; } int main() { n=read();mod=read(); register int i,l,r,val,opt; for(i=1;i<=n;++i)a[i]=read(); build(1,1,n); int Q=read(); while(Q--) { opt=read();l=read();r=read(); switch(opt) { case 1:val=read();modify_m(1,1,n,l,r,val);break; case 2:val=read();modify_p(1,1,n,l,r,val);break; case 3:print(query(1,1,n,l,r));puts("");break; default:break; } } return 0; } /* 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 */