#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define ar array
#define all(x) x.begin(),x.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
bool remender(ll a , ll b){return a%b;}
//freopen("problemname.in", "r", stdin);
//freopen("problemname.out", "w", stdout);
int k;
struct item {
vector<ll> vec;
int cnt;
};
struct Seg {
int siz;
vector<item> v;
void init(int n){
siz = 1;
while(siz < n)siz *= 2;
v.resize(siz * 2);
}
item single(int x){
item res;
res.cnt = 0;
while(x > 0){
//cout << x << endl;
res.vec.pb(x);
x /= k;
}
reverse(all(res.vec));
return res;
}
item merge(item& a , item& b){
item res;
res.cnt = 0;
int i = a.vec.size()-1;
int j = b.vec.size()-1;
while(i >= 0 || j >= 0){
ll sum = 0;
if(i >= 0)sum += a.vec[i];
if(j >= 0)sum += b.vec[j];
res.vec.pb(sum);
i--;
j--;
}
reverse(all(res.vec));
return res;
}
void lazy(int x , int cnt){
while(v[x].vec.size() && cnt){
v[x].vec.pop_back();
cnt--;
}
}
void build(vector<int>& a , int x , int lx , int rx){
if(rx - lx == 1){
if(lx < a.size()){
v[x] = single(a[lx]);
}
v[x].cnt = 0;
return;
}
int m = (lx + rx)/2;
build(a,2*x+1,lx,m);
build(a,2*x+2,m,rx);
v[x] = merge(v[2 * x + 1] , v[2 * x + 2]);
}
void build(vector<int>& a){
build(a , 0 , 0 , siz);
}
void remove(int l , int r , int x, int lx , int rx){
if(lx >= r || l >= rx)return;
if(lx >= l && rx <= r){
v[x].cnt++;
if(v[x].vec.size()){
v[x].vec.pop_back();
}
return;
}
v[2*x+1].cnt += v[x].cnt;
v[2*x+2].cnt += v[x].cnt;
lazy(2*x+1,v[x].cnt);
lazy(2*x+2,v[x].cnt);
v[x].cnt = 0;
int m = (lx + rx)/2;
remove(l,r,2*x+1,lx,m);
remove(l,r,2*x+2,m,rx);
v[x] = merge(v[2*x+1],v[2*x+2]);
}
void remove(int l , int r){
remove(l , r , 0 , 0 , siz);
}
void set(int i , int val , int x , int lx , int rx){
if(rx - lx == 1){
v[x] = single(val);
return;
}
v[2*x+1].cnt += v[x].cnt;
v[2*x+2].cnt += v[x].cnt;
lazy(2*x+1,v[x].cnt);
lazy(2*x+2,v[x].cnt);
v[x].cnt = 0;
int m = (lx + rx)/2;
if(i < m)set(i , val , 2 * x + 1 , lx , m);
else set(i , val , 2 * x + 2 , m , rx);
v[x] = merge(v[2 * x + 1] , v[2 * x + 2]);
}
void set(int i , int val){
set(i , val , 0 , 0 , siz);
}
ll sum(int l , int r , int x , int lx , int rx){
if(lx >= r || l >= rx)return 0;
if(lx >= l && rx <= r){
if(v[x].vec.size()){
return v[x].vec.back();
}
return 0;
}
v[2*x+1].cnt += v[x].cnt;
v[2*x+2].cnt += v[x].cnt;
lazy(2*x+1,v[x].cnt);
lazy(2*x+2,v[x].cnt);
v[x].cnt = 0;
int m = (lx + rx)/2;
ll res = sum(l , r , 2 * x + 1 , lx , m);
res += sum(l , r , 2 * x +2 , m , rx);
v[x] = merge(v[2*x+1],v[2*x+2]);
return res;
}
ll sum(int l , int r){
return sum(l , r , 0 , 0 , siz);
}
};
void solve(){
int n,q;
cin >> n >> q >> k;
vector<int> arr(n);
for(int i = 0; i < n; i++)cin >> arr[i];
Seg st;
st.init(n+1);
//cout << "came1" << endl;
st.build(arr);
//cout << "came" << endl;
while(q--){
int a , b , c;
cin >> a >> b >> c;
if(a == 1){
st.set(b - 1 , c);
}
else if(a == 2){
st.remove(b - 1 , c);
}
else {
cout << st.sum(b-1,c) << '\n';
}
//cout << st.sum(0,5) << ' ';
//cout << "Came" << endl;
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//int t;cin >> t;while(t--)
solve();
return 0;
}
Compilation message
sterilizing.cpp: In member function 'void Seg::build(std::vector<int>&, int, int, int)':
sterilizing.cpp:80:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | if(lx < a.size()){
| ~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
372 KB |
Output is correct |
| 2 |
Runtime error |
642 ms |
524288 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
668 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
1612 KB |
Output is correct |
| 2 |
Correct |
29 ms |
6740 KB |
Output is correct |
| 3 |
Correct |
44 ms |
6864 KB |
Output is correct |
| 4 |
Correct |
107 ms |
4684 KB |
Output is correct |
| 5 |
Correct |
152 ms |
14672 KB |
Output is correct |
| 6 |
Correct |
158 ms |
14660 KB |
Output is correct |
| 7 |
Runtime error |
497 ms |
524288 KB |
Execution killed with signal 9 |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
300 ms |
20736 KB |
Output is correct |
| 2 |
Correct |
343 ms |
20892 KB |
Output is correct |
| 3 |
Correct |
356 ms |
29772 KB |
Output is correct |
| 4 |
Correct |
388 ms |
13736 KB |
Output is correct |
| 5 |
Correct |
528 ms |
39496 KB |
Output is correct |
| 6 |
Correct |
528 ms |
39972 KB |
Output is correct |
| 7 |
Correct |
512 ms |
39108 KB |
Output is correct |
| 8 |
Correct |
680 ms |
64404 KB |
Output is correct |
| 9 |
Correct |
465 ms |
39684 KB |
Output is correct |
| 10 |
Correct |
551 ms |
64276 KB |
Output is correct |
| 11 |
Correct |
398 ms |
39632 KB |
Output is correct |
| 12 |
Correct |
610 ms |
64776 KB |
Output is correct |
