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 <bits/stdc++.h>
using namespace std;
#define ll long long
#define repp(i,a,b) for (ll i = a; i <= b; i++)
#define repz(i,a,b) for (ll i = a; i < b; i++)
#define repm(i,a,b) for (ll i = a; i >= b; i--)
const ll N = 1e5+5, MOD = 1e9+7;
ll tc = 1, n, m, ar[N], br[N], tree[N*4][3];
ll x, y, k;
void build(ll l, ll r, ll idx, ll cr){
if (l == r){
if (cr == 0) tree[idx][cr] = ar[l];
else if (cr == 1) tree[idx][cr] = ar[l]*l;
else tree[idx][cr] = ar[l]*(n-l+1);
return;
}
ll md = (l+r)/2;
build(l,md,idx*2,cr);
build(md+1,r,idx*2+1,cr);
tree[idx][cr] = tree[idx*2][cr]+tree[idx*2+1][cr];
}
ll que(ll l, ll r, ll idx, ll x, ll y, ll cr){
if (l > r || l > y || r < x) return 0;
if (x <= l && r <= y) return tree[idx][cr];
ll md = (l+r)/2;
return que(l,md,idx*2,x,y,cr)+que(md+1,r,idx*2+1,x,y,cr);
}
void upd(ll l, ll r, ll idx, ll pos, ll val, ll cr){
if (l == r){
if (cr == 0) tree[idx][cr] = val;
else if (cr == 1) tree[idx][cr] = val*l;
else tree[idx][cr] = val*(n-l+1);
return;
}
ll md = (l+r)/2;
if (pos <= md) upd(l,md,idx*2,pos,val,cr);
else upd(md+1,r,idx*2+1,pos,val,cr);
tree[idx][cr] = tree[idx*2][cr]+tree[idx*2+1][cr];
}
void input(){
}
void solve(){
build(1,n,1,0);
build(1,n,1,1);
build(1,n,1,2);
cin >> m;
while(m--){
ll a, b, c, d;
cin >> a;
if (a == 1){
vector<ll> idx, val;
ll lst;
repp(i,1,k){
cin >> b;
idx.push_back(b);
if (i != 1) val.push_back(ar[b]);
else lst = ar[b];
}
val.push_back(lst);
repz(i,0,k){
upd (1,n,1,idx[i],val[i],0);
upd (1,n,1,idx[i],val[i],1);
upd (1,n,1,idx[i],val[i],2);
ar[idx[i]] = val[i];
}
continue;
}
cin >> b >> c >> d;
ll len = c-b+1;
if (d > (len+1)/2) d = len-d+1;
ll ten = que(1,n,1,b+d,c-d,0)*d;
ll kir= que(1,n,1,b,b+d-1,1)-que(1,n,1,b,b+d-1,0)*(b-1);
ll kan = que(1,n,1,c-d+1,c,2)-que(1,n,1,c-d+1,c,0)*(n-c);
ll tot = kir+kan+ten;
if (len%2 && d == (len+1)/2){
tot -= que(1,n,1,b+d-1,b+d-1,0)*d;
}
cout << tot << endl;
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> ar[i];
solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |