fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <cassert>
  3.  
  4. using namespace std;
  5.  
  6. #define QuocAn 0
  7. #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  8.  
  9. const int U = 400;
  10. const int B = 500;
  11.  
  12. struct elem {
  13.     int val;
  14.     int next;
  15.     int cnt;
  16. };
  17.  
  18. bool operator<(const elem &a, const elem &b) { 
  19.     return a.val < b.val; 
  20. }
  21.  
  22. elem bucket[305][905];
  23. int sz[305];
  24.  
  25. int sentinel;
  26. int b[150005];
  27. int a[150005], n, l;
  28. int q_cnt;
  29.  
  30. void bucket_label(int bnum) {
  31.     int pt = sz[bnum];
  32.     for (int i = sz[bnum] - 1; i >= 0; i--) {
  33.         while (pt && bucket[bnum][pt - 1].val > bucket[bnum][i].val + l) {
  34.             pt--;
  35.         }
  36.         if (pt == sz[bnum]) {
  37.             bucket[bnum][i].next = -1;
  38.             bucket[bnum][i].cnt = 0;
  39.         } else {
  40.             if (bucket[bnum][pt].next == -1) {
  41.                 bucket[bnum][i].next = pt;
  42.             } else {
  43.                 bucket[bnum][i].next = bucket[bnum][pt].next;
  44.             }
  45.             bucket[bnum][i].cnt = bucket[bnum][pt].cnt + 1;
  46.         }
  47.     }
  48. }
  49.  
  50. void bucket_clear() {
  51.     int piv = 0;
  52.     for (int i = 0; i < sentinel; i++) {
  53.         for (int j = 0; j < sz[i]; j++) {
  54.             b[piv++] = bucket[i][j].val;
  55.         }
  56.     }
  57.     for (int i = 0; i < sentinel; i++) {
  58.         sz[i] = min(n - i * B, B);
  59.         for (int j = 0; j < sz[i]; j++) {
  60.             elem tmp;
  61.             tmp.val = b[i * B + j];
  62.             tmp.next = 0;
  63.             tmp.cnt = 0;
  64.             bucket[i][j] = tmp;
  65.         }
  66.         bucket_label(i);
  67.     }
  68. }
  69.  
  70. void bucket_erase(int bnum, int pos) {
  71.     sz[bnum]--;
  72.     for (int i = pos; i < sz[bnum]; i++) {
  73.         bucket[bnum][i] = bucket[bnum][i + 1];
  74.     }
  75.     bucket_label(bnum);
  76. }
  77.  
  78. void bucket_update(int bnum, int pos, int val) {
  79.     sz[bnum]++;
  80.     for (int i = sz[bnum] - 1; i > pos; i--) {
  81.         bucket[bnum][i] = bucket[bnum][i - 1];
  82.     }
  83.     elem tmp;
  84.     tmp.val = val;
  85.     tmp.next = 0;
  86.     tmp.cnt = 0;
  87.     bucket[bnum][pos] = tmp;
  88.     bucket_label(bnum);
  89. }
  90.  
  91. int query() {
  92.     int pos = 0, ret = 0;
  93.     for (int i = 0; i < sentinel; ) {
  94.         if (!sz[i]) {
  95.             i++;
  96.             continue;
  97.         }
  98.  
  99.         ret += bucket[i][pos].cnt + 1;
  100.         if (bucket[i][pos].next != -1) pos = bucket[i][pos].next;
  101.  
  102.         int new_buck = i + 1;
  103.         int new_pos = bucket[i][pos].val + l;
  104.         elem target;
  105.         target.val = new_pos + 1;
  106.         target.next = 0;
  107.         target.cnt = 0;
  108.  
  109.         while (1) {
  110.             if (new_buck == sentinel) break;
  111.             if (lower_bound(bucket[new_buck], bucket[new_buck] + sz[new_buck], target) != bucket[new_buck] + sz[new_buck]) break;
  112.             new_buck++;
  113.         }
  114.  
  115.         if (new_buck == sentinel) break;
  116.         i = new_buck;
  117.         pos = (int)(lower_bound(bucket[new_buck], bucket[new_buck] + sz[new_buck], target) - bucket[new_buck]);
  118.     }
  119.     return ret;
  120. }
  121.  
  122. void init(int N, int L, int* X) {
  123.     memcpy(a, X, sizeof(int) * N);
  124.     memcpy(b, a, sizeof(int) * N);
  125.     n = N;
  126.     l = L;
  127.     while (sentinel * B < n) sentinel++;
  128.     bucket_clear();
  129. }
  130.  
  131. int update(int i, int y) {
  132.     q_cnt = (q_cnt + 1) % U;
  133.     int o = a[i];
  134.     a[i] = y;
  135.     elem target_o;
  136.     target_o.val = o;
  137.     target_o.next = 0;
  138.     target_o.cnt = 0;
  139.  
  140.     for (int idx = 0; idx < sentinel; idx++) {
  141.         if (!sz[idx]) continue;
  142.         else if (bucket[idx][0].val <= o && o <= bucket[idx][sz[idx] - 1].val) {
  143.             int pos = (int)(lower_bound(bucket[idx], bucket[idx] + sz[idx], target_o) - bucket[idx]);
  144.             bucket_erase(idx, pos);
  145.             break;
  146.         }
  147.     }
  148.     int low = -1;
  149.     for (int idx = 0; idx < sentinel; idx++) {
  150.         if (!sz[idx]) continue;
  151.         if (bucket[idx][0].val <= y) low = idx;
  152.     }
  153.     if (low == -1) {
  154.         bucket_update(0, 0, y);
  155.     } else {
  156.         elem target_y;
  157.         target_y.val = y;
  158.         target_y.next = 0;
  159.         target_y.cnt = 0;
  160.         int pos = (int)(lower_bound(bucket[low], bucket[low] + sz[low], target_y) - bucket[low]);
  161.         bucket_update(low, pos, y);
  162.     }
  163.     if (q_cnt == 0) {
  164.         bucket_clear();
  165.     }
  166.     return query();
  167. }
  168.  
  169. int main() {
  170.     fastio
  171.     int N, L, M;
  172.     if (!(cin >> N >> L >> M)) return 0;
  173.  
  174.     static int X[150005];
  175.     for (int i = 0; i < N; i++) {
  176.         cin >> X[i];
  177.     }
  178.  
  179.     init(N, L, X);
  180.  
  181.     while (M--) {
  182.         int idx, val;
  183.         cin >> idx >> val;
  184.         cout << update(idx, val) << "\n";
  185.     }
  186.  
  187.     return QuocAn;
  188. }
  189.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/9dwnSX
language:
C++14 (clang 8.0)
created:
10 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!