제출 #1280643

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1280643		azik21	Addk (eJOI21_addk)	C++20	100 / 100	211 ms	8804 KiB

Main

#include <map>
#include <set>
#include <unordered_set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <fstream>
#include <unordered_map>
#include <complex>
#define int long long 
#define pb push_back
#define all(v) (v).begin() , (v).end()
using namespace std;
const int N = 2e5+18;
int p[N * 4] , a[N] , s[4 * N] , sum[N*4];
int n ;
void build(int v , int l , int r ){
    if(l == r ){
        p[v] = a[l] * l;
        s[v] = a[l] * (n - l + 1 );
        sum[v] = a[l];
        return ;
    }
    int mid = ( l + r )/2;
    build(v * 2 , l , mid );
    build(v * 2 + 1 , mid + 1 ,r );
    sum[v] = sum[v * 2 ] + sum[v * 2 + 1 ];
    p[v] =p[v*2] + p[v*2+1];
    s[v] = s[v*2] + s[v * 2 + 1 ];
}
void up(int v , int l , int r , int pos, int x ){
    if(l == r ){
        sum[v] = x;
        p[v] = x * pos ;
        s[v] = x * (n - pos + 1 );
        return;
    }
    int mid = ( l + r ) / 2 ;
    if(pos <= mid )up(v * 2 , l , mid , pos , x );
    else up(v * 2 + 1 , mid + 1 , r , pos , x );
    sum[v] = sum[v * 2 ] + sum[v * 2 + 1 ];
    p[v] = p[v * 2 ] + p[v * 2 + 1 ];
    s[v] = s[v * 2 ] + s[v * 2 + 1 ];
}
int getsum(int v , int tl , int tr , int l , int r ){
    if(l <= tl && tr <= r )return sum[v];
    if(tl > r || l > tr )return 0 ;
    int mid = (tl + tr )/2;
    return getsum(v * 2 , tl , mid , l , r ) + getsum(v * 2 + 1 , mid + 1 , tr , l , r );
}
int getp(int v , int tl , int tr , int l , int r ){
    if(l <= tl && tr <= r )return p[v];
    if(tl > r || l > tr )return 0 ;
    int mid = (tl + tr )/2;
    return getp(v * 2 , tl , mid , l , r ) + getp(v * 2 + 1 , mid + 1 , tr , l , r );
}
int gets(int v , int tl , int tr , int l , int r ){
    if(l <= tl && tr <= r )return s[v];
    if(tl > r || l > tr )return 0 ;
    int mid = (tl + tr )/2;
    return gets(v * 2 , tl , mid , l , r ) + gets(v * 2 + 1 , mid + 1 , tr , l , r );
}
signed main(){

    // kbo 9.11

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int k ;
    cin >> n >> k ;
    for(int i= 1; i <= n ; i++){
        cin >> a[i];
    }
    build(1 , 1 ,n );
    int q;
    cin >> q ;
    while(q--){
        int type ;
        cin >> type;
        if(type==1){
            int pos[k + 1 ];
            vector<int>v;
            for(int i = 1 ; i <= k; i++){
                cin >> pos[i];
                if(i > 1 )v.pb(a[pos[i]]);
            }
            v.pb(a[pos[1]]);
            for(int i=0 ; i < v.size(); i++){
                a[pos[i+1]] = v[i];
                up(1 , 1 , n , pos[i+1] , v[i]);
            }
        }
        else {
            int l , r , m ;
            cin >> l >> r >> m ;
            int mx = (r - l + 1 )/m + (r - l + 1 ) % m ;
            int len = min((r - l + 1 ) - m, m - 1 ); 
            int tl = l + len - 1 , tr = r - len + 1 ;
            int first = getp(1 , 1 , n , l , tl ) - getsum(1 , 1 , n , l , tl ) * (l - 1 );
            int second = gets(1 , 1 , n ,tr , r  ) - getsum(1 , 1 , n , tr , r ) * (n - r );
            // cout << l << ' ' << r << ' ' << m << ' ' << len << ' ' << first + second + (sum[tr-1]- sum[tl]) * (len + 1 ) << '\n';
            cout << first + second + getsum(1 ,1 , n , tl + 1 , tr - 1 ) * (len + 1 ) << '\n';
        }
        // for(int i=1 ; i<= n ;i++)cout << a[i] << ' ' ;
        //     cout << '\n';
    }

}

• Subtask 1: 36 / 36
• Subtask 2: 56 / 56
• Subtask 3: 8 / 8