LOJ10129
2024-10-19 06:22:25
AHOI 2009
老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。
有长为 nn 的数列，不妨设为 a1,a2,⋯,an。有如下三种操作形式：
- 把数列中的一段数全部乘一个值；
- 把数列中的一段数全部加一个值；
- 询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模 P 的值。
输入格式
第一行两个整数 n 和 P；
第二行含有 n 个非负整数，从左到右依次为 a1,a2,⋯,an；
第三行有一个整数 M，表示操作总数；
从第四行开始每行描述一个操作，输入的操作有以下三种形式：
- 操作 1：
1 t g c，表示把所有满足t≤i≤g 的 a_iai 改为ai×c； - 操作 2：
2 t g c，表示把所有满足t≤i≤g 的 a_iai 改为 ai+c； - 操作 3：
3 t g，询问所有满足 t≤i≤g 的 a_iai 的和模 P 的值。
同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。
输出格式
对每个操作 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≤t≤g≤n,0≤c,ai≤10^9,1≤P≤10^9。
测试数据规模如下表所示：n,m<=1e5
______________________________________________________________
线段树维护两个懒惰标记，增加值和乘积
______________________________________________________________
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 const int maxn=1e5+10;
5 ll n,m,p;
6 ll sum[maxn<<2],dels[maxn<<2],delp[maxn<<2];
7 ll a[maxn];
8 void down(ll cur,ll l,ll r)
9 {
10 if(delp[cur]!=1)
11 {
12 sum[cur<<1]=(sum[cur<<1]*delp[cur])%p;
13 sum[cur<<1|1]=(sum[cur<<1|1]*delp[cur])%p;
14 delp[cur<<1]=(delp[cur<<1]*delp[cur])%p;
15 delp[cur<<1|1]=(delp[cur<<1|1]*delp[cur])%p;
16 dels[cur<<1]=(dels[cur<<1]*delp[cur])%p;
17 dels[cur<<1|1]=(dels[cur<<1|1]*delp[cur])%p;
18 delp[cur]=1;
19 }
20 if(dels[cur])
21 {
22 ll mid=(l+r)>>1;
23 sum[cur<<1]=(sum[cur<<1]+dels[cur]*(mid-l+1))%p;
24 sum[cur<<1|1]=(sum[cur<<1|1]+dels[cur]*(r-mid))%p;
25 dels[cur<<1]=(dels[cur<<1]+dels[cur])%p;
26 dels[cur<<1|1]=(dels[cur<<1|1]+dels[cur])%p;
27 dels[cur]=0;
28 }
29 }
30 void build(ll cur,ll l,ll r)
31 {
32 if(l==r)
33 {
34 sum[cur]=a[l]%p;
35 delp[cur]=1;
36 return ;
37 }
38 ll mid=(l+r)>>1;
39 build(cur<<1,l,mid);
40 build(cur<<1|1,mid+1,r);
41 sum[cur]=(sum[cur<<1]+sum[cur<<1|1])%p;
42 delp[cur]=1;
43 }
44 void change1(ll cur,ll l,ll r,ll ql,ll qr,ll x)
45 {
46 if(ql<=l && r<=qr)
47 {
48 sum[cur]=(sum[cur]*x)%p;
49 delp[cur]=(delp[cur]*x)%p;
50 dels[cur]=(dels[cur]*x)%p;
51 return ;
52 }
53 if(dels[cur] || delp[cur]!=1)down(cur,l,r);
54 ll mid=(l+r)>>1;
55 if(ql<=mid)change1(cur<<1,l,mid,ql,qr,x);
56 if(mid<qr)change1(cur<<1|1,mid+1,r,ql,qr,x);
57 sum[cur]=(sum[cur<<1]+sum[cur<<1|1])%p;
58 }
59 void change2(ll cur,ll l,ll r,ll ql,ll qr,ll x)
60 {
61 if(ql<=l && r<=qr)
62 {
63 sum[cur]=(sum[cur]+x*(r-l+1))%p;
64 dels[cur]=dels[cur]+x>=p?dels[cur]+x-p:dels[cur]+x;
65 return ;
66 }
67 if(dels[cur] || delp[cur]!=1)down(cur,l,r);
68 ll mid=(l+r)>>1;
69 if(ql<=mid)change2(cur<<1,l,mid,ql,qr,x);
70 if(mid<qr)change2(cur<<1|1,mid+1,r,ql,qr,x);
71 sum[cur]=(sum[cur<<1]+sum[cur<<1|1])%p;
72 }
73 ll query(ll cur,ll l,ll r,ll ql,ll qr)
74 {
75 if(ql<=l && r<=qr)return sum[cur];
76 if(dels[cur] || delp[cur]!=1)down(cur,l,r);
77 ll ans=0;
78 ll mid=(l+r)>>1;
79 if(ql<=mid)ans+=query(cur<<1,l,mid,ql,qr);
80 if(mid<qr)ans+=query(cur<<1|1,mid+1,r,ql,qr);
81 return ans%p;
82 }
83 int main()
84 {
85 scanf("%lld%lld",&n,&p);
86 for(int i=1;i<=n;++i)scanf("%lld",a+i);
87 build(1,1,n);
88 scanf("%lld",&m);
89 while(m--)
90 {
91 ll op,l,r,x;
92 scanf("%lld",&op);
93 if(op==1)
94 {
95 scanf("%lld%lld%lld",&l,&r,&x);
96 x%=p;
97 change1(1,1,n,l,r,x);
98 }
99 else if(op==2)
100 {
101 scanf("%lld%lld%lld",&l,&r,&x);x%=p;
102 change2(1,1,n,l,r,x);
103 }
104 else
105 {
106 scanf("%lld%lld",&l,&r);
107 cout<<query(1,1,n,l,r)%p<<endl;
108 }
109 }
110 return 0;
111 }
最新文章
- js中的文本编辑器控件KindEditor---那些打酱油的日子
- Linux-终端-快捷键
- NSSM - windows 服务安装工具
- CSS 自定义字体
- 第一个 Asp.Net vNext 应用程序
- iOS阶段学习第29天笔记(UITextField的介绍)
- 转：Web页面通过URL地址传递参数常见问题及检测方法
- C# 十进制与十六进制互转
- 使用开源工具MonoDevelop开发GTK#图形界面
- landsat8简介
- js中的时间转换—毫秒转换成日期时间
- C++类构造函数
- linux配置ssh+rsync
- sys.argv向脚本中传递参数
- Java集合源码分析（三）Vevtor和Stack
- 字符串匹配(一)----Rabin-Karp算法
- Python学习计划
- SpringBoot实现跨域
- cardlayout
- Java collection 容器