G

Kornyachka

public
Guest Jan 04, 2024 Never 61
Clone
C++ paste1.cpp 136 lines (123 loc) | 3.67 KB
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
};