제출 #1285366

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1285366		silence25	Addk (eJOI21_addk)	C++20	100 / 100	314 ms	8852 KiB

Main

#include "bits/stdc++.h"
#define ll long long
#define pb push_back
#define pp pop_back
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define sz(s) (ll)s.size()
using namespace std;
const ll INF = 1e9+7;
const ll maxn = 1e5+5;
ll n;
ll v[maxn];
ll s1[4*maxn];
ll s2[4*maxn];
ll s3[4*maxn];
void build(ll nd,ll s,ll e){
	if(s == e){
		s1[nd] = v[s];
		s2[nd] = v[s] * s;
		s3[nd] = v[s] * (n-s+1);
		return;
	}
	ll mid = s + (e-s)/2;
	build(2*nd,s,mid);
	build(2*nd+1,mid+1,e);
	s1[nd] = s1[2*nd] + s1[2*nd+1];
	s2[nd] = s2[2*nd] + s2[2*nd+1];
	s3[nd] = s3[2*nd] + s3[2*nd+1];
}
void update(ll nd,ll s,ll e,ll pos){
	if(s > pos || e < pos)
		return;
	if(s == e){
		s1[nd] = v[s];
		s2[nd] = v[s] * s;
		s3[nd] = v[s] * (n-s+1);
		return;
	}
	ll mid = s + (e-s)/2;
	update(2*nd,s,mid,pos);
	update(2*nd+1,mid+1,e,pos);
	s1[nd] = s1[2*nd] + s1[2*nd+1];
	s2[nd] = s2[2*nd] + s2[2*nd+1];
	s3[nd] = s3[2*nd] + s3[2*nd+1];
}
ll get(ll nd,ll s,ll e,ll l,ll r,ll tp){
	if(s > r || e < l)
		return 0;
	if(l <= s && e <= r){
		if(tp == 1)
			return s1[nd];
		else if(tp == 2)
			return s2[nd];
		else
			return s3[nd];
	}
	ll mid = s + (e-s)/2;
	return get(2*nd,s,mid,l,r,tp) + get(2*nd+1,mid+1,e,l,r,tp);
}
void solve(){
	ll k;
	cin>>n>>k;
	for(ll i = 1;i<=n;++i)
		cin>>v[i];
	build(1,1,n);
	ll q;
	cin>>q;
	while(q--){
		ll tp;
		cin>>tp;
		if(tp == 1){
			vector<ll>a(k);
			for(auto &it:a)
				cin>>it;
			ll old = v[a[0]];
			for(ll i = 0;i<k-1;++i)
				v[a[i]] = v[a[i+1]];
			v[a.back()] = old;
			for(auto it:a)
				update(1,1,n,it);
		}else{
			ll l,r,m;
			cin>>l>>r>>m;
			ll ans = 0;
			ll cnt = r-l-m+2;
			ll g = min(cnt,m);
			ll st = l + g - 1;
			ll ed = r - g + 1;
			if(st <= ed)
				ans += get(1,1,n,st,ed,1)*g;
			ll coef = 1 - l;
			if(st - 1 >= l)
				ans += get(1,1,n,l,st-1,2) + coef * get(1,1,n,l,st-1,1);
			coef = r - n;
			if(ed + 1 <= r)
				ans += get(1,1,n,ed+1,r,3) + coef * get(1,1,n,ed+1,r,1);
			cout<<ans<<endl;
		}
	}
}

int main(){
    // freopen("file.in","r",stdin);
    ios::sync_with_stdio(false);cin.tie(nullptr);
 	solve();
    return 0;
}

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