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 int long long
#define pb push_back
#define sz(x) x.size()
#define nl '\n'
#define F first
#define S second
const int N = 1e5 + 1;
int t[4 * N], a[N];
void upd( int v, int tl, int tr, int pos )
{
if( tl == tr )
{
t[v] = a[tl];
return;
}
int m = (tl + tr) / 2;
if( pos <= m )
upd(v + v, tl, m, pos);
else
upd(v + v + 1, m + 1, tr, pos);
t[v] = t[v + v] + t[v + v + 1];
}
int get( int v, int tl, int tr, int l, int r )
{
if( l > tr || tl > r )
return 0;
if( l <= tl && tr <= r )
return t[v];
int m = (tl + tr) / 2;
return get(v + v, tl, m, l, r) + get(v + v + 1, m + 1, tr, l, r);
}
signed main()
{
ios_base::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];
upd(1, 1, n, i);
}
cin >>q;
while( q-- )
{
int type, l, r, m;
cin >>type;
if( type == 1 )
{
vector< int >v, vv;
v.pb( 0 );
vv.pb( 0 );
for( int i = 1, x; i <= k; ++i )
{
cin >>x;
v.pb( x );
vv.pb( a[x] );
}
for( int i = 1; i <= k; ++i )
{
if( i == k )
a[v[i]] = vv[0];
else
a[v[i]] = vv[i + 1];
upd(1, 1, n, v[i]);
}
}
else
{
cin >>l >>r >>m;
int ans = get(1, 1, n, l, r) * m;
for( int i = 0, x = m - 1; i < m; ++i, --x )
{
ans -= a[l + i] * x;
ans -= a[r - i] * x;
}
cout <<ans <<nl;
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |