#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;
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 == 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";
}
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
7 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
24 ms |
2424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
301 ms |
18236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1022 ms |
142876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
