fork download
copy 
  1. // WA
  2. #include <bits/stdc++.h>
  3. #define BUFFER 5
  4. #define BUFF(x) x + BUFFER
  5. #define N_MAX (int) 1e5
  6. #define Q_MAX (int) (5 * 1e5)
  7. #define BLOCKS_MAX 775
  8. #define INF (int) 1e9
  9. using namespace std;
  10. typedef long long int ll;
  11. typedef unsigned long long int ull;
  12. int n, max_val;
  13. int elements[BUFF(N_MAX)];
  14. struct {
  15.   int type;
  16.   int idx, v;
  17. } queries[BUFF(Q_MAX)];
  18. struct N {
  19.   bool type;
  20.   int idx, val;
  21. } numbers[BUFF(N_MAX + Q_MAX)];
  22. int n_ptr;
  23. int freq[BUFF(N_MAX + Q_MAX)];
  24. int freq_sum;
  25. struct {
  26.   int blk_l, blk_r;
  27.   int min_freq; // min_freq is valid iff non_zeros == (blk_r - blk_l + 1)
  28.   int non_zeros;
  29. } blocks[BUFF(BLOCKS_MAX)];
  30. int block_size, block_count;
  31. int getBlockNumber(int x) { return (x - 1) / block_size + 1; }
  32. int getBlockLeft(int blk_id) { return (blk_id - 1) * block_size + 1; }
  33. int getBlockRight(int blk_id) { return min(max_val, blk_id * block_size); }
  34. bool n_comparator(N a, N b) { return a.val < b.val; }
  35. void addToNumbers(int val, int idx, bool type) {
  36.   ++n_ptr;
  37.   numbers[n_ptr].val = val;
  38.   numbers[n_ptr].idx = idx;
  39.   numbers[n_ptr].type = type;
  40. }
  41. void applyCompression() {
  42.   int num = 0;
  43.   int diff;
  44.   for (int i = 1; i <= n_ptr; ++i) {
  45.     diff = numbers[i].val - numbers[i - 1].val;
  46.     if (diff == 1)
  47.       ++num;
  48.     else if (diff > 1)
  49.       num += 2;
  50.     if (numbers[i].type)
  51.       queries[numbers[i].idx].v = num;
  52.     else {
  53.       elements[numbers[i].idx] = num;
  54.       ++freq[num];
  55.     }
  56.   }
  57.   max_val = num;
  58. }
  59. void calculateForBlock(int blk_id) {
  60.   blocks[blk_id].non_zeros = 0;
  61.   blocks[blk_id].min_freq = INF;
  62.   for (int i = blocks[blk_id].blk_l; i <= blocks[blk_id].blk_r; ++i) {
  63.     if (freq[i]) {
  64.       ++blocks[blk_id].non_zeros;
  65.       blocks[blk_id].min_freq = min(blocks[blk_id].min_freq, freq[i]);
  66.     }
  67.   }
  68. }
  69. void buildBlocks() {
  70.   block_size = ceil(sqrt(max_val));
  71.   block_count = getBlockNumber(max_val);
  72.   for (int blk_id = 1; blk_id <= block_count; ++blk_id) {
  73.     blocks[blk_id].blk_l = getBlockLeft(blk_id);
  74.     blocks[blk_id].blk_r = getBlockRight(blk_id);
  75.     calculateForBlock(blk_id);
  76.   }
  77. }
  78. int freqTowardsLeft(int x) {
  79.   int ret = INF;
  80.   int blk_id, blk_l, blk_r;
  81.   while (x >= 1) {
  82.     blk_id = getBlockNumber(x);
  83.     blk_l = blocks[blk_id].blk_l;
  84.     blk_r = blocks[blk_id].blk_r;
  85.     if (x == blk_r && blocks[blk_id].non_zeros == (blk_r - blk_l + 1)) {
  86.       ret = min(ret, blocks[blk_id].min_freq);
  87.       x = blk_l - 1;
  88.     } else {
  89.       int i;
  90.       for (i = x; i >= blk_l && freq[i]; --i)
  91.         ret = min(ret, freq[i]);
  92.       if (i == blk_l - 1) x = blk_l - 1;
  93.       else x = 0;
  94.     }
  95.   }
  96.   return ret;
  97. }
  98. int freqTowardsRight(int x) {
  99.   int ret = INF;
  100.   int blk_id, blk_l, blk_r;
  101.   while (x <= max_val) {
  102.     blk_id = getBlockNumber(x);
  103.     blk_l = blocks[blk_id].blk_l;
  104.     blk_r = blocks[blk_id].blk_r;
  105.     if (x == blk_l && blocks[blk_id].non_zeros == (blk_r - blk_l + 1)) {
  106.       ret = min(ret, blocks[blk_id].min_freq);
  107.       x = blk_r + 1;
  108.     } else {
  109.       int i;
  110.       for (i = x; i <= blk_r && freq[i]; ++i)
  111.         ret = min(ret, freq[i]);
  112.       if (i == blk_r + 1) x = blk_r + 1;
  113.       else x = max_val + 1;
  114.     }
  115.   }
  116.   return ret;
  117. }
  118. void calculateFreq() {
  119.   int cur_min = INF;
  120.   for (int i = 1; i <= max_val; ++i) {
  121.     if (freq[i])
  122.       cur_min = min(cur_min, freq[i]);
  123.     else if (cur_min != INF) {
  124.       freq_sum += cur_min;
  125.       cur_min = INF;
  126.     }
  127.   }
  128.   if (cur_min != INF)
  129.     freq_sum += cur_min;
  130. }
  131. void reduceFrequency(int val) {
  132.   int min_left, min_right;
  133.   min_left = freqTowardsLeft(val - 1);
  134.   min_right = freqTowardsRight(val + 1);
  135.   freq_sum -= min(freq[val], min(min_left, min_right));
  136.   --freq[val];
  137.   if (freq[val])
  138.     freq_sum += min(freq[val], min(min_left, min_right));
  139.   else {
  140.     if (min_left != INF)
  141.       freq_sum += min_left;
  142.     if (min_right != INF)
  143.       freq_sum += min_right;
  144.   }
  145.   int blk_id = getBlockNumber(val);
  146.   calculateForBlock(blk_id);
  147. }
  148. void increaseFrequency(int val) {
  149.   int min_left, min_right;
  150.   min_left = freqTowardsLeft(val - 1);
  151.   min_right = freqTowardsRight(val + 1);
  152.   if (freq[val])
  153.     freq_sum -= min(freq[val], min(min_left, min_right));
  154.   else {
  155.     if (min_left != INF)
  156.       freq_sum -= min_left;
  157.     if (min_right != INF)
  158.       freq_sum += min_right;
  159.   }
  160.   ++freq[val];
  161.   freq_sum += min(freq[val], min(min_left, min_right));
  162.   int blk_id = getBlockNumber(val);
  163.   calculateForBlock(blk_id);
  164. }
  165. void program() {
  166.   int q;
  167.   scanf("%d", &n);
  168.   for (int i = 1; i <= n; ++i) {
  169.     scanf("%d", &elements[i]);
  170.     addToNumbers(elements[i], i, false);
  171.   }
  172.   scanf("%d", &q);
  173.   for (int i = 1; i <= q; ++i) {
  174.     scanf("%d", &queries[i].type);
  175.     if (queries[i].type == 1) {
  176.       scanf("%d %d", &queries[i].idx, &queries[i].v);
  177.       addToNumbers(queries[i].v, i, true);
  178.     }
  179.   }
  180.   sort(numbers + 1, numbers + 1 + n_ptr, n_comparator);
  181.   applyCompression();
  182.   buildBlocks();
  183.   calculateFreq();
  184.   for (int i = 1; i <= q; ++i) {
  185.     if (queries[i].type == 1) {
  186.       reduceFrequency(elements[queries[i].idx]);
  187.       elements[queries[i].idx] = queries[i].v;
  188.       increaseFrequency(queries[i].v);
  189.     } else printf("%d\n", freq_sum);
  190.   }
  191. }
  192. int main() {
  193.   program();
  194.   return 0;
  195. }
Success #stdin #stdout 0s 30872KB
comments (?)
stdin
copy 
7
2 7 2 7 1 2 3
4
1 5 2
2
1 7 2
2
stdout
copy 
3
7
https://ideone.com/nJap4V
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
secret

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!