# 莫隊+數學

**許多競賽中的題目常常會有多筆詢問
像是這樣:**

### 注意
給一個$T$，代表有幾次輸入，這種並不算是多筆詢問

這種類型的題目通常都是要求你先預處理好，再每次有效率的回答詢問
先把所有詢問都讀入，通過排序或是其他的處理方法
全部一起處理完，會被稱為離線的算法
而每次得到詢問後馬上回答，會被稱為是在線的

由於離線可以自己決定要怎麼處理，因次通常都會有比在線更好的複雜度或是實作難度

## 莫隊算法

莫隊算法是

基本上這個東西的想法就是暴力，只是把它優化一下

莫隊算法通常可以處理的問題形式如下:
* 有一個長度為$N$的陣列
* 接著有$Q$筆詢問
* 每筆詢問給區間$[ql,qr]$，求這個區間的答案(例如區間眾數、區間最大連續和、區間某個數字的數量)
* 可以離線處理(沒有修改)

最當初的想法是把上一次的詢問直接往下做到下一次的詢問
例:$[4,10]$移到$[6,9]$只需要把左界往右2格，右界往左1格就好了
可是這樣會有worst case:
$[1,1]$
$[1,n]$
$[1,2]$
$[1,n-1]$
$[1,3]$
$[1,n-2]$
$......$
這樣每次會需要花很久的時間才能移到下一個詢問
因此我們可以找一個好的詢問順序，讓相鄰兩個詢問移動距離變小

**把剛剛的想法修改一下:**
1. 把序列每 $\sqrt n$ 個分成一塊。
2. 把所有詢問先按「左界所在的塊」排序。
3. 若左界所在的塊相同,則按右界排序。


提醒: 塊的大小和數量都是$\sqrt n$
很神奇的，這樣複雜度會變成$O((n+q) \sqrt n)$

證明:

* 同一塊中，右界只會一直往右，因此右界會動 (塊的數量$\times n$) 次
* 左界被限制在$\sqrt n$的範圍內，因此左界移動次數是 ($q\sqrt n$)次
因此把詢問排序好之後，再將移動的函式寫好，就可以得到一個好的暴力算法!

由於他只要暴力然後簡單的做，因此作法通常都很簡單

**例題:[Range Pairing Query](https://atcoder.jp/contests/abc242/tasks/abc242_g)**

題目大意: 有一個陣列$a_i$，代表第$i$個人的衣服顏色是$a_i$
衣服顏色相同的兩個人可以配對
請問最多可以配出幾組
可以發現如果每次都只加一個人或減少一個人，要算答案很快$O(1)$
所以套莫隊的話就只需要$O(n \sqrt n)$就能做完了

#include<bits/stdc++.h>
using namespace std;
int K;
vector<int> v;
 
struct qry{
    int a,b,p;
};
bool operator<(const qry &q1,const qry &q2){
    if(q1.a/K==q2.a/K){
        return q1.b<q2.b;
    }
    return q1.a<q2.a;
}
int main(){
    int n;cin>>n;
    vector<int> v(n);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    int m;
    cin>>m;
    K=sqrt(n);
    vector<qry> q(m);
    vector<int> ans(m);
    for(int i=0;i<m;i++){
        cin>>q[i].a>>q[i].b;
        q[i].a--;q[i].b--;
        q[i].p=i;
    }
    sort(q.begin(),q.end());
    int cnt=0;
    vector<int> w(n+1);
    auto add=[&](int p){
        if(w[p]&1){
            cnt++;
        }
        w[p]++;
    };
    auto del=[&](int p){
        w[p]--;
        if(w[p]&1){
            cnt--;
        }
    };
 
    int l=0,r=-1;
    for(int i=0;i<m;i++){
        while(q[i].a>l){
            del(v[l]);
            l++;
        }
        while(q[i].a<l){
            l--;
            add(v[l]);
        }
        while(q[i].b>r){
            r++;
            add(v[r]);
        }
        while(q[i].b<r){
            del(v[r]);
            r--;
        }
        ans[q[i].p]=cnt;
    }
    for(int i=0;i<m;i++){
        cout<<ans[i]<<'\n';
    }
    return 0;
}

### 奇偶優化

由於右邊指標會一直往右，到下一塊再移回來，因此移回來相當於浪費了，因為他沒做到事
所以可以把第一塊由小到大排
第二塊由大到小排
然後依次往下
這樣可以節省一些時間

bool operator<(const qry &q1,const qry &q2){
    if(q1.a/K==q2.a/K){
        if((q1.a/K)&1)return q1.b>q2.b;
        return q1.b<q2.b;
    }
    return q1.a<q2.a;
}


### 練習題:
第一次寫的話可以寫這題先練習看看:
[**Static Range Sum Queries**](https://cses.fi/problemset/task/1646)

[**XOR and Favorite Number**](https://codeforces.com/problemset/problem/617/E)

[**Ann and Books**](https://codeforces.com/problemset/problem/877/F)

[**Distinct Values Queries**](https://cses.fi/problemset/task/1734)

[**One Occurrence**](https://codeforces.com/contest/1000/problem/F)

### 帶修改莫隊

這東西不常用，可以看看就好
如果題目需要修改的話，就不能用原本的莫隊算法了

**例題:[Machine Learning](https://codeforces.com/problemset/problem/940/F)**

題目大意:
有一個陣列$a_i$，並且有$Q$次詢問:
1. 單點改值
2. 詢問區間每個數字出現次數的MEX
例: [3,3,2]的答案是3，因為有出現過0次,1次,2次
[3,3,3,2]的答案就是2

大概的作法是把 \[左界,右界,時間\]一起用莫隊做
1. 把序列每$K$個分成一塊。
2. 把所有詢問先按「左界所在的塊」排序。
3. 若左界所在的塊相同,則按右界排序。
4. 若右界的塊相同，則按時間排序

總共移動次數會是$O(\frac{N^3}{K^2}+NK)$
~~我不會證明~~

當$K$取$N^{\frac {2}{3} }$的時候可以得到一個$O(N^{\frac{5}{3}})$的演算法

看起來寫得很清楚的
Code:https://codeforces.com/contest/940/submission/35760839

## :ideograph_advantage: Math

### 排容原理

有 $n$ 的集合 $S_1, S_2, \cdots, S_n$ 則
$$
\sum_{T \in {1, 2, \cdots, n}}{(-1)^{|T|}|\bigcap_{i \in T}S_i|}=0
$$

以 $n=3$ 為例：
$$
|S_1 \cup S_2 \cup S_3|-|S_1|-|S_2|-|S_3|+|S_1 \cap S_2|+|S_2 \cap S_3|+|S_3 \cap S_1|-|S_1 \cap S_2 \cap S_3|=0
$$

### 莫比烏斯反演

令 $A=\{S_1, S_2, \cdots, S_n\}$ 則
$$
g(A)=\sum_{B \subseteq A}f(B) \Longleftrightarrow f(A)=\sum_{B \subseteq A}\mu(A \setminus B)g(B)
$$

### 莫比烏斯函數

$$
\mu(B)=
\begin{cases}
0 & 如果 B 裡面有重複的元素 \\
(-1)^{|B|} & 如果 B 裡面沒有重複的元素
\end{cases}
$$

### 錯排

一個 $1$ 到 $n$ 的排列裡面有多少種排列使得 $\sigma_i \neq i$

通式
$$
D_n=(n-1)(D_{n-1}+D_{n-2})
$$

其中 $D_n$ 代表長度為 $n$ 的錯排數

或者有另一種通式

$$
D_n=n!\sum_{i=0}^n{\frac{(-1)^i}{i!}}
$$

**題目:[Christmas Party](https://cses.fi/problemset/task/1717)**

### 線性遞迴

$$
a_n=c_1a_{n-1}+c_2a_{n-2}+\cdots+c_ka_{n-k}
$$

則我們說這個是一個 $k$ 階的線性遞迴

### 矩陣快速冪

$$
\begin{pmatrix}
a_n \\
a_{n-1} \\
a_{n-2} \\
\vdots \\
a_{n-k+1}
\end{pmatrix}
=\begin{pmatrix}
c_1 & c_2 & \cdots & c_{k-1} & c_k \\
1 & 0 & \cdots & 0 & 0 \\
0 & 1 & \cdots & 0 & 0 \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & \cdots & 1 & 0
\end{pmatrix}
\begin{pmatrix}
a_{n-1} \\
a_{n-2} \\
a_{n-3} \\
\vdots \\
a_{n-k}
\end{pmatrix}
$$

**題目: [Fibonacci Numbers](https://cses.fi/problemset/task/1722)**
Code: https://cses.fi/paste/f3b7618032ab50ef41d162/

[**Throwing Dice**](https://cses.fi/problemset/task/1096)
Code: https://cses.fi/paste/f52f6ed39b6f675445e7ec/

### 卡特蘭數

$$
C_{n+1}=\sum_{i=0}^{n}{C_iC_{n-i}} \\
C_n=\frac{1}{n+1}\binom{2n}{n}
$$

#### 神奇組合對應

* 長度為 $2n$ 的合法括號數列
* 凸 $n+2$ 邊形分割成多個三角形的個數
* $n+1$ 個點的有根樹數量
* $n$ 個點的完全二元樹數量(不含葉子)

### 組合數

$$
\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}
$$

### 線性蓋 $1$ 到 $n$ 的模逆元

$$
q = \lfloor \frac{m}{i} \rfloor \\
m = iq + r \\
-iq \equiv r \pmod m \\
-iq(i^{-1}r^{-1}) \equiv r(i^{-1}r^{-1}) \equiv i^{-1} \pmod m \\
i^{-1} \equiv -qr^{-1} \pmod m
$$

## 沒了