Submission #1209820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209820		sunflower	Addk (eJOI21_addk)	C++17	100 / 100	122 ms	8004 KiB

Main

#include <bits/stdc++.h>
using namespace std;

int n, numPerm, q;

#define MAX_N 100'100
int a[MAX_N + 2];
int id[12];
long long pre[MAX_N + 2], sum[MAX_N + 2];

struct node {
  long long pre, sum;

  node operator + (const node &other) const {
    return {pre + other.pre, sum + other.sum};
  }
};

struct Segtree {
  node seg[4 * MAX_N + 7];

  void build(int id, int l, int r) {
    if (l == r) {
      seg[id].pre = a[l];
      seg[id].sum = 1LL * a[l] * l;
      return;
    }

    int g = (l + r) >> 1;
    build(id << 1, l, g);
    build(id << 1 | 1, g + 1, r);

    seg[id] = seg[id << 1] + seg[id << 1 | 1];
  }

  void update(int id, int l, int r, int pos, int val) {
    while (l < r) {
      int g = (l + r) >> 1;
      if (pos <= g) {
        id = 2 * id;
        r = g;
      } else {
        id = 2 * id + 1;
        l = g + 1;
      }
    }

    seg[id].pre = val;
    seg[id].sum = 1LL * pos * val;

    while (id > 1) {
      id >>= 1;
      seg[id] = seg[id << 1] + seg[id << 1 | 1];
    }
  }

  node get(int id, int l, int r, int u, int v) {
    if (l > v || u > r) return {0, 0};
    if (u <= l && r <= v) return seg[id];
    int g = (l + r) >> 1;
    return get(id << 1, l, g, u, v) + get(id << 1 | 1, g + 1, r, u, v);
  }

  void update(int pos, int val) {
    update(1, 1, n, pos, val);
  }

  node get(int l, int r) {
    return get(1, 1, n, l, r);
  }
} st;

#undef MAX_N

int main() {
  ios_base::sync_with_stdio(false);cin.tie(nullptr);
//  freopen("test.inp","r",stdin);
//  freopen("test.out","w",stdout);
  cin >> n >> numPerm;
  pre[0] = sum[0] = 0;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    pre[i] = pre[i - 1] + a[i];
    sum[i] = sum[i - 1] + 1LL * a[i] * i;
  }

  st.build(1, 1, n);

  cin >> q;
  while (q--) {
    int type;
    cin >> type;
    if (type == 1) {
      for (int i = 1; i <= numPerm; ++i) cin >> id[i];

      if (numPerm == 1) continue;

      int tmp = a[id[1]];
      for (int i = 1; i < numPerm; ++i) {
        a[id[i]] = a[id[i + 1]];
        st.update(id[i], a[id[i]]);
      }

      a[id[numPerm]] = tmp;
      st.update(id[numPerm], a[id[numPerm]]);
    } else {
      int L, R, range;
      cin >> L >> R >> range;
      if (R - L + 1 < range) {cout << "0\n"; continue;}

      int num = (R - L + 1) - range + 1;

      range = min(range, num);

      long long ans = 0;
      int pref = L + range - 2;

      node T1 = st.get(L, pref);

//      ans += sum[pref] - sum[L - 1] - 1LL * (L - 1) * (pre[pref] - pre[L - 1]);
      ans += T1.sum - 1LL * (L - 1) * T1.pre;

      L = pref + 1;

      int rig = max(pref + 1, R - range + 2);
      if (rig <= R) {
        node T2 = st.get(rig, R);

        ans += 1LL * (R + 1) * T2.pre - T2.sum;
      }

      R = rig - 1;
      if (L <= R) {
        node T3 = st.get(L, R);
        ans += 1LL * range * T3.pre;
      }

      cout << ans << "\n";
    }
  }

  return 0;
}

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