#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
int K, C;
struct BIT{
int n;
vector<ll> sm;
BIT(int _n){
n = _n;
sm.resize(n);
}
void add(int in, ll x){
in++;
while(in <= n) sm[in-1]+=x, in+=in&-in;
}
ll sum(int in){
in++;
ll s = 0;
while(in >= 1) s+=sm[in-1], in-=in&-in;
return s;
}
ll sum(int l, int r){
return sum(r)-(l == 0? 0:sum(l-1));
}
};
struct segtree{
struct node{
int divisions;
deque<ll> d;
node(){
divisions = 0;
d.assign(C, 0);
}
node(ll x){
divisions = 0;
d.assign(C, 0);
for(int i = 0; i < C; i++){
d[i] = x%K;
x/=K;
}
reverse(d.begin(), d.end());
}
node operator+(node &a){
node rt;
for(int i = 0; i < C; i++) rt.d[i] = d[i]+a.d[i];
return rt;
}
void pushdown_from(node &p){
int x = p.divisions;
divisions+=x;
if(x >= C) d.assign(C, 0);
else{
while(x--) d.pop_back(), d.push_front(0);
}
}
};
int k;
vector<node> v;
segtree(int n){
k = 1;
while(k < n) k*=2;
k*=2;
v.assign(k, node());
}
void update(int in, int nd, int a, int b, ll x){
if(a == b){
v[nd] = node(x);
return;
}
int md = (a+b)/2;
v[2*nd].pushdown_from(v[nd]);
v[2*nd+1].pushdown_from(v[nd]);
v[nd].divisions = 0;
if(in <= md) update(in, 2*nd, a, md, x);
else update(in, 2*nd+1, md+1, b, x);
v[nd] = v[2*nd]+v[2*nd+1];
}
void update(int in, ll x){
update(in, 1, 0, k/2-1, x);
}
void spray(int l, int r, int nd, int a, int b){
if(a > r || b < l) return;
if(a >= l && b <= r){
v[nd].d.pop_back();
v[nd].d.push_front(0);
v[nd].divisions++;
return;
}
int md = (a+b)/2;
v[2*nd].pushdown_from(v[nd]);
v[2*nd+1].pushdown_from(v[nd]);
v[nd].divisions = 0;
spray(l, r, 2*nd, a, md);
spray(l, r, 2*nd+1, md+1, b);
v[nd] = v[2*nd]+v[2*nd+1];
}
void spray(int l, int r){
spray(l, r, 1, 0, k/2-1);
}
ll sum(int l, int r, int nd, int a, int b){
if(a > r || b < l) return 0;
if(a >= l && b <= r){
ll p = 1, s = 0;
for(int i = C-1; i >= 0; i--) s+=v[nd].d[i]*p, p*=K;
return s;
}
int md = (a+b)/2;
v[2*nd].pushdown_from(v[nd]);
v[2*nd+1].pushdown_from(v[nd]);
v[nd].divisions = 0;
ll rt = sum(l, r, 2*nd, a, md) + sum(l, r, 2*nd+1, md+1, b);
v[nd] = v[2*nd]+v[2*nd+1];
return rt;
}
ll sum(int l, int r){
return sum(l, r, 1, 0, k/2-1);
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n >> q >> K;
if(K == 1){
BIT bit(n);
for(int i = 0; i < n; i++){
ll x; cin >> x;
bit.add(i, x);
}
while(q--){
int tt; cin >> tt;
if(tt == 1){
int in; ll x; cin >> in >> x; in--;
bit.add(in, x-bit.sum(in, in));
}
if(tt == 2){
int l, r; cin >> l >> r; l--, r--;
//do nothing
}
if(tt == 3){
int l, r; cin >> l >> r; l--, r--;
cout << bit.sum(l, r) << "\n";
}
}
exit(0);
}
ll p = 1; C = 0;
while(p < ll(1e9)) p*=K, C++;
segtree seg(n);
for(int i = 0; i < n; i++){
ll x; cin >> x;
seg.update(i, x);
}
while(q--){
int tt; cin >> tt;
if(tt == 1){
int in; ll x; cin >> in >> x; in--;
seg.update(in, x);
}
if(tt == 2){
int l, r; cin >> l >> r; l--, r--;
seg.spray(l, r);
}
if(tt == 3){
int l, r; cin >> l >> r; l--, r--;
cout << seg.sum(l, r) << "\n";
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
596 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
8 ms |
5020 KB |
Output is correct |
| 4 |
Correct |
22 ms |
4564 KB |
Output is correct |
| 5 |
Correct |
30 ms |
9076 KB |
Output is correct |
| 6 |
Correct |
26 ms |
9040 KB |
Output is correct |
| 7 |
Correct |
28 ms |
9076 KB |
Output is correct |
| 8 |
Correct |
28 ms |
8988 KB |
Output is correct |
| 9 |
Correct |
42 ms |
9084 KB |
Output is correct |
| 10 |
Correct |
33 ms |
9036 KB |
Output is correct |
| 11 |
Correct |
29 ms |
9080 KB |
Output is correct |
| 12 |
Correct |
28 ms |
9032 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
3068 KB |
Output is correct |
| 2 |
Correct |
31 ms |
2600 KB |
Output is correct |
| 3 |
Correct |
30 ms |
2840 KB |
Output is correct |
| 4 |
Correct |
44 ms |
3504 KB |
Output is correct |
| 5 |
Correct |
38 ms |
3944 KB |
Output is correct |
| 6 |
Correct |
39 ms |
3916 KB |
Output is correct |
| 7 |
Correct |
42 ms |
3984 KB |
Output is correct |
| 8 |
Correct |
43 ms |
4032 KB |
Output is correct |
| 9 |
Correct |
40 ms |
3800 KB |
Output is correct |
| 10 |
Correct |
38 ms |
3852 KB |
Output is correct |
| 11 |
Correct |
42 ms |
3916 KB |
Output is correct |
| 12 |
Correct |
44 ms |
3900 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
347 ms |
18476 KB |
Output is correct |
| 2 |
Correct |
449 ms |
136096 KB |
Output is correct |
| 3 |
Correct |
591 ms |
136344 KB |
Output is correct |
| 4 |
Correct |
1100 ms |
71676 KB |
Output is correct |
| 5 |
Correct |
2043 ms |
283596 KB |
Output is correct |
| 6 |
Correct |
2462 ms |
283664 KB |
Output is correct |
| 7 |
Correct |
42 ms |
2636 KB |
Output is correct |
| 8 |
Correct |
2011 ms |
283788 KB |
Output is correct |
| 9 |
Correct |
1393 ms |
283516 KB |
Output is correct |
| 10 |
Correct |
1293 ms |
283516 KB |
Output is correct |
| 11 |
Correct |
1303 ms |
283500 KB |
Output is correct |
| 12 |
Correct |
1617 ms |
283624 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1166 ms |
144372 KB |
Output is correct |
| 2 |
Correct |
1292 ms |
145328 KB |
Output is correct |
| 3 |
Correct |
1129 ms |
137240 KB |
Output is correct |
| 4 |
Correct |
1261 ms |
80084 KB |
Output is correct |
| 5 |
Correct |
2060 ms |
285004 KB |
Output is correct |
| 6 |
Correct |
2045 ms |
284876 KB |
Output is correct |
| 7 |
Correct |
2057 ms |
284908 KB |
Output is correct |
| 8 |
Correct |
2593 ms |
284956 KB |
Output is correct |
| 9 |
Correct |
1907 ms |
284756 KB |
Output is correct |
| 10 |
Correct |
2021 ms |
284876 KB |
Output is correct |
| 11 |
Correct |
1680 ms |
284728 KB |
Output is correct |
| 12 |
Correct |
2084 ms |
284728 KB |
Output is correct |
