#include <bits/stdc++.h>
using namespace std;
const long long nx=1e5+5, kx=33;
#define ll long long
ll n, q, k, a[nx], p[kx], x, l, r, t;
struct segtree
{
struct node
{
ll cnt, lz, sm[kx];
} d[4*nx];
void pushlz(int l, int r, int i)
{
d[i].cnt=min(d[i].cnt+d[i].lz, kx);
if (l==r) return void(d[i].lz=0);
d[2*i].lz+=d[i].lz;
d[2*i+1].lz+=d[i].lz;
return void(d[i].lz=0);
}
void update(int l, int r, int i, int idx, int vl)
{
pushlz(l, r, i);
if (r<idx||idx<l) return;
if (l==r)
{
for (int j=0; j<kx; j++) d[i].sm[j]=vl/p[j];
d[i].cnt=0;
return;
}
int md=(l+r)/2;
update(l, md, 2*i, idx, vl);
update(md+1, r, 2*i+1, idx, vl);
for (int j=0; j<kx; j++) d[i].sm[j]=d[2*i].sm[min(d[2*i].cnt+j, kx-1)]+d[2*i+1].sm[min(d[2*i+1].cnt+j, kx-1)];
d[i].cnt=0;
}
void update2(int l, int r, int i, int ql, int qr)
{
pushlz(l, r, i);
if (qr<l||r<ql) return;
if (ql<=l&&r<=qr) return void(d[i].lz++);
int md=(l+r)/2;
update2(l, md, 2*i, ql, qr);
update2(md+1, r, 2*i+1, ql, qr);
}
ll query(int l, int r, int i, int ql, int qr)
{
pushlz(l, r, i);
if (qr<l||r<ql) return 0;
if (ql<=l&&r<=qr) return d[i].sm[d[i].cnt];
int md=(l+r)/2;
return query(l, md, 2*i, ql, qr)+query(md+1, r, 2*i+1, ql, qr);
}
} s;
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>q>>k;
for (int i=1; i<=4*n; i++) for (int j=0; j<kx; j++) s.d[i].cnt=s.d[i].lz=s.d[i].sm[j]=0;
p[0]=1;
for (int i=1; i<nx; i++) p[i]=min((ll)2e9, p[i-1]*k);
for (int i=1; i<=n; i++) cin>>a[i], s.update(1, n, 1, i, a[i]);
//for (int i=0; i<kx; i++) cout<<i<<' '<<s.d[1].sm[i]<<'\n';
while (q--)
{
cin>>t;
if (t==1) cin>>x>>a[x], s.update(1, n, 1, x, a[x]);
if (t==2) cin>>l>>r, s.update2(1, n, 1, l, r);
if (t==3) cin>>l>>r, cout<<s.query(1, n, 1, l, r)<<'\n';
}
}
Compilation message
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:66:34: warning: iteration 32 invokes undefined behavior [-Waggressive-loop-optimizations]
66 | for (int i=1; i<nx; i++) p[i]=min((ll)2e9, p[i-1]*k);
| ~~~~^~~~~~~~~~~~~~~~~~~~~~~
sterilizing.cpp:66:20: note: within this loop
66 | for (int i=1; i<nx; i++) p[i]=min((ll)2e9, p[i-1]*k);
| ~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
182 ms |
55184 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
9628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
155 ms |
58844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
