이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5;
int n, k, q, a[maxn+5], b[maxn+5], st_pref[4*maxn+5], st_preg[4*maxn+5], st_gerp[4*maxn+5], pos[maxn+5];
void up_pref(int id, int ss, int se, int po, int va) {
if (ss == se) {
st_pref[id] = va;
return;
}
int mi = (ss + se)/2;
if (po <= mi) up_pref(2*id, ss, mi, po, va);
else up_pref(2*id+1, mi+1, se, po, va);
st_pref[id] = st_pref[2*id] + st_pref[2*id+1];
}
void up_preg(int id, int ss, int se, int po, int va) {
if (ss == se) {
st_preg[id] = ss*va;
return;
}
int mi = (ss + se)/2;
if (po <= mi) up_preg(2*id, ss, mi, po, va);
else up_preg(2*id+1, mi+1, se, po, va);
st_preg[id] = st_preg[2*id] + st_preg[2*id+1];
}
void up_gerp(int id, int ss, int se, int po, int va) {
if (ss == se) {
st_gerp[id] = (n-ss+1)*va;
return;
}
int mi = (ss + se)/2;
if (po <= mi) up_gerp(2*id, ss, mi, po, va);
else up_gerp(2*id+1, mi+1, se, po, va);
st_gerp[id] = st_gerp[2*id] + st_gerp[2*id+1];
}
int pref(int id, int ss, int se, int qs, int qe) {
if (qs <= ss && se <= qe) return st_pref[id];
if (se < qs || qe < ss) return 0;
int mi = (ss + se)/2;
return pref(2*id, ss, mi, qs, qe) + pref(2*id+1, mi+1, se, qs, qe);
}
int preg(int id, int ss, int se, int qs, int qe) {
if (qs <= ss && se <= qe) return st_preg[id];
if (se < qs || qe < ss) return 0;
int mi = (ss + se)/2;
return preg(2*id, ss, mi, qs, qe) + preg(2*id+1, mi+1, se, qs, qe);
}
int gerp(int id, int ss, int se, int qs, int qe) {
if (qs <= ss && se <= qe) return st_gerp[id];
if (se < qs || qe < ss) return 0;
int mi = (ss + se)/2;
return gerp(2*id, ss, mi, qs, qe) + gerp(2*id+1, mi+1, se, qs, qe);
}
signed main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> k;
for (int i=1; i<=n; i++) {
cin >> a[i];
up_pref(1, 1, n, i, a[i]);
up_preg(1, 1, n, i, a[i]);
up_gerp(1, 1, n, i, a[i]);
}
cin >> q;
while (q--) {
int t;
cin >> t;
if (t == 1) {
for (int i=1; i<=k; i++) {
cin >> pos[i];
}
for (int i=1; i<=k; i++) {
b[pos[i]] = a[ pos[(i+1)%k + (i==k-1)] ];
up_pref(1, 1, n, pos[i], a[ pos[(i+1)%k + (i==k-1)] ]);
up_preg(1, 1, n, pos[i], a[ pos[(i+1)%k + (i==k-1)] ]);
up_gerp(1, 1, n, pos[i], a[ pos[(i+1)%k + (i==k-1)] ]);
}
for (int i=1; i<=k; i++) {
a[pos[i]] = b[pos[i]];
}
}
else {
int l, r, m;
cin >> l >> r >> m;
int len = r - l + 1;
int h = min(len-m+1, m);
int x = l + h - 1, y = r - h + 1;
int ans = h*pref(1, 1, n, x, y) + preg(1, 1, n, l, x-1) - (l-1)*pref(1, 1, n, l, x-1) + gerp(1, 1, n, y+1, r) - (n-r)*pref(1, 1, n, y+1, r);
cout << ans << "\n";
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |