제출 #1266364

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1266364		PlayVoltz	Addk (eJOI21_addk)	C++20	100 / 100	1266 ms	40092 KiB

Main

#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
using namespace std;

#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

struct node{
	int s, e, m, val;
	node *l, *r;
	
	node(int S, int E){
		s = S, e = E, m = (s+e)/2;
		val=0;
		if (s!=e){
			l = new node(s, m);
			r = new node(m+1, e);
		}
	}
	void up(int ind, int nv){
		if (s==e)val=nv;
		else{
			if (ind<=m)l->up(ind, nv);
			else r->up(ind, nv);
			val = l->val+r->val;
		}
	}
	int query(int left, int right){
		if (left>right)return 0;
		if (s==left && e==right)return val;
		if (right<=m)return l->query(left, right);
		else if (left>m)return r->query(left, right);
		else return l->query(left, m)+r->query(m+1, right);
	}
}*st, *st2, *st3;

int32_t main(){
	int n, k, q, a, l, r, m;
	cin>>n>>k;
	vector<int> vect(n+1), change(k), nv(k);
	st = new node(1, n);
	st2 = new node(1, n);
	st3 = new node(1, n);
	for (int i=1; i<=n; ++i)cin>>vect[i], st->up(i, vect[i]), st2->up(i, vect[i]*i), st3->up(i, vect[i]*(n-i+1));
	cin>>q;
	while (q--){
		cin>>a;
		if (a==1){
			for (int i=0; i<k; ++i)cin>>change[i];
			for (int i=0; i<k; ++i)nv[i]=vect[change[(i+1)%k]];
			for (int i=0; i<k; ++i){
				st->up(change[i], nv[i]);
				st2->up(change[i], change[i]*nv[i]);
				st3->up(change[i], (n-change[i]+1)*nv[i]);
				vect[change[i]]=nv[i];
			}
		}
		else{
			cin>>l>>r>>m;
			int high=min(m, r-l-m+2), ans=0;
			ans+=st2->query(l, l+high-2)-(l-1)*st->query(l, l+high-2);
			ans+=st3->query(r-high+2, r)-(n-r)*st->query(r-high+2, r);
			ans+=st->query(l+high-1, r-high+1)*high;
			cout<<ans<<"\n";
		}
	}
}

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