#6283.数列ブロック入門7(区間乗算、区間加算、単点問合せ)
13336 ワード
タイトルリンク:https://loj.ac/problem/6283
中国語のテーマ
具体的な考え方:セグメントツリーの考え方と同じようにlazyの下放に注意し、不完全な区間については、配列aの値を更新してから配列aを操作する必要があります.完全な操作については、優先度に注意し、元がa*b+cであれば、この区間にeを乗じると、a*(b*e)+c*eと表示されます.
ACコード:
転載先:https://www.cnblogs.com/letlifestop/p/10472364.html
中国語のテーマ
具体的な考え方:セグメントツリーの考え方と同じようにlazyの下放に注意し、不完全な区間については、配列aの値を更新してから配列aを操作する必要があります.完全な操作については、優先度に注意し、元がa*b+cであれば、この区間にeを乗じると、a*(b*e)+c*eと表示されます.
ACコード:
1 #include
2 using namespace std;
3 # define ll long long
4 const int maxn = 2e6+100;
5 const int inf = 0x3f3f3f3f;
6 const int mod = 1e4+7;
7 ll l[maxn],r[maxn],belong[maxn];
8 ll add[maxn],a[maxn],sum[maxn],mul[maxn];
9 int n;
10 void buildblock()
11 {
12 ll tmp=(ll)sqrt(n);
13 ll tot=n/tmp;
14 if(n%tmp)
15 tot++;
16 for(ll i=1; i<=n; i++)
17 {
18 belong[i]=(i-1)/tmp+1ll;
19 }
20 for(ll i=1; i<=tot; i++)
21 {
22 l[i]=(i-1)*tmp+1ll;
23 r[i]=i*tmp;
24 }
25 r[tot]=n;
26 }
27 void down(int pos)
28 {
29 for(int i=l[pos]; i<=r[pos]; i++)
30 {
31 a[i]=(a[i]*mul[pos]+add[pos]+mod)%mod;
32 }
33 mul[pos]=1;
34 add[pos]=0;
35 }
36 void update1(ll st,ll ed,ll val)
37 {
38 if(belong[st]==belong[ed])
39 {
40 down(belong[st]);
41 for(ll i=st; i<=ed; i++)
42 a[i]+=val,a[i]%=mod;
43 return ;
44 }
45 down(belong[st]);
46 for(ll i=st; i<=r[belong[st]]; i++)
47 a[i]+=val,a[i]%=mod;
48 down(belong[ed]);
49 for(ll i=l[belong[ed]]; i<=ed; i++)
50 a[i]+=val,a[i]%=mod;
51 for(ll i=belong[st]+1; i)
52 add[i]+=val,add[i]%=mod;
53 }
54 void update2(ll st,ll ed,ll val)
55 {
56 if(belong[st]==belong[ed])
57 {
58 down(belong[st]);
59 for(ll i=st; i<=ed; i++)
60 a[i]*=val,a[i]=a[i]%mod;
61 return ;
62 }
63 down(belong[st]);
64 for(ll i=st; i<=r[belong[st]]; i++)
65 a[i]*=val,a[i]%=mod;
66 down(belong[ed]);
67 for(ll i=l[belong[ed]]; i<=ed; i++)
68 a[i]*=val,a[i]%=mod;
69 for(ll i=belong[st]+1; i)
70 mul[i]*=val,add[i]*=val,mul[i]%=mod,add[i]%=mod;
71 }
72 ll ask(ll pos)
73 {
74 return (a[pos]*mul[belong[pos]]%mod+add[belong[pos]])%mod;
75 }
76 int main()
77 {
78 memset(add,0,sizeof(add));
79 for(int i=0; i)
80 mul[i]=1;
81 scanf("%d",&n);
82 for(int i=1; i<=n; i++)
83 {
84 scanf("%lld",&a[i]);
85 }
86 buildblock();
87 ll op,st,ed;
88 ll val;
89 while(n--)
90 {
91 scanf("%lld %lld %lld %lld",&op,&st,&ed,&val);
92 if(op==0)
93 {
94 update1(st,ed,val);
95 }
96 else if(op==1)
97 {
98 update2(st,ed,val);
99 }
100 else if(op==2)
101 {
102 printf("%lld
",ask(ed)%mod);
103 }
104 }
105 return 0;
106 }
転載先:https://www.cnblogs.com/letlifestop/p/10472364.html