莫隊算法

一個基於分塊之上的演算法
先來看例題:

不帶修改莫隊算法

題目:給定一陣列a和q項查詢[l,r],求[l,r]中有幾個不同的數字

對於每個詢問，可以拿上一次詢問完的[l,r]加上移動到與這一次詢問的[l,r]的差異值，就是答案，那麼現在的問題就是 : 所有詢問間的位移最小值

依照上面的想法可以先寫出一個code
























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

(法1) 我們可以依照L由小到大，如果L一樣，就依照R





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)

(法2) 利用分塊概念，當L在不同塊時，用塊去排序，當L在同一塊時，用R去排序







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

加速
一開始右界會從最左邊跑到最右邊，此時下一塊可由最右邊開始，從右跑到左，再下一塊就由最左邊開始，這樣比較有效率








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
ZJ b417: 區間眾數 Code 





























































#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;
}

帶修改莫隊算法

分塊

要分成n2/3塊,別問我問什麼,我也不知道
(2022/6/28)更 : 因為時間複雜度最小，至於怎麼證明有待研究

k=pow(n,2/3.0);

排序

優先順序為左塊>右塊>t，t為第幾次修改















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]中刪掉，然後新增此修改值，最後在修改陣列的值，要注意的是不能直接覆蓋，而是交換，因為後面有可能會把此元素換回未修改前的值。

注意:在函式裡做交換要取本尊來交換











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--]);
Code 
































































































#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]\)的值後，我們可以以這個區間來位移到我們要查詢的區間，這樣就不用每個都從頭算了。

在位移的值後，我們可以發現在新增元素的時候很好寫，只需要跟答案取最大值就好，但刪除元素的時候就沒那麼容易了，因此我們可以採用一個方法 : 回朔，先記錄下更新此元素前的最大值是多少，接著還刪除此元素後就考可以一併更新最大值了。












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順序排的，右界是直接照順序排的，因此左界要回朔，再移動到新的左界，右界只需要一直往右移動就好了，因為回朔具有單調性，因此左界每次都要回到最初的起點才不會左把右界混和。


















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++;
}
Code 























































































#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';
}
Select a repo