This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#define ll unsigned long long
using namespace std;
class SegmentTree {
ll n, i = 0;
vector<ll> seggy;
public:
SegmentTree(ll size):n(size) {
seggy = vector<ll>(2*n);
}
void build() {
for(ll i = n-1; i > 0; i--) seggy[i] = seggy[2*i]+seggy[2*i+1];
}
void push(ll x) {
seggy[n+i] = x;
i++;
}
void update(ll x, ll y) {
x+=n;
seggy[x] = y;
while(x > 1) {
x/=2;
seggy[x] = seggy[2*x]+seggy[2*x+1];
}
}
ll query(ll x, ll y) {
ll res = 0;
for(x+=n, y+=n+1; x<y; x/=2, y/=2) {
if(x%2) res+=seggy[x++];
if(y%2) res+=seggy[--y];
}
return res;
}
void print() {
for(int i = 0; i < 2*n; i++) cout << seggy[i] << endl;
}
};
int main() {
ll n, k, q, l, r, m;
cin >> n >> k;
vector<ll> a(n), u(k);
SegmentTree b(n), c(n);
for(ll i = 0; i < n; i++) {
cin >> a[i];
b.push(a[i]);
c.push((i+1)*a[i]);
}
b.build();
c.build();
cin >> q;
while(q--) {
cin >> m;
if(m == 1) {
for(ll i = 0; i < k; i++) {
cin >> u[i];
u[i]--;
}
l = a[u[k-1]];
for(ll i = k-1; i > 0; i--) {
b.update(u[i-1], l);
c.update(u[i-1], (u[i-1]+1)*l);
r = a[u[i-1]];
a[u[i-1]] = l;
l = r;
}
b.update(u[k-1], l);
c.update(u[k-1], (u[k-1]+1)*l);
a[u[k-1]] = l;
} else {
cin >> l >> r >> m;
l--, r--;
if(2*m <= r-l+1) cout << c.query(l, l+m-1)-l*b.query(l, l+m-1) + b.query(l+m, r-m)*m + (r+2)*b.query(r-m+1, r)-c.query(r-m+1, r) << "\n";
else cout << c.query(l, r-m)-l*b.query(l, r-m) + b.query(r-m+1, l+m-1)*(r-l+2-m) + (r+2)*b.query(l+m, r)-c.query(l+m, r) << "\n";
}
}
}
Compilation message (stderr)
Main.cpp: In member function 'void SegmentTree::print()':
Main.cpp:37:26: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
37 | for(int i = 0; i < 2*n; i++) cout << seggy[i] << endl;
| ~~^~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |