Submission #1043885

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043885		kebine	Addk (eJOI21_addk)	C++17	0 / 100	98 ms	13396 KiB

Main

#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";
    }
  }
}

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