#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);
}
};
struct Fen {
vector<ll> tree;
void init(int n){
tree.assign(n + 1 , 0LL);
}
void set(int i , ll val , int n){
i++;
while(i <= n){
tree[i] += val;
i += (i & (-i));
}
}
ll sum(int i){
i++;
ll ans = 0;
while(i > 0){
ans += tree[i];
i -= (i & (-i));
}
return ans;
}
void build(vector<int>& a){
int n = a.size();
for(int i = 0; i < n; i++){
set(i , a[i] , n);
}
}
};
void solve(){
int n,q;
cin >> n >> q >> k;
vector<int> arr(n);
for(int i = 0; i < n; i++)cin >> arr[i];
if(k == 1){
Fen ft;
ft.init(n+1);
for(int i = 0; i < n; i++)ft.set(i , arr[i] , n + 1);
while(q--){
int a , b , c;
cin >> a >> b >> c;
b--;
if(a == 1){
ft.set(b , c - arr[b] , n + 1);
arr[b] = c;
}
else if(a == 3)cout << ft.sum(c-1) - ft.sum(b) << '\n';
}
return;
}
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 |
7 ms |
368 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
360 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
3248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
1168 KB |
Output is correct |
| 2 |
Correct |
32 ms |
6520 KB |
Output is correct |
| 3 |
Correct |
53 ms |
6484 KB |
Output is correct |
| 4 |
Correct |
100 ms |
3556 KB |
Output is correct |
| 5 |
Correct |
146 ms |
13192 KB |
Output is correct |
| 6 |
Correct |
163 ms |
13232 KB |
Output is correct |
| 7 |
Incorrect |
29 ms |
3032 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
315 ms |
19344 KB |
Output is correct |
| 2 |
Correct |
365 ms |
19196 KB |
Output is correct |
| 3 |
Correct |
352 ms |
28640 KB |
Output is correct |
| 4 |
Correct |
386 ms |
11792 KB |
Output is correct |
| 5 |
Correct |
547 ms |
37100 KB |
Output is correct |
| 6 |
Correct |
572 ms |
37420 KB |
Output is correct |
| 7 |
Correct |
512 ms |
36796 KB |
Output is correct |
| 8 |
Correct |
733 ms |
62040 KB |
Output is correct |
| 9 |
Correct |
456 ms |
37384 KB |
Output is correct |
| 10 |
Correct |
547 ms |
61896 KB |
Output is correct |
| 11 |
Correct |
381 ms |
37440 KB |
Output is correct |
| 12 |
Correct |
620 ms |
62436 KB |
Output is correct |
