Submission #777651

#TimeUsernameProblemLanguageResultExecution timeMemory
777651ihcekerAddk (eJOI21_addk)C++14
100 / 100
257 ms8640 KiB
#include<bits/stdc++.h> #define int long long #define MOD 1000000007 #define all(x) x.begin(),x.end() #define ff first #define ss second #define pb push_back #define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); using namespace std; int n,k,f[100005],f2[100005],f3[100005]; void update(int x,int y){ for(int i=x;i<=n;i+=(i&-i)){ f[i]+=y; } return; } void update2(int x,int y){ for(int i=x;i<=n;i+=(i&-i)){ f2[i]+=y; } return; } void update3(int x,int y){ for(int i=x;i>=1;i-=((n-i+1)&(i-n-1))){ f3[i]+=y; } return; } int query(int x){ int y=0; for(int i=x;i>=1;i-=(i&-i)){ y+=f[i]; } return y; } int query2(int x){ int y=0; for(int i=x;i>=1;i-=(i&-i)){ y+=f2[i]; } return y; } int query3(int x){ int y=0; for(int i=x;i<=n;i+=((n-i+1)&(i-n-1))){ y+=f3[i]; } return y; } int32_t main(){ cin>>n>>k; int arr[n+5]; for(int i=1;i<=n;i++){ cin>>arr[i]; } for(int i=1;i<=n;i++){ update(i,arr[i]); update2(i,arr[i]*i); update3(i,arr[i]*(n-i+1)); } int q; cin>>q; while(q--){ int a; cin>>a; if(a==1){ int b[k]; for(int i=0;i<k;i++)cin>>b[i]; vector<int>v; int x=arr[b[0]]; for(int i=0;i<k-1;i++){ v.pb(arr[b[i]]); arr[b[i]]=arr[b[i+1]]; } v.pb(arr[b[k-1]]); arr[b[k-1]]=x; for(int i=0;i<k;i++){ update(b[i],arr[b[i]]-v[i]); update2(b[i],(arr[b[i]]-v[i])*b[i]); update3(b[i],(arr[b[i]]-v[i])*(n-b[i]+1)); } } else{ int x,y,z; cin>>x>>y>>z; if(z==1){ cout<<query(y)-query(x-1)<<endl; continue; } int l=x+z-1,r=y-z+1; cout<<(query(r)-query(l-1))*z+query2(l-1)-query2(x-1)-(query(l-1)-query(x-1))*(x-1)+query3(r+1)-query3(y+1)-(query(y)-query(r))*(n-y)<<endl; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...