Location>code7788 >text

Roots Partitioning Mo Team

Popularity:437 ℃/2024-08-14 16:33:57

Mo team (sports)

Reference Article:
Mo Teams in Detail - Learning Mo Teams from Scratch
Mo-Team Algorithms - From Introductory to Black Questions
oiwiki - Common Mo Team

Mo Team Profile

The Mo Team algorithm is an algorithm proposed by Mo Tao. Before Mo Tao proposed the Mo Team algorithm, the Mo Team algorithm had already been circulated in a small circle of Codeforces experts, but Mo Tao was the first one to summarize the Mo Team algorithm in detail. When Mo Tao proposed the Mo Team algorithm, he only analyzed the common Mo Team algorithm, but after the collective wisdom of OIer and ACMer, Mo Team has a variety of extended versions.
The Mo Team algorithm solves a class of offline interval queries with extremely broad applicability. It can also be extended to easily handle path queries on trees and to support modification operations.

ordinary Mössbauer algorithm (math.)

formality

suppose that...\(n = m\), then for the interval interrogation problem on sequences, if from the\([l, r]\) The answer can be\(O(1)\) extend to\([l-1, r]\), \([l+1, r]\), \([l, r+1]\), \([l, r-1]\)(i.e., with\([l, r]\) neighboring intervals) of the answer, then the answer can be found in the\(O(n\sqrt{n})\) to find the answers to all queries within the complexity of the

account for

Offline sorting, processing each query sequentially, violently moving from the answer of the previous interval to the answer of the next interval (just move one step at a time).

Sorting methods

For intervals\([l, r]\), by\(l\) The number of the block in which it is located is the first keyword.\(r\) Sort for the second keyword from smallest to largest.

Slightly .......
Let's go straight to the title.
P1494 [NATIONAL TRAINING TEAM] Little Z's Socks

[NATIONAL TRAINING TEAM] Little Z's socks.

Title Description

upd on 2020.6.10 : Updated the timeframe.

As a person with a loose lifestyle, Little Z spends a long time every morning trying to find a pair of socks from a pile of colorful socks to wear. One day, Z couldn't stand this annoying process any longer, so he decided to do as he was told. ......

Specifically, Little Z puts this\(N\) Socks from\(1\) until (a time)\(N\) number, and then from the number\(L\) until (a time)\(R\) Z is asked to choose two socks at random from among all the socks in his collection. Although Z doesn't care if the two socks are a complete pair or not, he does care about the color of the socks - after all, it would be embarrassing to wear two socks of different colors.

Your task is to tell Little Z how likely he is to draw two socks of the same color. Of course, Little Z wants this probability to be as high as possible, so he may ask more than one question.\((L,R)\) to make it easier for you to choose.

However, the data has\(L=R\) Please specialize in this case by outputting the0/1

input format

The first line of the input file contains two positive integers\(N\) cap (a poem)\(M\)\(N\) is the number of socks.\(M\) Number of queries for Z. The next line contains\(N\) positive integer\(C_i\)which\(C_i\) denote\(i\) Only the color of the socks, the same color is represented by the same number. And then the next\(M\) Rows, two positive integers per row\(L, R\) Indicates an inquiry.

output format

encompass\(M\) line, for each query output the score in one line\(A/B\) denotes the interval from which the query\([L,R]\) The probability that two socks drawn at random are the same color. If this probability is\(0\) failing agreement0/1Otherwise the output of the\(A/B\) Must be the simplest fraction. (see sample for details)

Sample #1

Sample Input #1

6 4
1 2 3 3 3 2
2 6
1 3
3 5
1 6

Sample Output #1

2/5
0/1
1/1
4/15

draw attention to sth.

\(30\%\) In the data of the\(N,M\leq 5000\)

\(60\%\) In the data of the\(N,M \leq 25000\)

\(100\%\) In the data of the\(N,M \leq 50000\)\(1 \leq L \leq R \leq N\)\(C_i \leq N\)

AC Code:

#include<bits/stdc++.h>
#define int long long
#define debug() cout<<"----------debug-------------"
using namespace std.

const int N = 500010; // define the maximum size of the array
int n, q; // n is the size of the array, q is the number of queries
int c[N]; // store the input array
array<int, 3> que[N]; // store the array of queries, each query is a triple {l, r, i}
int B = 750; // size of the chunks
int ans[N]; // store the results of each query
int tmp = 0; // temporary variable for counting the number of distinct pairs of elements in the current interval
int ans2[N]; // record the denominator of each query
int cnt[N]; // record the number of times each number occurs

signed main() {
    ios::sync_with_stdio(0), (0), (0); // speed up input and output

    cin >> n >> q; // read array size and number of queries
    for (int i = 1; i <= n; i++)
        cin >> c[i]; // read array elements

    for (int i = 0; i < q; i++) {
        cin >> c[i]; // Read array elements for (int i = 0; i < q; i++) {
        cin >> l >> r; // read interval [l, r] for each query
        que[i] = {l, r, i}; // store the queries
        ans2[i] = (r - l) * (r - l + 1) / 2; // compute the denominator
    }

    // Sort the query according to the chunking strategy of the Mogul algorithm
    sort(que, que + q, [&](array<int, 3> a, array<int, 3> b) {
        int d = a[0] / B.
        if (a[0] / B ! = b[0] / B) return a[0] / B < b[0] / B;
        //if (d % 2 == 1) return a[1] < b[1]; //else return a[1] / B; if (a[0] / B != b[0] / B)
        //else return a[1] < b[1]; //if (d % 2 == 1)
        return a[1] < b[1].
    });

    int l = 1, r = 0; // initialize pointers l and r

    // Update tmp and cnt when adding elements.
    auto add = [&](int x) {
        tmp += cnt[c[x]]; // add tmp += cnt[c[x]].
        tmp += cnt[c[x]]; cnt[c[x]]++;
    };

    // Update tmp and cnt when deleting elements.
    auto del = [&](int x) {
        cnt[c[x]]--;; // update tmp and cnt when deleting an element.
        tmp -= cnt[c[x]];
    };

    // Iterate through each query, handling intervals by moving pointers l and r
    for (int i = 0; i < q; i++) {
        if (que[i][1] == que[i][0]) { // if the query interval length is 0
            ans[que[i][2]] = 0;
            continue.
        }
        while (r < que[i][1]) r++, add(r); // extend right boundary
        while (l > que[i][0]) l--, add(l); // extend left boundary
        while (r > que[i][1]) del(r), r--; // shrink right boundary
        while (l < que[i][0]) del(l), l++; // contract left boundary
        ans[que[i][2]] = tmp; // Record the result of the current query.
    }

    // Output the result of each query
    for (int i = 0; i < q; i++) {
        if (ans2[i] == 0 && ans[i] == 0) { // if both numerator and denominator are 0
            cout << "0/1" << endl;
            continue.
        }
        int d = __gcd(ans[i], ans2[i]); // compute the greatest common divisor
        cout << ans[i] / d << "/" << ans2[i] / d << endl; // Output results
    }

    return 0; }
}

Optimization:

course of events

Let's look at the following set of data

// Let the size of the block be 2 (assuming)
1 1
2 100
3 1
4 100

A bit of manual simulation shows that the r pointer moves about 300 times, and after we process the first block, the\(l = 2, r = 100\)At this point, we only need to move the l pointer twice to get the answer to the fourth query, but we move the r pointer to 1 to get the answer to the third query, and then to 100 to get the answer to the fourth query, which is ninety-some times more than we need to move the pointer. How can we optimize this? This is where we use parity sorting.

What is parity sorting? Parity sorting means that for queries belonging to odd blocks, r is sorted from smallest to largest, and for those belonging to even blocks, r is sorted from smallest to largest, and for those belonging to even blocks, r is sorted from smallest to largest.\(r\)Sort them from largest to smallest so that our\(r\) The pointer, after processing this odd-numbered block, will process the even-numbered block on its way back to the\(n\) The problem of moving to handle the next odd block is optimized for\(r\) The number of times the pointer is moved, and in general, this optimization makes the program faster\(30\)% or so.

  // Sort the query according to the chunking strategy of the MoTeam algorithm
    sort(que, que + q, [&](array<int, 3> a, array<int, 3> b) {
        int d = a[0] / B.
        if (a[0] / B ! = b[0] / B) return a[0] / B < b[0] / B;
        if (d % 2 == 1) return a[1] < b[1]; else return a[1] > b[1].
        else return a[1] > b[1];
    b[1]; else return a[1] < b[1]; });

Partition of the Roots (medical term)

The Root Partition, is a collection of embodiments of violent aesthetics. Rather than an algorithm, let's call it a commonly used trick.

introduce the topic

First, we introduce an introductory questionCF1207F Remainder Problem

Gives you a length of\(5×10^5\) The sequence of the initial values of\(0\)You're going to finish.\(q\) suboperations, there are two types of operations as follows:

  1. 1 x y:: Setting the subscripts to\(x\) The value of the location of the\(y\)
  2. 2 x y: Ask for all subscripted modules\(x\) The result of the\(y\) The sum of the values of the positions of the

violent solution

Violence 1

The first kind of violence is to do what the title says and open a\(5×10^5\) Arrays of size\(a\) De-stocking.\(1\) It's the right thing to do.\(a[x]\) on top of that\(y\)\(2\) The operation enumerates all subscripted modules\(x\) The result of the\(y\) position, counting their sums.

For this violence.\(1\) The time complexity of the operation is\(O(1)\)\(2\) The time complexity of the operation is\(O(n)\), so the total time complexity in the worst case can be as high as\(O(nq)\)

Violence 2

Upon reflection, we can find another kind of violence: opening a new file of size\(n×n\) two-dimensional array\(b\)\(b[i][j]\) All current subscript molds\(i\) The result of the\(j\) What is the sum of the numbers of the For each\(1\) operation to dynamically maintain this\(b\) array, just output the answer directly at each query.

For this violence.\(1\) The time complexity of the operation is the enumeration modulus of the\(O(n)\)\(2\) The time complexity of the operation is\(O(1)\), the total time complexity is\(O(nq)\)

Roots partition strategy

Now we find that these two kinds of violence correspond to two extremes: a\(1\) The time complexity of the operation is\(O(1)\)The time complexity of the 2 operation is\(O(n)\); the other is\(1\) The time complexity of the operation is the enumeration modulus of the\(O(n)\)The time complexity of the 2 operation is\(O(1)\). So, is there a way to make these two kinds of violence blend a bit, equalize the time complexity, and strike a balance?

Actually, there is. We set a threshold\(b\)

For all\(≤b\) number, we dynamically maintain the violence\(2\) (used form a nominal expression)\(b\) arrays. Each time the\(1\) The operation only needs to enumerate\(b\) The single operation can be done with only one modulus.\(1\) The time complexity is reduced to\(O(b)\)

For all\(>b\) number, we don't operate on the\(1\) maintenance center\(b\)It's just a matter of violently enumerating the subscripts when asking for the answer directly again. Obviously, this\(n\) The maximum number of subscripts in the\(⌈n/b⌉\) pair of subscripts\(x\) mold residue\(y\) Find the first one.\(y\) After each jump\(x\)The most important thing is that you can do it all in a single operation.\(2\) The time complexity is\(O(n\sqrt{b})\)

So the total time complexity becomes\(O(q×(b+n\sqrt{b}))\). From the fundamental inequality, it follows that\(b+n/b≥2√(b×n/b)=2√n\)regard as\(b=\sqrt{n}\) Time to take, etc. So we just need to let\(b=\sqrt{n}\), it is possible to achieve both time and space complexity of\(O(q\sqrt{n})\) The excellent algorithms are now available to pass this question.

Code:

#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
const int N=5e5+30,mod=998244353;
typedef long long ll;
typedef pair<int,int> PII;
int n,m;
int q;
const int B=750;
int ans[B+10][B+10];
int a[N];
void solve()
{
    cin>>q;
    while(q--)
    {
        int id,x,y;
        cin>>id>>x>>y;
        if(id==1)
        {
            for(int i=1;i<=B;i++) ans[i][x%i]+=y;
            a[x]+=y;
        }
        else
        {
            if(x<=B) cout<<ans[x][y]<<endl;
            else
            {
                int temp=0;
                for(int i=y;i<=500000;i+=x)
                {
                    temp+=a[i];
                }
                cout<<temp<<endl;
            }
        }
    }

   
}
signed main()
{
    ios::sync_with_stdio(0),(0),(0);
    int _;
    _=1;
    //cin>>T;
    while(_--)
     {
         solve();
     }
     return 0;
}