Elegant violence.
introduce
link。
This question can obviously be solved using line segment trees and tree arrays, but what if I don’t use these data structures?
We know that brute force modification and querying are the worst\(\mathcal{O}(n)\)Yes, it will definitely crash.
So what to do?
Main topic
Chunking
Consider dividing the sequence into several blocks, and let us set the length of each block to\(B\)。
for each query\(\left [ l, r \right ]\), the block we involve modifying is\(\left [ b_l, b_r \right ]\)（\(b_i\)represent\(i\)which block it belongs to).
in\(\left [ b_l + 1, b_r - 1 \right ]\)The entire piece has been modified.
You might as well set up a lazy flag and add the entire operation of each block to it.
The complexity of this modification is\(\mathcal{O}(\frac{n}{B})\)of.
Then we can perform brute force operations on the rest, and the complexity is\(\mathcal{O}(B)\)of.
Query is the same.
At this point, the complexity of modifying the query becomes\(\mathcal{O}(B + \frac{n}{B})\).
The one that minimizes this number is obviously\(B = \sqrt{n}\), so the time complexity of the algorithm is\(\mathcal{O}(m\sqrt{n})\)。
Blocking mainly solves the problem of district repair and classification, as long as the following conditions are met:
- Can be marked lazily (associative law).
- Time complexity allows.
Advantages: Can solve a wide range of problems.
Disadvantages: High time complexity.
Time complexity:\(\mathcal{O}(m\sqrt{n})\)。
Space complexity:\(\mathcal{O}(n)\)。
Team Mo
Ordinary Mo team
Team Mo is an offline algorithm and needs to meet the following conditions:
- In knowing\(\left [ l, r \right ]\)In the case of the answer, you can\(\mathcal{O}(1)\)find out\(\left [ l, r + 1 \right ]\)、 \(\left [ l, r - 1 \right ]\)、 \(\left [ l + 1, r \right ]\)、 \(\left [ l - 1, r \right ]\)answer.
- Allow offline.
- Only inquiry without modification.
First, take all inquiries offline and record them as\(\left [ ql_1, qr_1 \right ],\left [ ql_2, qr_2 \right ],\dots,\left [ ql_m, qr_m \right ]\)。
Sort the queries (this is the essence of Team Mo's algorithm), change the answers from the previous query to the current query one by one, and get the answer.
accomplish:
for (int i = 1; i <= m; i++) {
while (l < q[i].l) del(l++);
while (r > q[i].r) del(r--);
while (l > q[i].l) add(--l);
while (r < q[i].r) add(++r);
ans[q[i].id] = res;
}
However, careful analysis shows that the time complexity can still be stuck\(nm\), not excellent at all, even slower.
Consider optimizing。
The fundamental thing we want to optimize the complexity is to let\(l\)and\(r\)The pointer moves as little distance as possible.
Divide the query range into blocks with a block length of\(B\)。
The block number of the left endpoint of the query is used as the first keyword, and the right endpoint is sorted as the second keyword.
- If the current query is in the same block as the last time, then\(l\)Most moves\(B\)。
- queries for different blocks,\(l\)Most moves\(2B\)。
but:
- \(l\)The complexity of the move is\(m\times B = mB\)；
- \(r\)The complexity is\(\frac{n}{B} \times n = \frac{n^2}{B}\)。
Then the complexity is\(\mathcal{O}(mB + \frac{n^2}{B})\)。
so that the formula is minimized\(B\)The value is\(\frac{n}{\sqrt m}\), then the time complexity at this time is\(\mathcal{O}(n\sqrt{m} + m\log m)\)。
\(m \log m\)is the complexity of sorting.
To summarize.
The problems solved by the ordinary Mo team meet the following conditions:
- In knowing\(\left [ l, r \right ]\)In the case of the answer, you can\(\mathcal{O}(1)\)find out\(\left [ l, r + 1 \right ]\)、 \(\left [ l, r - 1 \right ]\)、 \(\left [ l + 1, r \right ]\)、 \(\left [ l - 1, r \right ]\)answer.
- Allow offline.
- Only inquiry without modification.
Advantages: Before there was any faster thinking method, she was almost the fastest runner and had the lowest level of thinking.
Disadvantages: Only supports offline.
Time complexity:\(\mathcal{O}(n\sqrt{m} + m\log m)\)。
Space complexity:\(\mathcal{O}(n)\)。
Example 1:Little B’s inquiry
It's a very stupid thing, please maintain it.\(c\)Just an array.
// #define int long long
#define pii pair
#define FRE(x) freopen(x ".in", "r", stdin), freopen(x ".out", "w", stdout)
#define ALL(x) (), ()
using namespace std;
int _test_ = 1;
const int N = 50008;
int n, m, k, block_size, res, cnt[N], a[N], ans[N];
struct node {
int l, r, id;
} q[N];
bool operator<(node x, node y) {
int xl = ( - 1) / block_size + 1, xr = ( - 1) / block_size + 1;
int yl = ( - 1) / block_size + 1, yr = ( - 1) / block_size + 1;
return (xl != yl) ? (xl < yl) : ( < );
}
void add(int x) {
res += cnt[a[x]] * 2 + 1;
cnt[a[x]]++;
}
void del(int x) {
res -= cnt[a[x]] * 2 - 1;
cnt[a[x]]--;
}
void init() {}
void clear() {}
void solve() {
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
block_size = n / sqrt(m); // block length
for (int i = 1; i <= m; i++) {
cin >> q[i].l >> q[i].r;
q[i].id = i;
}
sort(q + 1, q + m + 1);
int l = 1, r = 0;
for (int i = 1; i <= m; i++) {
while (l < q[i].l) del(l++);
while (r > q[i].r) del(r--);
while (l > q[i].l) add(--l);
while (r < q[i].r) add(++r);
ans[q[i].id] = res;
}
for (int i = 1; i <= m; i++) {
cout << ans[i] << "\n";
}
}
signed main() {
ios::sync_with_stdio(0);
(0), (0);
// cin >> _test_;
init();
while (_test_--) {
clear();
solve();
}
return 0;
} However, the length of this question block is\(1\)All can be there\(700\)If it passes within milliseconds, the data is too watery.
Example 2:Little Z's socks
It’s also very clumsy, please maintain it.\(c\)Array, and record the answer in the previous question in the numerator and denominator respectively.
Please note that the numerator is\(0\)situation.
#include <bits/stdc++.h>
// #define int long long
#define pii pair<int, int>
#define FRE(x) freopen(x ".in", "r", stdin), freopen(x ".out", "w", stdout)
#define ALL(x) (), ()
using namespace std;
int _test_ = 1;
const int N = 500008;
int n, m, k, block_size, len;
pii res;
int cnt[N], a[N];
pii ans[N];
struct node {
int l, r, id;
} q[N];
bool operator<(node x, node y) {
int xl = ( - 1) / block_size + 1, xr = ( - 1) / block_size + 1;
int yl = ( - 1) / block_size + 1, yr = ( - 1) / block_size + 1;
return (xl != yl) ? (xl < yl) : ( < );
}
void add(int x) {
+= cnt[a[x]];
+= len;
len++;
cnt[a[x]]++;
}
void del(int x) {
len--;
cnt[a[x]]--;
-= cnt[a[x]];
-= len;
}
void init() {}
void clear() {}
void solve() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
block_size = n / sqrt(m);
for (int i = 1; i <= m; i++) {
cin >> q[i].l >> q[i].r;
q[i].id = i;
}
sort(q + 1, q + m + 1);
int l = 1, r = 0;
for (int i = 1; i <= m; i++) {
if (q[i].l == q[i].r) ans[q[i].id] = {0, 1};
while (l < q[i].l) del(l++);
while (r > q[i].r) del(r--);
while (l > q[i].l) add(--l);
while (r < q[i].r) add(++r);
if ( == 0) {
ans[q[i].id] = {0, 1};
continue;
}
int g = __gcd(, );
ans[q[i].id] = { / g, / g};
}
for (int i = 1; i <= m; i++) {
cout << ans[i].first << "/" << ans[i].second << "\n";
}
}
signed main() {
ios::sync_with_stdio(0);
(0), (0);
// cin >> _test_;
init();
while (_test_--) {
clear();
solve();
}
return 0;
}
Facts have proved that still\(B = \frac{n}{\sqrt{m}}\)Run the fastest.
Lead the Xiu Mo team
Since it was too awkward not to be able to bring modifications, a team called Xiu Mo appeared.
The idea of leading the repair team is similar to that of all persistent data structures.
link.
Due to the modifications, we can no longer transfer like a normal Mo team.
Consider adding a one-dimensional timestamp when iterating.
Just add or subtract modifications one by one in order each time.
At the same time, the block number where the right endpoint is located is the second keyword, and the time is the third keyword.
Time complexity and optimal block length
Let the block length be\(B\), the sequence length is\(n\), the number of inquiries is\(q\), the number of modifications is\(c\)。
- The movement of the left and right endpoints has been analyzed above, and it is\(qB + \frac{n^2}{B}\)of.
- time pointer, for each block we move at most\(c\)times, that is\(\frac{n}{B} \times \frac{n}{B} \times c = \frac{cn^2}{B^2}\)。
The total time complexity is\(\mathcal{O}(qB + \frac{n^2}{B} + \frac{cn^2}{B^2})\)。
The optimal block length is probably...
So it’s better to choose the one that looks better.
for example\(B = \sqrt[3]{n^2}\)。
So the time complexity at this time is approximately\(\mathcal{O}(\sqrt[3]{n^5})\)。
To sum up, leading the Xiu Mo team needs to meet the following conditions:
- In knowing\(\left [ l, r \right ]\)In the case of the answer, you can\(\mathcal{O}(1)\)find out\(\left [ l, r + 1 \right ]\)、 \(\left [ l, r - 1 \right ]\)、 \(\left [ l + 1, r \right ]\)、 \(\left [ l - 1, r \right ]\)answer.
- Allow offline.
Advantages: Modification is allowed.
Disadvantages: Slower than the thinking method and only available offline. ,
Time complexity:\(\mathcal{O}(n\log n + \sqrt[3]{n^5})\)。
Space complexity:\(\mathcal{O}(n)\)。
Example 1:Count Color/Maintenance Queue
Just follow the simulation written above.
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define FRE(x) freopen(x ".in", "r", stdin), freopen(x ".out", "w", stdout)
#define ALL(x) (), ()
using namespace std;
int _test_ = 1;
const int N = 2e6 + 5;
int n, m, block_size, cnt_c, cnt_q, a[N], bel[N], cnt[N], ans[N], res;
struct query {
int l, r, t, id;
} c[N], q[N];
bool operator<(query x, query y) {
return (bel[] != bel[]) ? ( < ) : ((bel[] != bel[]) ? ( < ) : ( < ));
}
void build() {
block_size = pow(n, 0.666);
for (int i = 1; i <= n; i++) {
bel[i] = (i - 1) / block_size + 1;
}
}
void add(int x) {
res += (cnt[x] == 0);
cnt[x]++;
}
void del(int x) {
cnt[x]--;
res -= (cnt[x] == 0);
}
void upt(int x, int y) {
if (q[y].l <= c[x].l && c[x].l <= q[y].r) {
del(a[c[x].l]);
add(c[x].r);
}
swap(a[c[x].l], c[x].r);
}
void init() {}
void clear() {}
void solve() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
build();
for (int i = 1; i <= m; i++) {
char op;
int l, r;
cin >> op >> l >> r;
if (op == 'Q') q[++cnt_q] = {l, r, cnt_c, cnt_q};
else c[++cnt_c] = {l, r, 0, 0};
}
sort(q + 1, q + cnt_q + 1);
int l = 1, r = 0, t = 0;
for (int i = 1; i <= cnt_q; i++) {
while (l > q[i].l) add(a[--l]);
while (r < q[i].r) add(a[++r]);
while (l < q[i].l) del(a[l++]);
while (r > q[i].r) del(a[r--]);
while (t < q[i].t) upt(++t, i);
while (t > q[i].t) upt(t--, i);
ans[q[i].id] = res;
}
for (int i = 1; i <= cnt_q; i++) cout << ans[i] << "\n";
}
signed main() {
ios::sync_with_stdio(0);
(0), (0);
// cin >> _test_;
init();
while (_test_--) {
clear();
solve();
}
return 0;
}