제출 #1190477

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190477		ezzzay	Addk (eJOI21_addk)	C++20	100 / 100	91 ms	5904 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define int long long
const int N=1e5+5;
int a[N];
int ps[N];
int PS[N],SF[N];
vector<int>ans;
int n,k;
 inline void updateps(int idx, int val){
    while(idx<N){
        ps[idx]+=val;
        idx+= idx & -idx;
    }
}
inline int findps(int idx){
    if(idx==0)return 0;
    int s=0;
    while(idx>0){
        s+=ps[idx];
        idx-= idx & -idx;
    }
    return s;
}
inline void updatePS(int idx, int val){
    while(idx<N){
        PS[idx]+=val;
        idx+= idx & -idx;
    }
}
inline int findPS(int idx){
    if(idx==0)return 0;
    int s=0;
    while(idx>0){
        s+=PS[idx];
        idx-= idx & -idx;
    }
    return s;
}
inline void updateSF(int idx, int val){
    idx= n-idx+1;
    while(idx<N){
        SF[idx]+=val;
        idx+= idx & -idx;
    }
}
inline int findSF(int idx){
    idx= n-idx+1;
    if(idx==0)return 0;
    int s=0;
    while(idx>0){
        s+=SF[idx];
        idx-= idx & -idx;
    }
    return s;
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>k;
    vector<int>v(k+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        updateps(i, a[i]);
        updatePS(i,a[i]*i);
    }
    for(int i=n;i>=1;i--){
        updateSF(i,(n-i+1)*a[i]);
    }
    int q;
    cin>>q;
    while(q--){
        int t;
        cin>>t;
        if(t==1){
            for(int i=1;i<=k;i++){
                cin>>v[i];
                updateps(v[i],-a[v[i]]);
                updatePS(v[i],-a[v[i]]*v[i]);
                updateSF(v[i],-a[v[i]]*(n-v[i]+1));
            }
            int h=a[v[1]];
            for(int i=2;i<=k;i++){
                a[v[i-1]]=a[v[i]];
            }
            a[v[k]]=h;
            for(int i=1;i<=k;i++){
                updateps(v[i],a[v[i]]);
                updatePS(v[i],a[v[i]]*v[i]);
                updateSF(v[i],a[v[i]]*(n-v[i]+1));
            }
        }
        else{
            int l,r,m;
            cin>>l>>r>>m;
            int s=0;
            int k=min(m,r-l+1-m+1);
            int L=l+k-1;
            int R=r-k+1;
            cout<< (findps(R-1)-findps(L))*k + (findPS(L)-findPS(l-1)) - (findps(L)-findps(l-1))*(l-1) + findSF(R)-findSF(r+1) - (findps(r)-findps(R-1))*(n-r)<<'\n';
            ans.pb(s);
        }
    }
}

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