Submission #1164161

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164161		PikachudoraEHE	Addk (eJOI21_addk)	C++20	0 / 100	92 ms	1348 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int cur[N],n,k;
struct fenwick{
    int f[N];
    void update(int idx,int val){
        for(int i=idx;i<=n;i+=i&-i){
                f[i]+=val;
        }
    return;
    }
    int query(int idx){
        int s= 0;
        for(int i=idx;i>0;i-=i&-i){
                s+=f[i];
        }
    return s;
    }
}f1,f2,f3;
int main(){
    //ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>cur[i];
        f1.update(i,cur[i]);
        f2.update(i,cur[i]*i);
        f3.update(n-i+1,cur[i]*(n-i+1));
    }
    int q;cin>>q;
    while(q--){
        int op;cin>>op;
        if(op==1){
            vector<int>v,v2;
            for(int i=0;i<k;i++){
                int aa;cin>>aa;
                v.push_back(cur[aa]);
                v2.push_back(aa);
            }
            for(int i=1;i<k;i++){
                f1.update(v2[i-1],v[i]-cur[v2[i-1]]);
                f2.update(v2[i-1],(v[i]-cur[v2[i-1]])*v2[i-1]);
                f3.update(n-v2[i-1]+1,(v[i]-cur[v2[i-1]])*(n-v2[i-1]+1));
                cur[v2[i-1]]=v[i];
            }
            f1.update(v2[k-1],v[0]-cur[v2[k-1]]);
            f2.update(v2[k-1],(v[0]-cur[v2[k-1]])*v2[k-1]);
            f3.update(n-v2[k-1]+1,(v[0]-cur[v2[k-1]])*(n-v2[k-1]+1));
            cur[v2[k-1]]=v[0];

            /*for(int i=1;i<=n;i++){
                cout<<cur[i]<<" "<<f1.query(i)<<" "<<f2.query(i)<<f3.query(i)<<"\n";
            }*/
        }
        else{
            int l,r,m;cin>>l>>r>>m;int ans=0;
            if((r-l+1)%2){
              int mid = l+(r-l+1)/2;
                int sum = f1.query(mid)-f1.query(l-1);
                int sum2 = f1.query(r)-f1.query(mid-1);
                ans+=f2.query(mid)-f2.query(l-1);
                ans-=sum*(l-1);
                ans+=f3.query(n-mid+1)-f3.query(n-r);
                ans-=sum2*(n-r);
            }
            else{
                int mid = l-1+(r-l+1)/2;
                int sum = f1.query(mid)-f1.query(l-1);
                int sum2 = f1.query(r)-f1.query(mid);
                //cout<<"sum = "<<sum<<", sum2 = "<<sum2<<"\n";
                ans+=f2.query(mid)-f2.query(l-1);
                //cout<<f2.query(mid)-f2.query(l-1)<<"\n";
                ans-=sum*(l-1);
                //cout<<ans<<"\n";
                ans+=f3.query(n-mid)-f3.query(n-r);
                //cout<<f3.query(n-mid)<<"\n";
                //cout<<f3.query(n-r)<<"\n";
                ans-=sum2*(n-r);
            }
            cout<<ans<<"\n";
        }
    }

return 0;
}

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