#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MXN = 2e5 + 20 , LOG = 35;
#define lt(x) 2*x+1
#define rt(x) 2*x+2
int n,q,k;
int a[MXN];
struct seg_tree {
int size;
vector<ll> v[LOG] , d;
seg_tree() {
size = 0;
}
void init() {
size = 1;
while(size < n) size <<= 1;
for(int i = 0 ; i < LOG ; i++) v[i].assign(2*size , 0);
d.assign(2*size , 0);
}
void build(int x , int lx , int rx) {
if(rx-lx == 1) {
if(lx < n) {
v[0][x] = a[lx];
for(int i = 1 ; i < LOG ; i++) {
v[i][x] = v[i-1][x]/k;
}
}
return;
}
int m = (lx+rx)/2;
build(lt(x) , lx , m); build(rt(x) , m , rx);
for(int i = 0 ; i < LOG ; i++) {
v[i][x] = v[i][lt(x)] + v[i][rt(x)];
}
}
void build() {
build(0 , 0 , size);
}
void shift(int x , int lx , int rx) {
if(rx-lx == 1) return;
d[lt(x)] += d[x];
d[rt(x)] += d[x];
}
void update(int x , int lx , int rx) {
for(int i = 0 ; i < LOG ; i++) {
v[i][x] = (i+d[x] < LOG ? v[i+d[x]][x] : 0);
}
d[x] = 0;
}
void set(int x , int lx , int rx , int i , ll k) {
if(rx-lx == 1) {
v[0][x] = k;
for(int i = 1 ; i < LOG ; i++) {
v[i][x] = v[i-1][x]/k;
}
d[x] = 0;
return;
}
shift(x , lx , rx);
int m = (lx+rx)/2;
if(i < m) {
set(lt(x) , lx , m , i , k);
shift(rt(x) , m , rx); update(rt(x) , m , rx);
} else {
set(rt(x) , m , rx , i , k);
shift(lt(x) , lx , m); update(lt(x) , lx , m);
}
d[x] = 0;
for(int i = 0 ; i < LOG ; i++) v[i][x] = v[i][lt(x)] + v[i][rt(x)];
}
void set(int i , ll k) {
set(0 , 0 , size , i , k);
}
void divide(int x , int lx , int rx , int l , int r) {
if(lx >= l && rx <= r) {
d[x]++;
shift(x , lx , rx);
update(x , lx , rx);
return;
}
if(lx >= r || rx <= l) {
shift(x , lx , rx);
update(x , lx , rx);
return;
}
shift(x , lx , rx);
int m = (lx+rx)/2;
divide(lt(x) , lx , m , l , r);
divide(rt(x) , m , rx , l , r);
d[x] = 0;
for(int i = 0 ; i < LOG ; i++) v[i][x] = v[i][lt(x)] + v[i][rt(x)];
}
void divide(int l , int r) {
divide(0 , 0 , size , l , r);
}
ll sum(int x , int lx , int rx , int l , int r) {
if(lx >= l && rx <= r) {
shift(x , lx , rx);
update(x , lx , rx);
return d[x] >= LOG ? 0 : v[d[x]][x];
}
if(lx >= r || rx <= l) {
shift(x , lx , rx);
update(x , lx , rx);
return 0;
}
shift(x , lx , rx);
int m = (lx+rx)/2;
ll a = sum(lt(x) , lx , m , l , r) , b = sum(rt(x) , m , rx , l , r);
d[x] = 0;
for(int i = 0 ; i < LOG ; i++) v[i][x] = v[i][lt(x)] + v[i][rt(x)];
return a+b;
}
ll sum(int l , int r) {
return sum(0 , 0 , size , l , r);
}
} seg;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cin >> n >> q >> k;
for(int i = 0 ; i < n ; i++) {
cin >> a[i];
}
seg.init(); seg.build();
while(q--) {
int type,x,y; cin >> type >> x >> y;
if(type == 1) {
seg.set(x-1 , y);
}
if(type == 2) {
seg.divide(x-1 , y);
}
if(type == 3) {
cout << seg.sum(x-1 , y) << "\n";
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2489 ms |
37996 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
10076 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1797 ms |
37920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
