Kornyachka
public
Jan 04, 2024
Never
155
1 #include <vector> 2 #include <algorithm> 3 4 #define all(x) (x).begin(), (x).end() 5 6 // author: @noisegain 7 8 using namespace std; 9 10 const int K = 1288; // eq sqrt(nlogn) where n = 10^5 11 // because of O(sqrt(n * log(n))) instead of O(sqrt(n) * log(n)) 12 13 // [L; R) invariant for all type of queries and variables 14 15 struct sqrt_decompose { 16 vector<vector<int>> a; 17 vector<vector<int>> blocks; 18 vector<int> promise; 19 int changes = 0; 20 int n; 21 22 explicit sqrt_decompose(const vector<int> &init) { 23 n = init.size(); 24 a.push_back(init); 25 rebuild(); 26 } 27 28 void rebuild() { 29 vector<int> init; 30 init.reserve(n); 31 for (auto &x : a) { 32 init.insert(init.end(), x.begin(), x.end()); 33 } 34 a.clear(); 35 blocks.clear(); 36 changes = 0; 37 int size = (n + K - 1) / K; 38 a.resize(size); 39 blocks.resize(size); 40 for (int i = 0; i < size; ++i) { 41 a[i].reserve(K); 42 blocks[i].reserve(K); 43 } 44 promise.resize(size, 0); 45 for (int i = 0; i < n; ++i) { 46 a[i / K].push_back(init[i]); 47 blocks[i / K].push_back(init[i]); 48 } 49 for (auto &x : blocks) { 50 sort(all(x)); 51 } 52 } 53 54 void apply(int i) { 55 blocks[i].clear(); 56 for (auto &x : a[i]) { 57 x += promise[i]; 58 blocks[i].push_back(x); 59 } 60 promise[i] = 0; 61 sort(all(blocks[i])); 62 } 63 64 void erase(int ind) { 65 for (int i = 0, l = 0; i < blocks.size(); ++i) { 66 int r = l + blocks[i].size(); 67 if (ind < r) { 68 auto it = lower_bound(all(blocks[i]), a[i][ind - l]); 69 a[i].erase(a[i].begin() + (ind - l)); 70 blocks[i].erase(it); 71 break; 72 } 73 l = r; 74 } 75 --n; 76 if (++changes == K) { 77 rebuild(); 78 } 79 } 80 81 void insert(int ind, int v) { 82 for (int i = 0, l = 0, r; i < blocks.size(); ++i) { 83 r = l + blocks[i].size(); 84 if (ind <= r) { 85 auto it = upper_bound(all(blocks[i]), v); 86 a[i].insert(a[i].begin() + (ind - l), v); 87 blocks[i].insert(it, v); 88 break; 89 } 90 l = r; 91 } 92 ++n; 93 if (++changes == K) { 94 rebuild(); 95 } 96 } 97 98 void update(int l_q, int r_q, int x) { 99 for (int i = 0, l = 0, r; i < blocks.size(); i++, l = r) { 100 r = l + blocks[i].size(); 101 if (r <= l_q || r_q <= l) { 102 continue; 103 } 104 if (l >= l_q && r <= r_q) { 105 promise[i] += x; 106 continue; 107 } 108 for (int j = max(l, l_q); j < min(r, r_q); ++j) { 109 a[i][j - l] += x; 110 } 111 apply(i); 112 } 113 } 114 115 int get(int l_q, int r_q, int x, int y) { 116 int l = 0, r, cnt = 0; 117 for (int i = 0; i < blocks.size(); ++i, l = r) { 118 r = l + blocks[i].size(); 119 int nx = x - promise[i]; 120 int ny = y - promise[i]; 121 if (r <= l_q || r_q <= l) { 122 continue; 123 } 124 if (l >= l_q && r <= r_q) { 125 cnt += static_cast<int>(upper_bound(all(blocks[i]), ny) - lower_bound(all(blocks[i]), nx)); 126 continue; 127 } 128 for (int j = max(l, l_q); j < min(r, r_q); ++j) { 129 if (a[i][j - l] <= ny && a[i][j - l] >= nx) { 130 ++cnt; 131 } 132 } 133 } 134 return cnt; 135 } 136 };