제출 #638138

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
638138		Tekor	Addk (eJOI21_addk)	C++17	100 / 100	438 ms	12492 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(v) v.begin(),v.end()
#define en '\n'
void boos() {
	ios_base :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}
const int N = 3e5 + 100;
int n,k;
ll t[N * 4],t1[N * 4],t2[N * 4],a[N];
int b[N];
void merg(int v,int tl,int tr) {
	int tm = (tl + tr) / 2;
	t[v] = t[v + v] + t[v + v + 1];
	t1[v] = t1[v + v] + t1[v + v + 1] + (t[v + v + 1] * (ll)(tm - tl + 1));
	t2[v] = t2[v + v] + t2[v + v + 1] + (t[v + v] * (ll)(tr - tm));
}
void build(int v,int tl,int tr) {
	if(tl == tr) {
		t[v] = a[tl];
		t1[v] = a[tl];
		t2[v] = a[tl];
		return;
	}
	int tm = (tl + tr) / 2;
	build(v + v,tl,tm);
	build(v + v + 1,tm + 1,tr);
	merg(v,tl,tr);
}
void upd(int v,int tl,int tr,int pos,ll x) {
	if(tl == tr) {
		t[v] = x;
		t1[v] = x;
		t2[v] = x;
		return;
	}
	int tm = (tl + tr) / 2;
	if(pos <= tm)upd(v + v,tl,tm,pos,x);
	else upd(v + v + 1,tm + 1,tr,pos,x);
	merg(v,tl,tr);
}
ll get(int v,int tl,int tr,int l,int r) {
	if(tl > r || tr < l)return 0;
	if(tl >= l && tr <= r)return t[v];
	int tm = (tl + tr) / 2;
	return get(v + v,tl,tm,l,r) + get(v + v + 1,tm + 1,tr,l,r);
}
ll get1(int v,int tl,int tr,int l,int r) {
	if(tl > r || tr < l)return 0;
	if(tl >= l && tr <= r)return t1[v] + (ll)(tl - l) * t[v];
	int tm = (tl + tr) / 2;
	return get1(v + v,tl,tm,l,r) + get1(v + v + 1,tm + 1,tr,l,r);
}
ll get2(int v,int tl,int tr,int l,int r) {
	if(tl > r || tr < l)return 0;
	if(tl >= l && tr <= r)return t2[v] + (ll)(r - tr) * t[v];
	int tm = (tl + tr) / 2;
	return get2(v + v,tl,tm,l,r) + get2(v + v + 1,tm + 1,tr,l,r);
}
void solve() {
	cin >> n >> k;
	for(int i = 1;i <= n;i++) {
		cin >> a[i];
	}
	build(1,1,n);
	int q;
	cin >> q;
	for(int i = 1;i <= q;i++) {
		int typ;
		cin >> typ;
		if(typ == 1) {
			for(int j = 1;j <= k;j++)cin >> b[j];
			for(int j = 1;j <= k;j++) {
				if(j == k)upd(1,1,n,b[j],a[b[1]]);
				else upd(1,1,n,b[j],a[b[j + 1]]);
			}
			ll last = a[b[1]];
			for(int j = k;j >= 1;j--) {
				ll vv = a[b[j]];
				a[b[j]] = last;
				last = vv;
			}
		}else {
			int l,r,m;
			cin >> l >> r >> m;
			int R = min(l + m - 2,r - m),L = max(r - m + 2,l + m);
			cout << get1(1,1,n,l,R) + get(1,1,n,R + 1,L - 1) * (ll)(R - l + 2ll) + get2(1,1,n,L,r)  << en;
		}
	}
}
int main() {
	solve();
}

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