제출 #700174

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
700174		pera	Addk (eJOI21_addk)	C++14	100 / 100	401 ms	12472 KiB

Main

#include<bits/stdc++.h>
#include<vector>

using namespace std;

#define pb push_back
#define ll long long
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

const ll mod = 1e9 + 7 , N = 1e5 + 100;

ll n , A[N] , t[4 * N][3] , k;

void bld(ll v, ll tl, ll tr) {
    if (tl == tr) {
		t[v][0] = A[tl];
		t[v][1] = (tl + 1) * A[tl];
		t[v][2] = (n - tl) * A[tl];       
    } else {
        ll tm = (tl + tr) / 2;
        bld(v * 2 , tl, tm);
        bld(v * 2 + 1, tm + 1, tr);
    	for(int w = 0;w < 3;w ++){
    		t[v][w] = t[v * 2][w] + t[v * 2 + 1][w];
		}
	}
}

void upd(ll v, ll tl, ll tr, ll pos, ll val) {
    if (tl == tr) {
        t[v][0] = val;
        t[v][1] = (tl + 1) * val;
    	t[v][2] = (n - tl) * val;
	}else {
        ll tm = (tl + tr) / 2;
        if (pos <= tm){
            upd(v * 2 , tl , tm , pos ,val);
        }else{
            upd(v * 2 + 1 , tm + 1, tr, pos ,val);
    	}
		for(int w = 0;w < 3;w ++){
        	t[v][w] = t[v * 2][w] + t[v * 2 + 1][w];
		}
    }
}

ll sm(ll v, ll tl, ll tr, ll l, ll r , int p) {
    if (l > r) 
        return 0;
    if (l == tl && r == tr) {
        return t[v][p];
    }
    ll tm = (tl + tr) / 2;
    return sm(v * 2, tl, tm, l , min(r , tm) , p)
           + sm(v * 2 + 1 , tm + 1, tr , max(l, tm + 1) , r , p);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin >> n >> k;
	for(int i = 0;i < n;i ++){
		cin >> A[i];
	}
	bld(1 , 0 , n - 1);
	ll Q;cin >> Q;
	while(Q --){
		int tt;cin >> tt;
		if(tt == 1){
			vector<ll> inds(k) , nw;
			for(int i = 0;i < k;i ++){
				cin >> inds[i];
				-- inds[i];
				if(i) nw.pb(inds[i]);
			}
			if(k == 1){
				continue;
			}
			nw.pb(inds[0]);
			vector<ll> vls;
			for(int i = 0;i < k;i ++){
				vls.pb(A[nw[i]]);
			}
			for(int i = 0; i < k;i ++){
				A[inds[i]] = vls[i];
				upd(1 , 0 , n - 1 , inds[i] , vls[i]);
			}
		//	for(int i = 0;i < n;i ++){
		//		cout << A[i] << " ";
		//	}
		//	cout << endl;
		}else{
			ll l , r , m;cin >> l >> r >> m;
			-- l , -- r;
			ll sz = (r - l + 1);
			if(m > sz / 2){
				m = sz - m + 1;	
			}
			ll s1 = sm(1 , 0 , n - 1 , l , l + m - 2 , 1) - l * sm(1 , 0 , n - 1 , l , l + m - 2 , 0);
			ll s2 = sm(1 , 0 , n - 1 , l + m - 1 , r - m + 1 , 0) * m;
			ll s3 = sm(1 , 0 , n - 1 , r - m + 2 , r , 2) - (( n - ( r - ( m - 2 ))) - ( m - 1 )) * sm(1 , 0 , n - 1 , r - m + 2 , r , 0);
			cout << s1 + s2 + s3 << endl;
		}	
	}
}
/*
if(r - l + 1 <= (m - 1) * 2){
				ll x = l + (r - l + 1) / 2 - 1, y = x + 1;
				//cout << "X: " << x - l << " " << "Y: " << y - l << endl;
				ll s1 = sm(1 , 0 , n - 1 , l , x , 1) - sm(1 , 0 , n - 1 ,l , x , 0) * l;
				ll s2 = sm(1 , 0 , n - 1 , y , r , 2) - sm(1 , 0 , n - 1 , y , r , 0) * (n - r - 1);
				//cout << s1 << endl;
				//cout << s2 << endl;
				//cout << "ESAA PAS: ";
				cout << s1 + s2 << endl;
			}else{
				ll x = l + m - 2, y = r - m + 2;
				//cout << "X: " << x << " " << "Y: " << y << endl;
				ll s1 = sm(1 , 0 , n - 1 , x + 1 , y - 1 , 0) * m;
				ll s2 = 0 , s3 = 0;
				if(x >= l) s2 = sm(1 , 0 , n - 1 , l , x , 1) - sm(1 , 0 , n - 1 , l , x , 0) * l;
				if(y <= r) s3 = sm(1 , 0 , n - 1 , y , r , 2) - sm(1 , 0 , n - 1 , y , r , 0) * (n - r - 1);
				cout << s1 + s2 + s3 << endl;
			}
8 3
7 2 5 1 9 3 4 6
1
1 2 5 8
*/

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