#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
using ll = long long ;
//#define int long long
using ii = pair < int , int > ;
const int MAX = 1e5+4,mod=1e9+7;
const int inf=0x3f3f3f3f;
int K;
vector < ii > pr[MAX];
void minn(int &a , int b){
if(b<a) a=b;
}
void maxx(int &a , int b){
if(b>a) a=b;
}
int LZ[MAX*4];
int ST[30][MAX*4];
int val;
int a[MAX];
void up (int x,int id,int l,int r){
if(l==r){
int z=0;
while(val!=0){
ST[z++][id]=val%K;
val/=K;
}
return;
}
int mid=l+r>>1;
if(LZ[id]){
minn(LZ[id],30);
LZ[id<<1]+=LZ[id];
LZ[id<<1|1]+=LZ[id];
for(int i=0;i<30-LZ[id];i++) ST[i][id<<1]=ST[i+LZ[id]][id<<1],ST[i][id<<1|1]=ST[i+LZ[id]][id<<1|1];;
for(int i=30-LZ[id];i<30;i++) ST[i][id<<1]=ST[i][id<<1|1]=0;
LZ[id]=0;
}
if(x>mid) up(x,id<<1|1,mid+1,r);
else up(x,id<<1,l,mid);
for(int i=29;i>=0;i--) ST[i][id]=ST[i][id<<1]+ST[i][id<<1|1];
}
void upd (int x,int y,int id,int l,int r){
if(y<l || x>r) return;
if(x<=l && r<=y){
for(int i=0;i<29;i++)
ST[i][id]=ST[i+1][id];
ST[29][id]=0;
LZ[id]++;
return;
}
int mid=l+r>>1;
if(LZ[id]){
minn(LZ[id],30);
LZ[id<<1]+=LZ[id];
LZ[id<<1|1]+=LZ[id];
for(int i=0;i<30-LZ[id];i++) ST[i][id<<1]=ST[i+LZ[id]][id<<1],ST[i][id<<1|1]=ST[i+LZ[id]][id<<1|1];;
for(int i=30-LZ[id];i<30;i++) ST[i][id<<1]=ST[i][id<<1|1]=0;
LZ[id]=0;
}
upd(x,y,id<<1,l,mid);
upd(x,y,id<<1|1,mid+1,r);
for(int i=29;i>=0;i--) ST[i][id]=ST[i][id<<1]+ST[i][id<<1|1];
}
ll P[30];
ll get(int x,int y,int id,int l,int r){
if(y<l || x>r) return 0;
if(x<=l && r<=y){
ll res=0;
for(int i=0;i<30;i++)
res+=P[i]*ST[i][id];
return res;
}
int mid=l+r>>1;
if(LZ[id]){
minn(LZ[id],30);
LZ[id<<1]+=LZ[id];
LZ[id<<1|1]+=LZ[id];
for(int i=0;i<30-LZ[id];i++) ST[i][id<<1]=ST[i+LZ[id]][id<<1],ST[i][id<<1|1]=ST[i+LZ[id]][id<<1|1];;
for(int i=30-LZ[id];i<30;i++) ST[i][id<<1]=ST[i][id<<1|1]=0;
LZ[id]=0;
}
return get(x,y,id<<1,l,mid)+get(x,y,id<<1|1,mid+1,r);
}
int main() {
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//freopen("JOI15.inp", "r", stdin);//freopen("JOI15.out", "w", stdout);
int n,Q;
cin>>n>>Q>>K;
P[0]=1;
for(int i=1;i<30;i++) P[i]=P[i-1]*K;
for(int i=1;i<=n;i++) {cin>>val;up(i,1,1,n);}
int t,x,y;
while(Q--){
cin>>t>>x>>y;
if(t==1){
val=y;
up(x,1,1,n);
}
else{
if(t==2)
upd(x,y,1,1,n);
else cout<<get(x,y,1,1,n)<<'\n';
}
}
}
Compilation message
sterilizing.cpp: In function 'void up(int, int, int, int)':
sterilizing.cpp:34:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
34 | int mid=l+r>>1;
| ~^~
sterilizing.cpp: In function 'void upd(int, int, int, int, int)':
sterilizing.cpp:57:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
57 | int mid=l+r>>1;
| ~^~
sterilizing.cpp: In function 'll get(int, int, int, int, int)':
sterilizing.cpp:79:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
79 | int mid=l+r>>1;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2944 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
5632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
111 ms |
5496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
449 ms |
20472 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
