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<deque>
using namespace std;
long long int a[100005], d[1000005], lazy[1000005];
void push(int v, int tl, int tr) {
int mid = (tl + tr) / 2;
d[v * 2] += lazy[v] * (mid - tl + 1);
d[v * 2 + 1] += lazy[v] * (tr - mid);
lazy[v * 2] += lazy[v];
lazy[v * 2 + 1] += lazy[v];
lazy[v] = 0;
}
void update(int v, int tl, int tr, int l, int r, long long int x) {
if (l > r) return;
if (tl == l && tr == r) {
d[v] += x * (r - l + 1);
lazy[v] += x;
return;
}
push(v, tl, tr);
int mid = (tl + tr) / 2;
update(v * 2, tl, mid, l, min(r, mid), x);
update(v * 2 + 1, mid + 1, tr, max(l, mid + 1), r, x);
d[v] = d[v * 2] + d[v * 2 + 1];
}
long long int get(int v, int tl, int tr, int l, int r) {
if (l > r) return 0;
if (tl == l && tr == r) {
return d[v];
}
push(v, tl, tr);
int mid = (tl + tr) / 2;
return get(v * 2, tl, mid, l, min(r, mid)) + get(v * 2 + 1, mid + 1, tr, max(l, mid + 1), r);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n,k,q;
cin >> n >> k;
for(int i = 1;i <= n;i++)
{
cin >> a[i];
update(1,0,n,i,n,a[i]);
}
cin >> q;
while(q--)
{
long long int type,l,r,x;
cin >> type;
if(type == 2)
{
cin >> l >> r >> x;
int h = (l + x - 1);
k = r - x;
cout << get(1,0,n,h,r) - get(1,0,n,l - 1,k) << endl;
}
else
{
deque<int> v,d;
for(int i = 0;i < k;i++)
{
int x;
cin >> x;
v.push_back(x);
d.push_back(x);
}
d.push_back(d[0]);
d.pop_front();
for(int i = 0;i < k;i++)
{
update(1,0,n,v[i],n,a[d[i]] - a[v[i]]);
}
int h = a[v[0]];
for(int i = 0;i < k - 1;i++)
{
a[v[i]] = a[d[i]];
}
a[v[k - 1]] = h;
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |