脚本宝典收集整理的这篇文章主要介绍了(线段树) P4588 数学计算,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
小豆现在有一个数 x,初始值为 1。小豆有 QQ 次操作,操作有两种类型:
1 m
:将 x变为 x × m,并输出 x mod M
2 pos
:将 x 变为 x 除以第 pos次操作所乘的数(保证第 pos 次操作一定为类型 1,对于每一个类型 1 的操作至多会被除一次),并输出 x mod M。
第一眼真的看不出来是个线段树的题,仔细思考看题解后才明白思路,以时间为轴,创建以每次操作次数为叶子节点的线段树,每次操作只需更改叶子
节点的值,最终pushup上去后,tr[1]就是我们要找的x的值
1 # include<iostream>
2 # include<algorithm>
3 # include<cstring>
4 # define int long long
5 # define endl "n"
6 using namespace std;
7 const int N = 1e5+10;
8 int n,m;
9 struct node{
10 int l,r;
11 int v;
12 }tr[4*N];
13
14 void pushup(int u){
15 tr[u].v =( tr[u<<1|1].v*tr[u<<1].v)%m;/*向上更新父节点的值*/
16 }
17
18 void build(int u,int l,int r){
19 tr[u].l = l,tr[u].r = r;
20 if(l == r){
21 tr[u].v = 1;/*初始化所有操作值初始为 1 */
22 return;
23 }
24 int mid = l+r>>1;
25 build(u<<1,l,mid),build(u<<1|1,mid+1,r);
26 pushup(u);
27 }
28
29 void modify(int u,int x,int v){
30 if(tr[u].l == x && tr[u].r == x){
31 tr[u].v = (tr[u].v*v)%m;
32 return;
33 }
34 int mid = tr[u].l+tr[u].r>>1;
35 if(x<=mid) modify(u<<1,x,v);
36 else modify(u<<1|1,x,v);
37 pushup(u);
38 }
39
40 void remodify(int u,int x){
41 if(tr[u].l == x && tr[u].r == x){
42 tr[u].v = 1;
43 return;
44 }
45 int mid = tr[u].l+tr[u].r>>1;
46 if(x<=mid) remodify(u<<1,x);
47 else remodify(u<<1|1,x);
48 pushup(u);
49 }
50
51
52 int tt;
53 void solve(){
54 cin>>n>>m;
55 // memset(tr,0,sizeof tr);
56 build(1,1,n);
57 int kk = 0;/*记录一下操作次数*/
58 while(n--){
59 int op,v;
60 cin>>op>>v;
61 kk++;
62 if(op == 1){
63 modify(1,kk,v);
64 cout<<(tr[1].v)%m<<endl;
65 }
66 else{
67 remodify(1,v);
68 cout<<(tr[1].v)%m<<endl;
69 }
70 }
71
72 }
73 signed main(){
74 ios::sync_with_stdio(false);
75 cin.tie(0);
76 cout.tie(0);
77 cin>>tt;
78 while(tt--) solve();
79
80 return 0;
81 }
在乘的时候有可能爆int,所以要边乘边取模,开long long
以上是脚本宝典为你收集整理的(线段树) P4588 数学计算全部内容,希望文章能够帮你解决(线段树) P4588 数学计算所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。