//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<ll , x>
#define endl '\n'
int n , q , k , a[100000];
arr(30) seg[400001];
int seginf[400001][2] , laz[400001];
arr(30) frm(int e){
arr(30) res;
for(int i = 0 ; i < 30 ; i++){
res[i] = e % k;;
e /= k;
}
return res;
}
void readSeg(int i){
for(int bit = 0 ; bit < 30 ; bit++) seg[i][bit] = seg[i << 1][bit] + seg[(i << 1) | 1][bit];
}
void buildSeg(int l = 0 , int r = n - 1 , int i = 1){
seginf[i][0] = l , seginf[i][1] = r , laz[i] = 0;
if(l == r) seg[i] = frm(a[l]);
else{
int c = (r + l - 1) >> 1;
buildSeg(l , c , i << 1) , buildSeg(c + 1 , r , (i << 1) | 1);
readSeg(i);
}
}
void shftSeg(int i , int e){
for(int bit = 0 ; bit < 30 ; bit++){
if(bit + e < 30) seg[i][bit] = seg[i][bit + e];
else seg[i][bit] = 0;
}
}
void pushSeg(int i){
if(laz[i] == 0) return;
for(int ch = (i << 1) ; ch <= ((i << 1) | 1) ; ch++){
laz[ch] += laz[i] , shftSeg(ch , laz[i]);
}
laz[i] = 0;
}
void chgSeg(int l , int i , int val){
if(seginf[i][0] == l and seginf[i][1] == l) seg[i] = frm(val);
else if(seginf[i][0] <= l and seginf[i][1] >= l){
pushSeg(i);
chgSeg(l , i << 1 , val) , chgSeg(l , (i << 1) | 1 , val);
readSeg(i);
}
}
void updSeg(int l , int r , int i){
if(seginf[i][0] >= l and seginf[i][1] <= r) shftSeg(i , 1) , laz[i]++;
else if(seginf[i][1] >= l and seginf[i][0] <= r){
pushSeg(i);
updSeg(l , r , i << 1) , updSeg(l , r , (i << 1) | 1);
readSeg(i);
}
}
ll getSeg(int l , int r , int i){
if(seginf[i][0] >= l and seginf[i][1] <= r){
ll d = 1 , res = 0;
for(int bit = 0 ; bit < 30 and d <= int(1e9) ; bit++ , d *= k) res += (d * (1ll * seg[i][bit]));
return res;
}else if(seginf[i][1] >= l and seginf[i][0] <= r){
pushSeg(i);
return (getSeg(l , r , i << 1) + getSeg(l , r , (i << 1) | 1));
}
return 0;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> q >> k;
bool flg = (k == 1);
if(flg) k = int(2e9);
for(int i = 0 ; i < n ; i++) cin >> a[i];
for(int i = 0 ; i < n ; i++){
ps[i] = a[i];
if(i > 0) ps[i] += ps[i - 1];
}
buildSeg();
for(int i = 0 ; i < q ; i++){
int op , l , r;
cin >> op >> l >> r;
if(op == 1){
chgSeg(l - 1 , 1 , r);
}else if(op == 2){
if(!flg) updSeg(l - 1 , r - 1 , 1);
}else{
cout << getSeg(l - 1 , r - 1 , 1) << endl;
}
}
}
Compilation message
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:91:9: error: 'ps' was not declared in this scope; did you mean 'pp'?
91 | ps[i] = a[i];
| ^~
| pp