이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define nn "\n";
#define pb push_back
const int N = 2e6 + 8 , inf = 1e9+7 ;
int n , m , q , k , a[N] , t[N] , p[N] ,s[N];
void build(int v , int l , int r ){
if( l == r ){
t[v] = a[l];
p[v] = a[l]*l , s[v] = a[l]*(n - l + 1 );
return;
}
int mid = ( l + r )>>1;
build(v * 2 , l , mid );
build(v * 2 + 1 , mid + 1, r );
p[v] = p[v*2]+p[v*2+1];
s[v] = s[v*2]+s[v*2+1];
t[v] = t[v*2]+t[v*2+1];
}
int gett(int v , int tl , int tr , int l , int r ){
if(tl <= l && r <= tr ){
return t[v];
}
if(l > tr || r < tl ){
return 0 ;
}
int mid = ( l + r )/2;
return gett(v * 2 ,tl , tr , l , mid )+gett(v* 2 + 1 , tl , tr , mid + 1 , r );
}
int getp(int v , int tl , int tr , int l , int r ){
if(tl <= l && r <= tr ){
return p[v];
}
if(l > tr || r < tl ){
return 0 ;
}
int mid = ( l + r )/2;
return getp(v * 2 ,tl , tr , l , mid )+getp(v* 2 + 1 , tl , tr , mid + 1 , r );
}
int gets(int v , int tl , int tr , int l , int r ){
if(tl <= l && r <= tr ){
return s[v];
}
if(l > tr || r < tl ){
return 0 ;
}
int mid = ( l + r )/2;
return gets(v * 2 ,tl , tr , l , mid )+gets(v* 2 + 1 , tl , tr , mid + 1 , r );
}
void up(int v, int pos , int l , int r , int x ){
if(l == r ){
t[v] = x , p[v] = x * l , s[v] = x * ( n - l +1);
return ;
}
int mid = ( l + r )/2;
if(pos <= mid ){
up(v * 2 , pos , l , mid , x );
}
else {
up(v * 2 + 1 , pos , mid + 1 , r , x );
}
p[v] = p[v*2]+p[v*2+1];
s[v] = s[v*2]+s[v*2+1];
t[v] = t[v*2]+t[v*2+1];
}
signed main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin>> n >> k ;
for(int i= 1 ; i <= n; i++){
cin>> a[i];
}
build(1 , 1 , n );
cin>> q ;
while(q--) {
int h;
cin >> h;
if (h == 1) {
vector<int> v;
int w[k + 1];
for (int i = 1; i <= k; i++) {
cin >> w[i];
v.pb(a[w[i]]);
}
v.pb(a[v[0]]);
v.erase(v.begin());
for (int i = 1; i <= k; i++) {
a[w[i]] = v[i - 1];
up(1, w[i], 1, n, v[i - 1]);
}
} else {
int l, r;
cin >> l >> r >> m;
m = min(m, (r - l + 1) - m + 1);
int pos2 = l + m - 1;
int pos3 = r - m + 1;
int l1 = min(pos2, pos3);
int r1 = max(pos2, pos3);
int a1 = getp(1, l, l1 - 1 , 1, n) + (gett(1, l, l1-1, 1, n) * (-(l - 1)));
int b2 = gett(1, l1, r1, 1, n) * m;
int c2 = gets(1, r1 + 1, r, 1, n) + ((gett(1, r1 + 1, r, 1, n) * (-(r - r1 - 1 ))));
cout << b2 +a1 + c2 << nn
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |