owned this note
owned this note
Published
Linked with GitHub
# 莫隊算法
一個基於[分塊](https://hackmd.io/86kWJsh6S5KjPzYLc1xsxg?view)之上的演算法
先來看例題:
## 不帶修改莫隊算法
### 題目:給定一陣列a和q項查詢[l,r],求[l,r]中有幾個不同的數字
對於每個詢問，可以拿上一次詢問完的[l,r]加上移動到與這一次詢問的[l,r]的差異值，就是答案，那麼現在的問題就是 : 所有詢問間的位移最小值
依照上面的想法可以先寫出一個code
```cpp=
int ans=0,cnt[MAXN]={0},a[]={..../*test*/};
void add(int val){
if(cnt[val]==0) ans++;
cnt[val]++;
}
void sub(int val){
if(cnt[val]==1) ans--;
cnt[val]--;
}
//main-----------
int l=0,r=-1; //初始化
for(int i=0;i<q;i++){
cin >> ql >> qr;
while(l<ql) sub(a[l++]);
while(l>ql) add(a[--l]);
while(r<qr) add(a[++r]);
while(r>qr) sub(a[r--]);
cout << ans << '\n';
}
```
但是這樣會來來回回很多次，所以回到我們之前的問題 : 如何讓位移量最小化
### 排序
但要怎麼排呢?
假設我們的側資長這樣
```
L R :
5 8
1 10
6 9
5 9
1 5
3 10
1 9
1 1
6 9
2 3
```
<b>(法1)</b> 我們可以依照L由小到大，如果L一樣，就依照R
```cpp=
bool cmp(node a,node b){
if(a.l!=b.l) return a.l<b.l;
else return a.r<b.r;
}
```
```
L R :
1 1
1 5
1 9
1 10
2 3
3 10
5 8
5 9
6 9
6 9
```
L是很好沒錯，但R在L換數字時就會跳很大了，所以我們可以在適當的範圍內讓L跳，像是做完第一組詢問後可以跳(2,3)
<b>(法2)</b> 利用分塊概念，當L在不同塊時，用塊去排序，當L在同一塊時，用R去排序
```cpp=
int k=(int)sqrt(n);
bool cmp(node a,node b){
if(a.l/k!=b.l/k) return a.l/k>b.l/k;
else return a.r<b.r;
}
```
```
L R :
1 1
2 3
1 5
1 9
1 10
5 8
5 9
3 10
6 9
6 9
```
<b>加速</b>
一開始右界會從最左邊跑到最右邊，此時下一塊可由最右邊開始，從右跑到左，再下一塊就由最左邊開始，這樣比較有效率
```cpp=
bool cmp(Q a,Q b){
if(a.F/k==b.F/k){
if((a.F/k)%2) return a.S>b.S;
else return a.S<b.S;
}
return a.F/k<b.F/k;
}
```
```
L R :
1 1
2 3
1 5
1 9
1 10
3 10
5 9
5 8
6 9
6 9
```
:::spoiler ZJ b417: 區間眾數 Code
```cpp=
#include <bits/stdc++.h>
#define MAXN 100005
#define pii pair<int,int>
using namespace std;
typedef struct{
int l,r,id;
}node;
int cnt[MAXN]={0},cntcnt[MAXN]={0},ma=0,k;
bool cmp(node a,node b){
return a.l/k==b.l/k?a.r<b.r:a.l/k<b.l/k;
}
void add(int pos){
cntcnt[cnt[pos]]--;
cnt[pos]++;
cntcnt[cnt[pos]]++;
if(cntcnt[cnt[pos]]==1) ma=max(ma,cnt[pos]);
}
void sub(int pos){
cntcnt[cnt[pos]]--;
cnt[pos]--;
cntcnt[cnt[pos]]++;
if(cntcnt[cnt[pos]+1]==0 && ma==cnt[pos]+1) ma=cnt[pos];
}
int main(){
cin.sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,m;
cin >> n >> m;
k=(int)sqrt(n);
vector<int> v(n+1);
for(int i=1;i<=n;i++){
cin >> v[i];
}
vector<node> q(m);
for(int i=0;i<m;i++){
cin >> q[i].l >> q[i].r;
q[i].id=i;
}
sort(q.begin(),q.end(),cmp);
vector<pii> ans(m);
int l=1,r=0;
for(auto p:q){
while(l<p.l) sub(v[l++]);
while(l>p.l) add(v[--l]);
while(r<p.r) add(v[++r]);
while(r>p.r) sub(v[r--]);
ans[p.id].first=ma;
ans[p.id].second=cntcnt[ma];
}
for(auto i:ans) cout << i.first << ' ' << i.second << '\n';
return 0;
}
```
:::
## 帶修改莫隊算法
### 分塊
要分成n^2/3^塊,別問我問什麼,我也不知道
(2022/6/28)更 : 因為時間複雜度最小，至於怎麼證明有待研究
```cpp=
k=pow(n,2/3.0);
```
### 排序
優先順序為左塊>右塊>t，t為第幾次修改
```cpp=
struct Q{
int l,r,t,idx;
bool operator<(Q b){
if(l/k==b.l/k){
if(r/k==b.r/k){
return t<b.t;
}else{
return r/k<b.r/k;
}
}else{
return l/k<b.l/k;
}
}
}q[MAXN];
```
### 修改
跟前面一樣，就只是多了個t要判斷，在修改的時候，如果要修改的編號不在[l,r]那就直接修改，否則要先把此元素在[l,r]中刪掉，然後新增此修改值，最後在修改陣列的值，要注意的是不能直接覆蓋，而是交換，因為後面有可能會把此元素換回未修改前的值。
注意:在函式裡做交換要取本尊來交換
```cpp=
void modity(Q x,M &y){
if(x.l<=y.idx && y.idx<=x.r){
sub(a[y.idx]);
add(y.val);
}
swap(a[y.idx],y.val);
}
//新增要判斷的
while(t<q[i].t) modity(q[i],m[++t]);
while(t>q[i].t) modity(q[i],m[t--]);
```
:::spoiler Code
```cpp=
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define mem(a) memset(a,0,sizeof(a))
#define binary_search
#define inf LLONG_MAX
#define mod 1000000007
const int MAXN=133335;
int N=1,n,x,k;
//-----------------------------------
int a[MAXN],mp[1000005],l,r,t,qid,mid,cnt;
struct Q{
int l,r,t,idx;
bool operator<(Q b){
if(l/k==b.l/k){
if(r/k==b.r/k){
return t<b.t;
}else{
return r/k<b.r/k;
}
}else{
return l/k<b.l/k;
}
}
}q[MAXN];
struct M{
int idx,val;
}m[MAXN];
void add(int val){
if(!mp[val]) cnt++;
mp[val]++;
}
void sub(int val){
mp[val]--;
if(!mp[val]) cnt--;
}
void modity(Q x,M &y){
if(x.l<=y.idx && y.idx<=x.r){
sub(a[y.idx]);
add(y.val);
}
swap(a[y.idx],y.val);
}
signed main(){
cin.sync_with_stdio(0),cin.tie(0);
int q_num;
char info;
cin >> n >> q_num;
k=pow(n,(double)2/(double)3);
for(int i=1;i<=n;i++) cin >> a[i];
for(int i=0;i<q_num;i++){
cin >> info;
int l,r,x,val;
if(info=='Q'){
cin >> l >> r;
q[qid]={l,r,mid,qid};
qid++;
}else{
cin >> x >> val;
m[++mid]={x,val};
}
}
sort(q,q+qid);
vector<int> ans(qid);
for(int i=0;i<qid;i++){
while(l<q[i].l) sub(a[l++]);
while(l>q[i].l) add(a[--l]);
while(r>q[i].r) sub(a[r--]);
while(r<q[i].r) add(a[++r]);
while(t<q[i].t) modity(q[i],m[++t]);
while(t>q[i].t) modity(q[i],m[t--]);
ans[q[i].idx]=cnt;
}
for(auto i:ans) cout << i << '\n';
}
```
:::
## 回滾莫對
### 題目:給你一個n項的陣列，有q次詢問，每次詢問區間[l,r]中$max\{cnt_x×x\}$的值
莫對其念是當我們得知一個區間$[l,r]$的值後，我們可以以這個區間來位移到我們要查詢的區間，這樣就不用每個都從頭算了。
在位移的值後，我們可以發現在新增元素的時候很好寫，只需要跟答案取最大值就好，但刪除元素的時候就沒那麼容易了，因此我們可以採用一個方法 : 回朔，先記錄下更新此元素前的最大值是多少，接著還刪除此元素後就考可以一併更新最大值了。
```cpp=
void add(int x){
stk.push({cur_ma,x});
cnt[x]++;
cur_ma=max(cur_ma,cnt[x]*x);
}
void roll_back(){
pii top=stk.top();stk.pop();
cur_ma=top.F;
cnt[top.S]--;
}
```
如果$[l,r]$在同一個block的時候可以先做，直接暴力求解，不同block時，以下為更新的步驟 :
初始話時，L要在左界屬於的block+1的最左邊的格子，R要在左界屬於的block的最右邊，因最左界往左跑，要初始話在-1的地方，右界同理。
接著右界移動，左界移動，然後更新答案，最後再把左界移到初始位置，因為左界是照block順序排的，右界是直接照順序排的，因此左界要回朔，再移動到新的左界，右界只需要一直往右移動就好了，因為回朔具有單調性，因此左界每次都要回到最初的起點才不會左把右界混和。
```cpp=
for(auto [ql,qr,i]:q){
if(ql/k==qr/k) continue;
if(ql/k!=block){
while(!stk.empty()) roll_back();
block=ql/k;
L=(block+1)*k;
R=L-1;
}
while(R<qr) add(a[++R]);
while(ql<L) add(a[--L]);
ans[i]=curma;
while(L<(block+1)*k) roll_back(),L++;
}
```
:::spoiler Code
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 100005
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define pii pair<int,int>
#define F first
#define S second
#define inf LLONG_MAX
int a[MAXN],ans[MAXN],ori[MAXN],cnt[MAXN],k,curma;
stack<pii> stk;
struct Q{
int l,r,i;
bool operator<(Q b){
return (l/k==b.l/k ? r<b.r : l/k<b.l/k);
}
};
void add(int x){
stk.push({curma,x});
cnt[x]++;
curma=max(curma,cnt[x]*ori[x]);
}
void roll_back(){
pii top=stk.top();stk.pop();
curma=top.F;
cnt[top.S]--;
}
signed main(){
int n,m;
cin >> n >> m;
k=sqrt(n);
vector<int> tmp;
for(int i=0;i<n;i++){
cin >> a[i];
tmp.pb(a[i]);
}
sort(all(tmp));
tmp.resize(unique(all(tmp))-tmp.begin());
for(int i=0;i<n;i++){
int id=lower_bound(all(tmp),a[i])-tmp.begin();
ori[id]=a[i];
a[i]=id;
}
vector<Q> q;
for(int i=0;i<m;i++){
int l,r;
cin >> l >> r;
l--,r--;
q.pb({l,r,i});
if(l/k==r/k){
for(int j=l;j<=r;j++) add(a[j]);
ans[i]=curma;
for(int j=l;j<=r;j++) roll_back();
}
}
sort(all(q));
int L=0,R=0,block=-1;
for(auto [ql,qr,i]:q){
if(ql/k==qr/k) continue;
if(ql/k!=block){
while(!stk.empty()) roll_back();
block=ql/k;
L=(block+1)*k;
R=L-1;
}
while(R<qr) add(a[++R]);
while(ql<L) add(a[--L]);
ans[i]=curma;
while(L<(block+1)*k) roll_back(),L++;
}
for(int i=0;i<m;i++) cout << ans[i] << '\n';
}
```
:::
Google Drive
Gist
Clipboard
Sign in with Wallet
