fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define MAX 200005
  5. int a[MAX], SongNghi[MAX];
  6. int cost[MAX], st[4 * MAX];
  7. long long cnt[MAX], diffArr[MAX]; // cnt for number of segments using edge i
  8. int n;
  9.  
  10. map<int, int> iniPos, afterPos;
  11. long long iniCost;
  12.  
  13. void build(int id, int l, int r) {
  14.     if (l == r) {
  15.         st[id] = cost[l];
  16.         return;
  17.     }
  18.     int mid = (l + r) / 2;
  19.     build(2 * id, l, mid);
  20.     build(2 * id + 1, mid + 1, r);
  21.     st[id] = st[2 * id] + st[2 * id + 1];
  22. }
  23.  
  24. void update(int id, int l, int r, int index, int value) {
  25.     if (l > index || r < index) return;
  26.     if (l == r) {
  27.         st[id] = value;
  28.         return;
  29.     }
  30.     int mid = (l + r) / 2;
  31.     update(2 * id, l, mid, index, value);
  32.     update(2 * id + 1, mid + 1, r, index, value);
  33.     st[id] = st[2 * id] + st[2 * id + 1];
  34. }
  35.  
  36. int getSum(int id, int l, int r, int u, int v) {
  37.     if (l > v || r < u) return 0;
  38.     if (l >= u && r <= v) return st[id];
  39.     int mid = (l + r) / 2;
  40.     return getSum(2 * id, l, mid, u, v) + getSum(2 * id + 1, mid + 1, r, u, v);
  41. }
  42.  
  43. int calcCost(int l, int r) {
  44.     if (l > r) swap(l, r);
  45.     if (l == r) return 0;
  46.     return getSum(1, 1, n - 1, l, r - 1);
  47. }
  48.  
  49. void solve() {
  50.     scanf("%d", &n);
  51.     for (int i = 1; i <= n; i++) {
  52.         scanf("%d", &a[i]);
  53.         SongNghi[i] = a[i];
  54.     }
  55.     for (int i = 1; i <= n - 1; i++) scanf("%d", &cost[i]);
  56.  
  57.     build(1, 1, n - 1);
  58.  
  59.     // map initial and after positions
  60.     sort(SongNghi + 1, SongNghi + n + 1);
  61.     for (int i = 1; i <= n; i++) {
  62.         iniPos[a[i]] = i;
  63.         afterPos[SongNghi[i]] = i;
  64.     }
  65.  
  66.     // build difference array for cnt
  67.     for (int i = 1; i <= n; i++) diffArr[i] = 0;
  68.     for (int i = 1; i <= n; i++) {
  69.         int p = iniPos[a[i]];
  70.         int q = afterPos[a[i]];
  71.         if (p < q) {
  72.             diffArr[p]++;
  73.             diffArr[q]--;
  74.         } else if (q < p) {
  75.             diffArr[q]++;
  76.             diffArr[p]--;
  77.         }
  78.     }
  79.     // prefix to get cnt
  80.     cnt[0] = 0;
  81.     for (int i = 1; i <= n - 1; i++) {
  82.         cnt[i] = cnt[i - 1] + diffArr[i];
  83.     }
  84.  
  85.     // initial cost = sum cost[i] * cnt[i]
  86.     iniCost = 0;
  87.     for (int i = 1; i <= n - 1; i++) {
  88.         iniCost += cnt[i] * cost[i];
  89.     }
  90.     printf("%lld\n", iniCost);
  91.  
  92.     int q; scanf("%d", &q);
  93.     while (q--) {
  94.         int type, l, r;
  95.         scanf("%d %d %d", &type, &l, &r);
  96.         if (type == 1) {
  97.             int x = a[l];
  98.             int y = a[r];
  99.             // old contributions
  100.             long long oldX = calcCost(iniPos[x], afterPos[x]);
  101.             long long oldY = calcCost(iniPos[y], afterPos[y]);
  102.             iniCost -= (oldX + oldY);
  103.             // swap positions and values
  104.             swap(iniPos[x], iniPos[y]);
  105.             swap(a[l], a[r]);
  106.             // new contributions
  107.             long long newX = calcCost(iniPos[x], afterPos[x]);
  108.             long long newY = calcCost(iniPos[y], afterPos[y]);
  109.             iniCost += (newX + newY);
  110.         }
  111.         else if (type == 2) {
  112.             // update cost at edge l
  113.             int old = cost[l];
  114.             update(1, 1, n - 1, l, r);
  115.             cost[l] = r;
  116.             // adjust iniCost by number of segments using this edge
  117.             iniCost += cnt[l] * (long long)(r - old);
  118.         }
  119.         printf("%lld\n", iniCost);
  120.     }
  121. }
  122.  
  123. int main() {
  124.     solve();
  125.     return 0;
  126. }
  127.  
Success #stdin #stdout 0.01s 7768KB
comments (?)
stdin
copy 
3
1 3 2
1 2
2
2 2 3
1 2 3
stdout
copy 
4
6
0
https://ideone.com/8MKZU5
language:
C++14 (gcc 8.3)
created:
22 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!