|
6559 | 6559 |
|
6560 | 6560 |
|
6561 | 6561 |
|
6562 |
| - |
6563 |
| - |
6564 |
| - |
6565 |
| - |
6566 |
| - |
6567 |
| - |
6568 |
| - |
6569 |
| - |
6570 |
| - |
6571 |
| - |
6572 |
| - |
6573 |
| - |
6574 | 6562 |
|
6575 | 6563 |
|
6576 | 6564 |
|
|
6741 | 6729 |
|
6742 | 6730 |
|
6743 | 6731 |
|
6744 |
| - |
6745 |
| - |
6746 |
| - |
6747 |
| - |
6748 | 6732 |
|
6749 | 6733 |
|
6750 | 6734 |
|
|
6757 | 6741 | <ul class="metadata page-metadata" data-bi-name="page info" lang="en-us" dir="ltr">
|
6758 | 6742 |
|
6759 | 6743 | Last update:
|
6760 |
| - <span class="git-revision-date-localized-plugin git-revision-date-localized-plugin-date">December 20, 2024</span>  |
| 6744 | + <span class="git-revision-date-localized-plugin git-revision-date-localized-plugin-date">October 1, 2024</span>  |
6761 | 6745 |
|
6762 | 6746 | <!-- Tags -->
|
6763 | 6747 |
|
@@ -6864,7 +6848,7 @@ <h2 id="mos-algorithm">Mo's algorithm<a class="headerlink" href="#mos-algorithm"
|
6864 | 6848 | During a normal sqrt decomposition, we have to precompute the answers for each block, and merge them during answering queries.
|
6865 | 6849 | In some problems this merging step can be quite problematic.
|
6866 | 6850 | E.g. when each queries asks to find the <strong>mode</strong> of its range (the number that appears the most often).
|
6867 |
| -For this each block would have to store the count of each number in it in some sort of data structure, and we can no longer perform the merge step fast enough any more. |
| 6851 | +For this each block would have to store the count of each number in it in some sort of data structure, and we cannot longer perform the merge step fast enough any more. |
6868 | 6852 | <strong>Mo's algorithm</strong> uses a completely different approach, that can answer these kind of queries fast, because it only keeps track of one data structure, and the only operations with it are easy and fast.</p>
|
6869 | 6853 | <p>The idea is to answer the queries in a special order based on the indices.
|
6870 | 6854 | We will first answer all queries which have the left index in block 0, then answer all queries which have left index in block 1 and so on.
|
@@ -6974,7 +6958,7 @@ <h2 id="practice-problems">Practice Problems<a class="headerlink" href="#practic
|
6974 | 6958 |
|
6975 | 6959 | <ul class="metadata page-metadata" data-bi-name="page info" lang="en-us" dir="ltr">
|
6976 | 6960 | <span class="contributors-text">Contributors:</span>
|
6977 |
| - <ul class="contributors" data-bi-name="contributors"><li><a href="https://github.com/madhur4127" title="madhur4127" data-bi-name="contributorprofile" target="_blank">madhur4127</a> (56.22%)</li><li><a href="https://github.com/tcNickolas" title="tcNickolas" data-bi-name="contributorprofile" target="_blank">tcNickolas</a> (25.3%)</li><li><a href="https://github.com/RodionGork" title="RodionGork" data-bi-name="contributorprofile" target="_blank">RodionGork</a> (4.02%)</li><li><a href="https://github.com/Morass" title="Morass" data-bi-name="contributorprofile" target="_blank">Morass</a> (3.61%)</li><li><a href="https://github.com/adamant-pwn" title="adamant-pwn" data-bi-name="contributorprofile" target="_blank">adamant-pwn</a> (3.21%)</li><li><a href="https://github.com/tanmay-sinha" title="tanmay-sinha" data-bi-name="contributorprofile" target="_blank">tanmay-sinha</a> (2.01%)</li><li><a href="https://github.com/wikku" title="wikku" data-bi-name="contributorprofile" target="_blank">wikku</a> (1.2%)</li><li><a href="https://github.com/gampu" title="gampu" data-bi-name="contributorprofile" target="_blank">gampu</a> (1.2%)</li><li><a href="https://github.com/ypratik817" title="ypratik817" data-bi-name="contributorprofile" target="_blank">ypratik817</a> (0.4%)</li><li><a href="https://github.com/abirc8010" title="abirc8010" data-bi-name="contributorprofile" target="_blank">abirc8010</a> (0.4%)</li><li><a href="https://github.com/jakobkogler" title="jakobkogler" data-bi-name="contributorprofile" target="_blank">jakobkogler</a> (0.4%)</li><li><a href="https://github.com/3centroids" title="3centroids" data-bi-name="contributorprofile" target="_blank">3centroids</a> (0.4%)</li><li><a href="https://github.com/mrpandey" title="mrpandey" data-bi-name="contributorprofile" target="_blank">mrpandey</a> (0.4%)</li><li><a href="https://github.com/rajatdiptabiswas" title="rajatdiptabiswas" data-bi-name="contributorprofile" target="_blank">rajatdiptabiswas</a> (0.4%)</li><li><a href="https://github.com/meooow25" title="meooow25" data-bi-name="contributorprofile" target="_blank">meooow25</a> (0.4%)</li><li><a href="https://github.com/algmyr" title="algmyr" data-bi-name="contributorprofile" target="_blank">algmyr</a> (0.4%)</li></ul> |
| 6961 | + <ul class="contributors" data-bi-name="contributors"><li><a href="https://github.com/madhur4127" title="madhur4127" data-bi-name="contributorprofile" target="_blank">madhur4127</a> (56.63%)</li><li><a href="https://github.com/tcNickolas" title="tcNickolas" data-bi-name="contributorprofile" target="_blank">tcNickolas</a> (25.3%)</li><li><a href="https://github.com/RodionGork" title="RodionGork" data-bi-name="contributorprofile" target="_blank">RodionGork</a> (4.02%)</li><li><a href="https://github.com/Morass" title="Morass" data-bi-name="contributorprofile" target="_blank">Morass</a> (3.61%)</li><li><a href="https://github.com/adamant-pwn" title="adamant-pwn" data-bi-name="contributorprofile" target="_blank">adamant-pwn</a> (3.21%)</li><li><a href="https://github.com/tanmay-sinha" title="tanmay-sinha" data-bi-name="contributorprofile" target="_blank">tanmay-sinha</a> (2.01%)</li><li><a href="https://github.com/wikku" title="wikku" data-bi-name="contributorprofile" target="_blank">wikku</a> (1.2%)</li><li><a href="https://github.com/gampu" title="gampu" data-bi-name="contributorprofile" target="_blank">gampu</a> (1.2%)</li><li><a href="https://github.com/abirc8010" title="abirc8010" data-bi-name="contributorprofile" target="_blank">abirc8010</a> (0.4%)</li><li><a href="https://github.com/jakobkogler" title="jakobkogler" data-bi-name="contributorprofile" target="_blank">jakobkogler</a> (0.4%)</li><li><a href="https://github.com/3centroids" title="3centroids" data-bi-name="contributorprofile" target="_blank">3centroids</a> (0.4%)</li><li><a href="https://github.com/mrpandey" title="mrpandey" data-bi-name="contributorprofile" target="_blank">mrpandey</a> (0.4%)</li><li><a href="https://github.com/rajatdiptabiswas" title="rajatdiptabiswas" data-bi-name="contributorprofile" target="_blank">rajatdiptabiswas</a> (0.4%)</li><li><a href="https://github.com/meooow25" title="meooow25" data-bi-name="contributorprofile" target="_blank">meooow25</a> (0.4%)</li><li><a href="https://github.com/algmyr" title="algmyr" data-bi-name="contributorprofile" target="_blank">algmyr</a> (0.4%)</li></ul> |
6978 | 6962 | </ul>
|
6979 | 6963 |
|
6980 | 6964 | </article>
|
|
0 commit comments