fork(1) download
copy 
  1. #pragma GCC optimize("Ofast")
  2. #pragma GCC target("avx")
  3.  
  4. #include <iostream>
  5. #include <iomanip>
  6. #include <algorithm>
  7. #include <assert.h>
  8. #include <immintrin.h>
  9.  
  10. struct SqrtDecomposition {
  11.  
  12.     const int nGroups;
  13.  
  14.     int *gcnt;
  15.  
  16.     int *data;
  17.  
  18.     static const int gsize = 256;
  19.  
  20.     SqrtDecomposition(const int n) : nGroups((n + gsize - 1) / gsize) {
  21.         gcnt = (int*)_mm_malloc(nGroups * sizeof(int), 32);
  22.         data = (int*)_mm_malloc(n * sizeof(int), 32);
  23.         std::fill(data, data + n, 0);
  24.         std::fill(gcnt, gcnt + nGroups, 0);
  25.     }
  26.  
  27.     void inc(int pos, int delta) {
  28.         gcnt[pos / gsize] += (int)delta;
  29.         data[pos] += (int)delta;
  30.     }
  31.  
  32.     ~SqrtDecomposition() {
  33.         _mm_free(data);
  34.         _mm_free(gcnt);
  35.     }
  36.  
  37. };
  38.  
  39. namespace Solution {
  40.  
  41.     const int NMAX = 100000;
  42.  
  43.     const int blockSize = 1024;
  44.  
  45.     const int MaxNBlocks = (NMAX + blockSize - 1) / blockSize;
  46.  
  47.     SqrtDecomposition* cntTillBorder[MaxNBlocks];
  48.  
  49.     SqrtDecomposition* zeroBuffer;
  50.  
  51.     int* arr;
  52.  
  53.     int n, nBlocks;
  54.  
  55.     void alloc(int n_) {
  56.         n = n_;
  57.         nBlocks = (n + blockSize - 1) / blockSize;
  58.         arr = (int*)_mm_malloc(n * sizeof(int), 32);
  59.         zeroBuffer = new SqrtDecomposition(n);
  60.         for (int i = 0; i < nBlocks; ++i) {
  61.             cntTillBorder[i] = new SqrtDecomposition(n);
  62.         }
  63.     }
  64.  
  65.     void free() {
  66.         delete zeroBuffer;
  67.         _mm_free(arr);
  68.         for (int i = 0; i < nBlocks; ++i) {
  69.             delete cntTillBorder[i];
  70.         }
  71.     }
  72.  
  73.     void precalc() {
  74.         for (int i = 0; i < n; ++i) {
  75.             int value = (int)arr[i];
  76.             for (int b = i / blockSize; b < nBlocks; ++b) {
  77.                 cntTillBorder[b]->inc(value, +1);
  78.             }
  79.         }
  80.     }
  81.  
  82.     void naiveUpdateItems(int begin, int after, int x, int y) {
  83.         int cnt = 0;
  84.         for (int i = begin; i < after; ++i) {
  85.             cnt += (arr[i] == x);
  86.             arr[i] = (arr[i] == x) ? y : arr[i];
  87.         }
  88.         for (int b = begin / blockSize; b < nBlocks; ++b) {
  89.             cntTillBorder[b]->inc(int(x), -cnt);
  90.             cntTillBorder[b]->inc(int(y), +cnt);
  91.         }
  92.     }
  93.  
  94.     void modify(int lt, int rt, int x, int y) {
  95.         int bl = lt / blockSize;
  96.         int br = rt / blockSize;
  97.         if (bl == br) {
  98.             naiveUpdateItems(lt, rt+1, x, y);
  99.             return;
  100.         }
  101.         int changes = 0;
  102.         for (int i = lt; i < (bl+1) * blockSize; ++i) {
  103.             changes += (arr[i] == x);
  104.             arr[i] = (arr[i] == x) ? y : arr[i];
  105.         }
  106.         cntTillBorder[bl]->inc(int(x), -changes);
  107.         cntTillBorder[bl]->inc(int(y), +changes);
  108.  
  109.         for (int b = bl + 1; b < br; ++b) {
  110.             int* blockBegin = arr + b * blockSize;
  111.             for (int i = 0; i < blockSize; ++i) {
  112.                 changes += blockBegin[i] == x;
  113.                 blockBegin[i] = blockBegin[i] == x ? y : blockBegin[i];
  114.             }
  115.             cntTillBorder[b]->inc(int(x), -changes);
  116.             cntTillBorder[b]->inc(int(y), +changes);
  117.         }
  118.  
  119.         for (int i = br * blockSize; i <= rt; ++i) {
  120.             changes += (arr[i] == x);
  121.             arr[i] = (arr[i] == x) ? y : arr[i];
  122.         }
  123.         for (int b = br; b < nBlocks; ++b) {
  124.             cntTillBorder[b]->inc(int(x), -changes);
  125.             cntTillBorder[b]->inc(int(y), +changes);
  126.         }
  127.  
  128.     }
  129.  
  130.     int nth_element(int lt, int rt, int k) {
  131.         int bl = lt / blockSize;
  132.         int br = rt / blockSize;
  133.         SqrtDecomposition* arrLT = (bl == 0) ? zeroBuffer : cntTillBorder[bl-1];
  134.         SqrtDecomposition* arrRT = cntTillBorder[br];
  135.         for (int i = rt+1; i < std::min((br+1) * blockSize, n); ++i) { arrRT->inc((int)arr[i], -1); }
  136.         for (int i = bl * blockSize; i < lt; ++i) { arrLT->inc((int)arr[i], +1); }
  137.         int last = -1;
  138.         static const int STEP = SqrtDecomposition::gsize;
  139.         for (int g = 0; g < arrLT->nGroups; ++g) {
  140.             int cnt = int(arrRT->gcnt[g] - arrLT->gcnt[g]);
  141.             if (cnt >= k) { last = g * STEP - 1; break; }
  142.             k -= cnt;
  143.             last = g * STEP + STEP - 1;
  144.         }
  145.  
  146.         int cnt = 0;
  147.         while (cnt < k) { last++; cnt += int(arrRT->data[last] - arrLT->data[last]); }
  148.         for (int i = bl * blockSize; i < lt; ++i) { arrLT->inc((int)arr[i], -1); }
  149.         for (int i = rt+1; i < std::min((br+1) * blockSize, n); ++i) { arrRT->inc((int)arr[i], +1); }
  150.         return last;
  151.     }
  152. }
  153.  
  154. char getChar() {
  155.     static const int SIZE = 1 << 16;
  156.     static char buffer[SIZE];
  157.     static int pos = 0;
  158.     static int size = 0;
  159.     if (pos == size) {
  160.         size = (int)fread(buffer, 1, SIZE, stdin),
  161.         pos = 0;
  162.     }
  163.     if (pos == size) {
  164.         return EOF;
  165.     }
  166.     return buffer[pos++];
  167. }
  168.  
  169. template<typename T>
  170. T getInt() {
  171.     char c = '?';
  172.     while (!(c == '-' || ('0' <= c && c <= '9'))) { c = getChar(); }
  173.     bool pos = true;
  174.     if (c == '-') { pos = false; c = getChar(); }
  175.     T ret = 0;
  176.     while ('0' <= c && c <= '9') { (ret *= 10) += (c - '0'); c = getChar(); }
  177.     return pos ? ret : -ret;
  178. }
  179.  
  180. void putChar(char c) {
  181.     static const int SIZE = 1 << 16;
  182.     static char buffer[SIZE];
  183.     static int size = 0;
  184.     if (size == SIZE || c == EOF) {
  185.         fwrite(buffer, 1, size, stdout),
  186.         size = 0;
  187.     }
  188.     if (c != EOF) { buffer[size++] = c; }
  189. }
  190.  
  191. template<typename T>
  192. void putInt(T value) {
  193.     bool pos = true;
  194.     if (value < 0) { pos = false; value = -value; }
  195.     static char buf[24];
  196.     int size = 0;
  197.     do { buf[size++] = char(value % 10 + '0'); value /= 10; } while (value > 0);
  198.     if (!pos) { buf[size++] = '-'; }
  199.     while (size--) { putChar(buf[size]); }
  200. }
  201.  
  202. #include <random>
  203.  
  204. void stressTest() {
  205.     int n = 100000, q = 100000;
  206.     Solution::alloc(n);
  207.     for (int i = 0; i < n; ++i) {
  208.         Solution::arr[i] = int(n-1);
  209.     }
  210.     Solution::precalc();
  211.     std::mt19937 gen;
  212.     std::uniform_int_distribution<int> dist(0, n-1);
  213.     int last = n-1;
  214.     uint64_t sum = 0;
  215.     for (int id = 0; id < q; ++id) {
  216.         if (id % 2 == 0) {
  217.             int l = dist(gen);
  218.             int r = dist(gen);
  219.             if (l > r) { std::swap(l, r); }
  220.             auto res = Solution::nth_element(l, r, (r-l+1));
  221.             assert(res == last);
  222.             sum += res;
  223.         } else {
  224.             int x = last;
  225.             int y = (n-1) + (n-2) - last;
  226.             Solution::modify(0, n-1, x, y);
  227.             last = y;
  228.         }
  229.     }
  230.     assert(sum != 0);
  231.     Solution::free();
  232.     std::exit(0);
  233. }
  234.  
  235. int main() {
  236.     //stressTest();
  237.  
  238.     int n = getInt<int>(), q = getInt<int>();
  239.     Solution::alloc(n);
  240.     for (int i = 0; i < n; ++i) {
  241.         Solution::arr[i] = (int)(getInt<int>()-1);
  242.     }
  243.     Solution::precalc();
  244.  
  245.     while (q--) {
  246.         int t = getInt<int>();
  247.         if (t == 1) {
  248.             int lt = getInt<int>()-1, rt = getInt<int>()-1, x = getInt<int>()-1, y = getInt<int>()-1;
  249.             Solution::modify(lt, rt, (int)x, (int)y);
  250.         } else {
  251.             int lt = getInt<int>()-1, rt = getInt<int>()-1, k = getInt<int>();
  252.             putInt(Solution::nth_element(lt, rt, k)+1);
  253.             putChar('\n');
  254.             assert(t == 2);
  255.         }
  256.     }
  257.     putChar(EOF);
  258.     Solution::free();
  259.     return 0;
  260. }
  261.  
Success #stdin #stdout 0s 15368KB
comments (?)
stdin
copy 
3 3
2 3 3
2 1 3 1
1 1 3 3 1
2 1 3 2
stdout
copy 
2
1
https://ideone.com/5uMTfM
language:
C++14 (gcc 8.3)
created:
5 years 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!