2020算法设计竞赛

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 const int mod=1e9+7;
 5 const int N=2e5+5;
 6 ll K[N],B[N],k[N<<2],b[N<<2];
 7 int n,m;
 8 ll _k,_b;
 9 ll ans;
10 void query(int p,int l,int r,int L,int R){
11     if(L>=l&&R<=r){
12         ans=(ans*k[p]%mod+b[p])%mod;
13         return;
14     }
15     int mid=(L+R)>>1;
16     if(l<=mid) query(2*p,l,r,L,mid);
17     if(r>mid) query(2*p+1,l,r,mid+1,R);
18 }
19 void build(int p,int L,int R)
20 {
21     if(L==R){
22         k[p]=K[L],b[p]=B[L];
23         return;
24     }
25     int mid=(L+R)>>1;
26     build(2*p,L,mid);
27     build(2*p+1,mid+1,R);
28     k[p]=k[2*p]*k[2*p+1]%mod;
29     b[p]=((b[2*p]*k[2*p+1]%mod+b[2*p+1])%mod);
30 }
31 void change(int p,int x,int L,int R){
32     if(L==R){
33         k[p]=_k;
34         b[p]=_b;
35         return;
36     }
37     int mid=(L+R)>>1;
38     if(x<=mid) change(2*p,x,L,mid);
39     else change(2*p+1,x,mid+1,R);
40     k[p]=k[2*p]*k[2*p+1]%mod;
41     b[p]=((b[2*p]*k[2*p+1]%mod+b[2*p+1])%mod);
42      
43 }
44 int main()
45 {
46     int op,x;
47     scanf("%d%d",&n,&m);
48     for(int i=1;i<=n;i++) scanf("%lld",&K[i]);
49     for(int i=1;i<=n;i++) scanf("%lld",&B[i]);
50     build(1,1,n);
51     for(int i=1;i<=m;i++){
52         scanf("%d",&op);
53         if(op==1){
54             scanf("%d%lld%lld",&x,&_k,&_b);
55             change(1,x,1,n);
56         }
57         else{
58             int l,r;
59             scanf("%d%d",&l,&r);
60             ans=1;
61             query(1,l,r,1,n);
62             printf("%lld\n",ans%mod);
63         }
64     }
65 }