// IN THE NAME OF ALLAH
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL)
#define wall cerr << "------------------------------------" << endl
#define pb push_back
#define pob pop_back
#define F first
#define S second
#define all(x) x.begin() , x.end()
#define scan scanf
#define print printf
#define outs(x) print("%lld " , x)
#define out(x) print("%lld\n" , x)
#define in(x) scan("%lld" , &x)
#define gcd __gcd
#define endl '\n'
#define int ll
#pragma GCC optimize("Ofast")
typedef long long ll;
typedef pair<int , int> pii;
typedef pair<ll , ll> pll;
typedef pair<pii , int> piii;
typedef pair<pll , ll> plll;
const int N = 1e5+10;
const int K = 20 + 10;
const ll mod = 1e9+7;
const ll INF = 1e18+10;
const int P = 31;
int seg[4*N][K];
int la[4*N];
int n , q , k;
int a[N];
void build(int v , int tl , int tr) {
if(tl == tr) {
int x = a[tl];
seg[v][0] = x;
int o = 1;
while(x && o < 30) {
x /= k;
seg[v][o++] = x;
}
return;
}
int tm = (tl + tr)/2;
build(2*v , tl , tm);
build(2*v+1 , tm+1 , tr);
for(int i = 0 ; i < K ; i++)
seg[v][i] = seg[2*v][i] + seg[2*v+1][i];
}
void shift(int v , int tl , int tr) {
for(int i = 0 ; i <= K - la[v] - 1 ; i++)
seg[v][i] = seg[v][i+la[v]];
for(int i = K-1 ; i > K-la[v]-1 && i >= 0 ; i--)
seg[v][i] = 0;
if(tl != tr) {
la[2*v] += la[v];
la[2*v+1] += la[v];
}
la[v] = 0;
}
void update(int v , int tl , int tr , int pos , int x) {
shift(v , tl , tr);
if(tl > pos || pos > tr)
return;
if(tl == tr) {
int y = x;
seg[v][0] = y;
int o = 1;
while(y && o < 30) {
y /= k;
seg[v][o++] = y;
}
return;
}
int tm = (tl + tr)/2;
update(2*v , tl , tm , pos , x);
update(2*v+1 , tm+1 , tr , pos , x);
for(int i = 0 ; i < K ; i++)
seg[v][i] = seg[2*v][i] + seg[2*v+1][i];
}
void upd(int v , int tl , int tr , int l , int r) {
shift(v , tl , tr);
if(l > r)
return;
if(tl == l && tr == r) {
la[v] = 1;
shift(v , tl , tr);
return;
}
int tm = (tl + tr)/2;
upd(2*v , tl , tm , l , min(tm , r));
upd(2*v+1 , tm+1 , tr , max(l , tm+1) , r);
for(int i = 0 ; i < K ; i++)
seg[v][i] = seg[2*v][i] + seg[2*v+1][i];
}
int ask(int v , int tl , int tr , int l , int r) {
shift(v , tl , tr);
if(l > r)
return 0;
if(tl == l && tr == r)
return seg[v][0];
int tm = (tl + tr)/2;
return ask(2*v , tl , tm , l , min(tm , r)) + ask(2*v+1 , tm+1 , tr , max(l , tm+1) , r);
}
signed main()
{
fast;
cin >> n >> q >> k;
for(int i = 1 ; i <= n ; i++)
cin >> a[i];
build(1 , 1 , n);
if(k == 1) {
while(q--) {
int t , l , r;
cin >> t >> l >> r;
if(t == 1)
update(1 , 1 , n , l , r);
else if(t == 3)
cout << ask(1 , 1 , n , l , r) << "\n";
}
}
else {
while(q--) {
int t , l , r;
cin >> t >> l >> r;
if(t == 1)
update(1 , 1 , n , l , r);
else if(t == 2)
upd(1 , 1 , n , l , r);
else
cout << ask(1 , 1 , n , l , r) << "\n";
}
}
}
// IT'S EASY TO SEE
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
852 KB |
Output is correct |
3 |
Correct |
2 ms |
1364 KB |
Output is correct |
4 |
Incorrect |
6 ms |
1364 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
178 ms |
34236 KB |
Output is correct |
2 |
Correct |
129 ms |
20908 KB |
Output is correct |
3 |
Correct |
144 ms |
66380 KB |
Output is correct |
4 |
Correct |
182 ms |
67204 KB |
Output is correct |
5 |
Correct |
219 ms |
67568 KB |
Output is correct |
6 |
Correct |
242 ms |
67640 KB |
Output is correct |
7 |
Correct |
228 ms |
67532 KB |
Output is correct |
8 |
Correct |
230 ms |
67532 KB |
Output is correct |
9 |
Correct |
241 ms |
67464 KB |
Output is correct |
10 |
Correct |
179 ms |
67504 KB |
Output is correct |
11 |
Correct |
182 ms |
67608 KB |
Output is correct |
12 |
Correct |
194 ms |
67404 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
69 ms |
4368 KB |
Output is correct |
2 |
Correct |
73 ms |
32480 KB |
Output is correct |
3 |
Correct |
85 ms |
32388 KB |
Output is correct |
4 |
Correct |
216 ms |
16484 KB |
Output is correct |
5 |
Correct |
342 ms |
64716 KB |
Output is correct |
6 |
Correct |
330 ms |
64776 KB |
Output is correct |
7 |
Correct |
194 ms |
66008 KB |
Output is correct |
8 |
Correct |
340 ms |
66088 KB |
Output is correct |
9 |
Correct |
264 ms |
66000 KB |
Output is correct |
10 |
Correct |
248 ms |
66040 KB |
Output is correct |
11 |
Correct |
290 ms |
66044 KB |
Output is correct |
12 |
Correct |
251 ms |
65972 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
206 ms |
32704 KB |
Output is correct |
2 |
Correct |
230 ms |
32728 KB |
Output is correct |
3 |
Incorrect |
173 ms |
32636 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |