제출 #1167565

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167565		fryingduc	Addk (eJOI21_addk)	C++20	100 / 100	372 ms	6432 KiB

Main

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 1e5 + 5;
int n, k, a[maxn];
long long tree[maxn << 2];
long long lazy[maxn << 2];

void down(int ind, int l = 1, int r = n) {
  tree[ind] += lazy[ind] * (r - l + 1);
  if (l != r) {
    lazy[ind << 1] += lazy[ind];
    lazy[ind << 1 | 1] += lazy[ind];
  }
  lazy[ind] = 0;
}

void update(int x, int y, int val, int ind = 1, int l = 1, int r = n) {
  if (lazy[ind]) down(ind, l, r);
  if (x > y || l > y || r < x) return;
  if (x <= l and r <= y) {
    lazy[ind] = val;
    down(ind, l, r);
    return;
  }
  int mid = (l + r) >> 1;
  update(x, y, val, ind << 1, l, mid);
  update(x, y, val, ind << 1 | 1, mid + 1, r);
  tree[ind] = tree[ind << 1] + tree[ind << 1 | 1];
}

long long get(int x, int y, int ind = 1, int l = 1, int r = n) {
  if (lazy[ind]) down(ind, l, r);
  if (x > y || l > y || r < x) return 0;
  if (x <= l and r <= y) {
    return tree[ind];
  }
  int mid = (l + r) >> 1;
  return get(x, y, ind << 1, l, mid) + get(x, y, ind << 1 | 1, mid + 1, r);
}

void solve() {
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    update(i, n, a[i]);
  }
  int q; cin >> q;
  while (q--) {
    int op; cin >> op;
    if (op == 1) {
      vector<int> t(k);
      for (auto &i : t) {
        cin >> i;
        update(i, n, -a[i]);
      }
      for (int i = 1; i < k; ++i) {
        update(t[i - 1], n, a[t[i]]);
      }
      int tmp = a[t[0]];
      update(t.back(), n, a[t[0]]);
      for (int i = 1; i < k; ++i) {
        a[t[i - 1]] = a[t[i]];
      }
      a[t.back()] = tmp;
    } else {
      int l, r, m; cin >> l >> r >> m;
      long long res = get(l + m - 1, r) - get((l > 1 ? l - 1 : 0), r - m);
      cout << res << '\n';
    }
  }
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

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