Mo team learning notes (I)

This article references from ：https://www.cnblogs.com/ouuan/p/MoDuiTutorial.html

Ordinary Mo team

brief introduction

Mo team is a team based on Block thought Of offline Algorithm , For resolution Interval problem , The scope of application is as follows ：

1. Only query without modification
2. Allow offline processing （ Know all the data you need to enter at the beginning of the problem , And output the results immediately after solving a problem ）
3. Keep asking [l.r] The answer can be O(1) obtain [l,r+1],[l-1,r],[l+1.r] The answer .
   Meeting the above three conditions can be in O(n$\sqrt{m}$+mlogm) Get the solution of each query under the time complexity of .

Algorithmic thought

The essence of Mo team is to sort the queries , And take the result of the inquiry as the basis of the next Xu Ben solution , The complexity of violent solution is guaranteed .
In this paper “ Scope of application ” The third point of “ Ask in known [l,r] The answer can be O(1) obtain [l,r−1],[l,r+1],[l−1,r],[l+1,r] The answer ” That is “ Take the result of the inquiry as the basis for solving the next inquiry ” Methods .
Example ：[ National Team ] Small Z Socks of
In this question , use cnt[i] Indicates that the color in the current processing range is i The number of socks that appear , use len Indicates the length of the current processing interval , use x Indicates the color of the new sock .
With a known interval [l,r] The answer of is to solve the interval [l,r+1] For example . Deal with numerator and denominator respectively ：

• The numerator is the total number of combinations of any two socks , It used to be $\frac{len\ast (len-1)}{2}$, Now it is $\frac{len\ast (len+1)}{2}$, Added len.
• The numerator is the total number of combinations with the same color of two socks , More than before cnt[i], That is, the new sock and the sock combination with the same color in the current range .
  therefore , The color is x Socks add a sequence of functions ：

//fz Representative molecules ,fm For the denominator 
void add(int x)
{
    
    fz += cnt[x];
    ++cnt[x];
    fm += len;
    ++len;
}

The color is x Socks remove the function of the sequence ：

void del(int x)
{
    
    --cnt[x];
    fz -= cnt[x];
    --len;
    fm -= len;
}

therefore , We can get a violent Algorithm ： use l and r Record the two endpoints of the current interval respectively , Then use the following code to update the answer （q[i].l,q[i].r Represents the two endpoints of the query being processed ,col[p] On behalf of the p The color of a sock ）

	while(l>q[i].l)
		add(col[--l]);
	while(r<q[i].r)
   		add(col[++r]);
    while(l<q[i].l)
        del(col[l++]);
    while(r>q[i].r)
        del(col[r--]);

However , The time complexity of this algorithm is O(nm), It's exactly the same as violence, even slower .
however , The essence of Mo team we mentioned earlier is to inquire about the questions , The complexity of violent solution is guaranteed .
We put the whole interval [1,n] Divide into pieces , Take the left endpoint of the query as the first keyword , Take the size of the right endpoint of the query as the second keyword , Sort it , that ：

• For the same piece of inquiry ,l The maximum size of the block that the pointer moves at a time ,r The movement of the pointer is monotonous , Move the most in total n .
• Queries about different blocks ,l Move up to twice the size of the block each time you change the block , r Move at most during each block change n .

summary ：（ use B Represents the size of the block ）l Every time the pointer moves O(B),r The pointer moves every piece O(n) .
therefore ：

• l The maximum number of moves is the number of queries × The size of the block , namely O(mB) .
• r The maximum number of moves is the number of blocks × Total interval size , namely O(n2/B) .
  therefore , The total number of moves is O(mB+n2/B) .
  you 're right , This is a double hook function , therefore B =$\frac{n^2}{m}$ namely $\frac{n}{\sqrt{m}}$ Minimum time complexity , by O(n$\sqrt{m}$).
  The last question left ： What is the initial current interval ？
  Just specify an empty interval arbitrarily , Such as l=1,r=0 .
  So the Mo team algorithm can be summarized as ：

1. Record inquiries
2. With $\frac{n}{\sqrt{m}}$ For the size of the block , Take the block where the left endpoint of the query is located as the first keyword , Take the size of the right endpoint of the query as the second key , Sort queries .
3. Violent handling of every inquiry
4. Output the answer
   Total complexity ：O(n$\sqrt{m}$ + mlogm)
   Code ：

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
#include<ctime>
#include<utility>
#include<map>
#define ll long long
#define ld long double
#define ull unsigned long long
using namespace std;
const int INF = 100000;
const double eps = 1e-6;
const int maxn = 50100;
int n,m,nm;
int fz,fm,len;
int col[maxn],cnt[maxn],ans[maxn][2];
struct In{
    
    int l,r,id;
    bool operator < (In &b){
    
        return l/nm==b.l/nm ? r<b.r : l<b.l;
    }
}q[maxn];
inline int gcd(int a,int b)
{
    
    return b==0 ? a : gcd(b,a%b);
}
inline void add(int x)
{
    
    fz += cnt[x];
    ++cnt[x];
    fm += len;
    ++len;
}
inline void del(int x)
{
    
    --cnt[x];
    fz -= cnt[x];
    --len;
    fm -= len;
}
int main(void)
{
    
    scanf("%d%d",&n,&m);
    nm = n / sqrt(m);
    for(int i=1;i<=n;i++){
    
        scanf("%d",&col[i]);
    }
    for(int i=0;i<m;i++){
    
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].id = i;
    }
    sort(q,q+m);
    int l=1,r=0;
    for(int i=0;i<m;i++){
    
        if(q[i].l==q[i].r){
    
            ans[q[i].id][0] = 0;
            ans[q[i].id][1] = 1;
            continue;
        }
        while(l>q[i].l)
            add(col[--l]);
        while(r<q[i].r)
            add(col[++r]);
        while(l<q[i].l)
            del(col[l++]);
        while(r>q[i].r)
            del(col[r--]);
        int g = gcd(fz,fm);
        ans[q[i].id][0] = fz / g;
        ans[q[i].id][1] = fm / g;
    }
    for(int i=0;i<m;i++){
    
        printf("%d/%d\n",ans[i][0],ans[i][1]);
    }
    return 0;
}

Example 2：SPOJ DQUERY

Given a sequence of n numbers a1, a2, …, an and a number of d-queries. A d-query is a pair (i, j) (1 ≤ i ≤ j ≤ n). For each d-query (i, j), you have to return the number of distinct elements in the subsequence ai, ai+1, …, aj.

Input

• Line 1: n (1 ≤ n ≤ 30000).
• Line 2: n numbers a1, a2, …, an (1 ≤ ai ≤ 10⁶).
• Line 3: q (1 ≤ q ≤ 200000), the number of d-queries.
• In the next q lines, each line contains 2 numbers i, j representing a d-query (1 ≤ i ≤ j ≤ n).

Output
For each d-query (i, j), print the number of distinct elements in the subsequence ai, ai+1, …, aj in a single line.

Example

Input
5
1 1 2 1 3
3
1 5
2 4
3 5

Output
3
2
3

The question

Inquire about [l,r] Types of elements in the interval , Sequence length <=30000, Element size ∈[1,10⁶], Query times <=2000000.

Ideas

Generally speaking , What ordinary Mo team changed is add and del function , The rest is basically the same , Here we can use cnt[x] Show elements x The number in the sequence ,sum Indicates the type of elements in the sequence , that add and del Functions can be written ：

void add(int x)
{
    
    if(cnt[x]==0)   sum++;
    cnt[x]++;
}
void del(int x)
{
    
    --cnt[x];
    if(cnt[x]==0)   sum--;
}

AC Code ：

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
#include<ctime>
#include<utility>
#include<map>
#define ll long long
#define ld long double
#define ull unsigned long long
using namespace std;
const int INF = 100000;
const double eps = 1e-6;
const int maxn = 2000010;
int n,m,nm;
int sum;
int col[maxn],cnt[maxn],ans[maxn];
struct In{
    
    int l,r,id;
    bool operator < (In &b){
    
        return l/nm==b.l/nm ? r<b.r : l<b.l;
    }
}q[maxn];
inline void add(int x)
{
    
    if(cnt[x]==0)   sum++;
    cnt[x]++;
}
inline void del(int x)
{
    
    --cnt[x];
    if(cnt[x]==0)   sum--;
}
int main(void)
{
    
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
    
        scanf("%d",&col[i]);
    }
    scanf("%d",&m);
    nm = n / sqrt(m);
    for(int i=0;i<m;i++){
    
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].id = i;
    }
    sort(q,q+m);
    int l=1,r=0;
    for(int i=0;i<m;i++){
    
        while(l>q[i].l)
            add(col[--l]);
        while(r<q[i].r)
            add(col[++r]);
        while(l<q[i].l)
            del(col[l++]);
        while(r>q[i].r)
            del(col[r--]);
        ans[q[i].id] = sum;
    }
    for(int i=0;i<m;i++){
    
        printf("%d\n",ans[i]);
    }
    return 0;
}

Example 3：P2709 Small B Of

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
#include<ctime>
#include<utility>
#include<map>
#define ll long long
#define ld long double
#define ull unsigned long long
using namespace std;
const int INF = 100000;
const double eps = 1e-6;
const int maxn = 2000010;
int n,m,k,nm;
int sum;
int col[maxn],cnt[maxn],ans[maxn];
struct In{
    
    int l,r,id;
    bool operator < (In &b){
    
        return l/nm==b.l/nm ? r<b.r : l<b.l;
    }
}q[maxn];
inline void add(int x)
{
    
    if(x>k||x<1)    return ;
    if(cnt[x]==0)   sum++;
    else    sum += (2*cnt[x]+1);
    cnt[x]++;
}
inline void del(int x)
{
    
    if(x>k||x<1)    return ;
    --cnt[x];
    if(cnt[x]==0)   sum--;
    else    sum -= (2*cnt[x]+1);
}
int main(void)
{
    
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++){
    
        scanf("%d",&col[i]);
    }
    nm = n / sqrt(m);
    for(int i=0;i<m;i++){
    
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].id = i;
    }
    sort(q,q+m);
    int l=1,r=0;
    for(int i=0;i<m;i++){
    
        while(l>q[i].l)
            add(col[--l]);
        while(r<q[i].r)
            add(col[++r]);
        while(l<q[i].l)
            del(col[l++]);
        while(r>q[i].r)
            del(col[r--]);
        ans[q[i].id] = sum;
    }
    for(int i=0;i<m;i++){
    
        printf("%d\n",ans[i]);
    }
    return 0;
}