#include <bits/stdc++.h>
#define DIM 100010
#define INF 1000000000000000LL
using namespace std;
const int max_exp = 32;
struct segment_tree{
long long v[max_exp];
int lazy;
} aint[DIM*4];
int n,k,q,i,j,x,y,tip;
long long sol[max_exp],v[DIM],p[max_exp],aint2[DIM*4];
void update_nod (int nod){
int fiu_st = nod<<1, fiu_dr = (nod<<1)|1;
for (int i=0;i<max_exp;i++)
aint[nod].v[i] = aint[fiu_st].v[i] + aint[fiu_dr].v[i];
}
void build (int nod, int st, int dr){
if (st == dr){
long long val = v[st];
for (int i=0;i<max_exp;i++){
aint[nod].v[i] = val % k;
val /= k;
}
/*
long long val = v[st];
for (int i=max_exp;i>=0;i--){
aint[nod].v[i] = val / p[i];
val -= aint[nod].v[i] * p[i];
}
*/
return;
}
int mid = (st+dr)>>1;
build (nod<<1,st,mid);
build ((nod<<1)|1,mid+1,dr);
update_nod (nod);
}
void update_lazy (int nod, int st, int dr){
if (!aint[nod].lazy)
return;
if (st != dr){
int fiu_st = nod<<1, fiu_dr = (nod<<1)|1;
int val = aint[nod].lazy;
for (int i=0;i+val<max_exp;i++){
aint[fiu_st].v[i] = aint[fiu_st].v[i + val];
aint[fiu_dr].v[i] = aint[fiu_dr].v[i + val];
}
for (int i=max_exp-val;i<max_exp;i++)
aint[fiu_st].v[i] = aint[fiu_dr].v[i] = 0;
aint[fiu_st].lazy += val;
aint[fiu_dr].lazy += val;
}
aint[nod].lazy = 0;
}
void update_intv (int nod, int st, int dr, int x, int y){
update_lazy (nod,st,dr);
if (x <= st && dr <= y){
for (int i=0;i<max_exp-1;i++)
aint[nod].v[i] = aint[nod].v[i+1];
aint[nod].v[max_exp-1] = 0;
aint[nod].lazy++;
update_lazy (nod,st,dr);
return;
}
int mid = (st+dr)>>1;
if (x <= mid)
update_intv (nod<<1,st,mid,x,y);
if (y > mid)
update_intv ((nod<<1)|1,mid+1,dr,x,y);
update_lazy (nod<<1,st,mid);
update_lazy ((nod<<1)|1,mid+1,dr);
update_nod(nod);
}
void update (int nod, int st, int dr, int poz, long long val){
update_lazy (nod,st,dr);
if (st == dr){
for (int i=0;i<max_exp;i++){
aint[nod].v[i] = val % k;
val /= k;
}
return;
}
int mid = (st+dr)>>1;
if (poz <= mid)
update (nod<<1,st,mid,poz,val);
else update ((nod<<1)|1,mid+1,dr,poz,val);
update_lazy (nod<<1,st,mid);
update_lazy ((nod<<1)|1,mid+1,dr);
update_nod (nod);
}
void query (int nod, int st, int dr, int x, int y){
update_lazy (nod,st,dr);
if (x <= st && dr <= y){
for (int i=0;i<max_exp;i++)
sol[i] += aint[nod].v[i];
return;
}
int mid = (st+dr)>>1;
if (x <= mid)
query (nod<<1,st,mid,x,y);
if (y > mid)
query ((nod<<1)|1,mid+1,dr,x,y);
}
void build2 (int nod, int st, int dr){
if (st == dr){
aint2[nod] = v[st];
return;
}
int mid = (st+dr)>>1;
build2 (nod<<1,st,mid);
build2 ((nod<<1)|1,mid+1,dr);
aint2[nod] = aint2[nod<<1] + aint2[(nod<<1)|1];
}
void update2 (int nod, int st, int dr, int poz, long long val){
if (st == dr){
aint2[nod] = val;
return;
}
int mid = (st+dr)>>1;
if (poz <= mid)
update2(nod<<1,st,mid,poz,val);
else update2((nod<<1)|1,mid+1,dr,poz,val);
aint2[nod] = aint2[nod<<1] + aint2[(nod<<1)|1];
}
long long query2 (int nod, int st, int dr, int x, int y){
if (x <= st && dr <= y)
return aint2[nod];
int mid = (st+dr)>>1;
long long sol_st = 0, sol_dr = 0;
if (x <= mid)
sol_st = query2(nod<<1,st,mid,x,y);
if (y > mid)
sol_dr = query2((nod<<1)|1,mid+1,dr,x,y);
return sol_st + sol_dr;
}
int main (){
//ifstream cin ("date.in");
//ofstream cout ("date.out");
cin>>n>>q>>k;
for (i=1;i<=n;i++)
cin>>v[i];
if (k == 1){
build2 (1,1,n);
for (;q--;){
cin>>tip>>x>>y;
if (tip == 1)
update2 (1,1,n,x,y);
else {
if (tip == 3)
cout<<query2 (1,1,n,x,y)<<"\n";
}
}
return 0;
}
p[0] = 1;
for (i=1;i<=max_exp;i++){
if (p[i-1] > INF / k)
break;
p[i] = p[i-1] * k;
}
build (1,1,n);
for (;q--;){
cin>>tip>>x>>y;
if (tip == 1)
update (1,1,n,x,y);
else {
if (tip == 2)
update_intv (1,1,n,x,y);
else {
for (int i=0;i<max_exp;i++)
sol[i] = 0;
query (1,1,n,x,y);
long long ans = 0;
for (int i=0;i<max_exp;i++)
ans += p[i] * sol[i];
cout<<ans<<"\n";
}
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
332 KB |
Output is correct |
| 2 |
Correct |
2 ms |
332 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1356 KB |
Output is correct |
| 4 |
Incorrect |
11 ms |
1356 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
187 ms |
2232 KB |
Output is correct |
| 2 |
Correct |
157 ms |
3532 KB |
Output is correct |
| 3 |
Correct |
134 ms |
4848 KB |
Output is correct |
| 4 |
Correct |
173 ms |
5572 KB |
Output is correct |
| 5 |
Correct |
231 ms |
5948 KB |
Output is correct |
| 6 |
Correct |
210 ms |
6020 KB |
Output is correct |
| 7 |
Correct |
216 ms |
5976 KB |
Output is correct |
| 8 |
Correct |
208 ms |
6020 KB |
Output is correct |
| 9 |
Correct |
204 ms |
5828 KB |
Output is correct |
| 10 |
Correct |
204 ms |
5880 KB |
Output is correct |
| 11 |
Correct |
240 ms |
5936 KB |
Output is correct |
| 12 |
Correct |
202 ms |
5828 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
165 ms |
4732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
491 ms |
34732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
