莫隊從入門到精通

莫隊從入門到精通，這篇文章越往后的內容可能越精煉，可以當快速復習整理食用，也可作為新手刷題

食用須知

這篇文章作者斷斷續續寫了幾個月，可能讀起來不連續或者風格術語變化，但是不影響大體
部分內容引自 $OI-wiki$，還有些內容參考了大佬博客，但是已經找不全了，在此一并感謝
本文章最初的設計意圖是校內講課用，因此有部分~~活潑的話語~~實際上是給同學寫的
有錯誤、不足歡迎指出，可以私信作者或者評論，有時間一定修
可能更好的閱讀體驗，~~不要臉的~~求一波關注和點贊
這篇文章越往后的內容可能越精煉，可以當快速復習整理食用，也可作為新手刷題

引子

副將不屑的瞥了他一眼，一抹黑色攀上手中的彎刀，恐怖的毀滅之力傾瀉而出！

“對了，最近，我給我這禁墟起了個名字，你要不要聽聽看？”副將手握黑色彎刀，轉頭問道。

“你一個莽夫，能起什么好名字。”儒生揚起下巴，“說說看，我可以給你潤色一下。”

副將緩緩提起手中的黑色彎刀，那雙眼眸中，迸發出一道璀璨的寒芒，他嘴角微微上揚，一字一頓的開口：

“黑，月，斬！！”
頌——！！

一道數十米長的黑色月牙猛地掠過夜空，瞬間將三只呼嘯而來的“神秘”身體斬成漫天碎塊，黑芒吞噬他們的殘軀，化作一陣血雨，飄零在燈火通明的酒樓上空。

噗嗤！

儒生忍不住笑了出來，“黑月斬？這么難聽的名字，也只有你詹玉武能想出來了！

”副將咬著牙，惡狠狠的開口，“那你起一個？”

儒生思索片刻，朗聲說道：“刀似月牙，泯滅眾生……不如，就叫它【泯生閃月】吧！”

基本預處理

首先我們要明確莫隊是離線算法，不能做一些強制在線的題，普通莫隊也并不支持修改

處理塊，塊長取值為 len

for(int i=1;i<=n;i++) pos[i]=(i-1)/len+1;;

我們以左端點所在塊為第一關鍵字，右端點為第二關鍵字排序，可以證明，這樣下去，每次操作均攤花費是 len

捕獲1

所以我們塊長取$\frac{n}{\sqrt{m} } $ 就好了

然后就是詢問間的轉移了，基本上是指針的轉移了，注意我們轉移區間要先擴再縮，不然的話面對一些求解組合數的問題會出神秘事件

while(q[i].l<l) l--,add(l);
while(q[i].r>r) r++,add(r);
while(q[i].l>l) del(l),l++;
while(q[i].r<r) del(r),r--;
ans[q[i].sa]=sum;

莫隊的小優化——奇偶化排序

據說適用于除了回滾以外的所有莫隊

什么是奇偶化排序？奇偶化排序即對于屬于奇數塊的詢問，r 按從小到大排序，對于屬于偶數塊的排序，r 從大到小排序，這樣我們的 r 指針在處理完這個奇數塊的問題后，將在返回的途中處理偶數塊的問題，再向 n 移動處理下一個奇數塊的問題，優化了 r 指針的移動次數，一般情況下，這種優化能讓程序快 30% 左右。（粘過來的，不知道真的假的）

bool cmp(node a,node b)
{
    if(pos[a.l]^pos[b.l]) return a.l<b.l;
    else if(pos[a.l]&1) return a.r<b.r;
    else return a.r>b.r;
}

普通莫隊例題：

P3709 大爺的字符串題

首先題意看似很神秘，實際上我們稍加思考就可以發現他與區間眾數有關

一般的數據結構很難維護眾數，原因就是無法高效的處理增量，但莫隊天生克制逐步增量的東西

考慮維護每個數出現個數（cnt），和出現次數為i的數的個數num，這樣的話就可以通過判斷num維護眾數值的加減

幾個經驗：P1997

int n,m,len,a[N],pos[N],b[N],sum,ans[N];

struct node {
	int l,r,id;
}q[N];
bool cmp(node a,node b) {
	if(pos[a.l]^pos[b.l]) return a.l<b.l;
	else if(pos[a.l]&1) return a.r>b.r;
	else return a.r<b.r;
}

int cnt[N],num[N];//每個數字出現個數，次數為這個 

void add(int p) {
	num[cnt[a[p]]]--; cnt[a[p]]++; num[cnt[a[p]]]++;
	if(cnt[a[p]]>z) z++;
}

void del(int p) {
	if(!--num[cnt[a[p]]]&&cnt[a[p]]==z) z--;
	num[--cnt[a[p]]]++;
}

signed main() {
	cin>>n>>m;len=n/sqrt(m*1.0);
	for(int i=1;i<=n;i++) b[i]=a[i]=read(),pos[i]=(i-1)/len+1;
	sort(b+1,b+1+n);
	int le=unique(b+1,b+1+n)-b-1;
	for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+le,a[i])-b;
	for(int i=1;i<=m;i++) {
		q[i].l=read(),q[i].r=read(),q[i].id=i;
	}
	sort(q+1,q+1+m,cmp);
	int l=1,r=0;
	for(int i=1;i<=m;i++) {
		while(q[i].l<l) l--,add(l);
		while(q[i].r>r) r++,add(r);
		while(q[i].l>l) del(l),l++;
		while(q[i].r<r) del(r),r--;
		ans[q[i].id]=sum;
	}
	return 0;
}

CF617E XOR and Favorite Number

這題也算個計數題，不知道大家還記不記得普及組時學習的技巧，區間異或和顯然等于前綴的異或

P3674 小清新人渣的本愿

來補一下之前自己沒填的坑，我們來思索一下，發現a_i值不大，這啟發我們把每個數存起來進行考慮，普通bool肯定是不可以的，但是我們用bitset就可以在 $O(c/w)$ 的時間里處理一次詢問，時間3s，那很好了

我們維護一個正bitset b，一個反bitset c $（x->N-x）$

對于減操作，判斷 Q=b&(b>>q_i.x)
是否有值即可
對于加操作，有一點區別，還記得我們存的反bitset嗎

Q=b&(c>>N-q[i].x);
  u=(N-v)-(N-x)
  u=x-v
  u+v=x

對于乘積，枚舉因數即可

#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=2e5+50,P=1e9+7;
int read() {
	int x=0;short f=1;char s=getchar();
	while(s<48||s>57){f=s=='-'?-1:1;s=getchar();}
	while(s>=48&&s<=57){x=x*10+s-48;s=getchar();}
	return x*f;
}

int n,m,opt,l,r,a[N<<1],siz[N<<1],pos[N<<1];

struct node {
	int l,r,op,x,id;
}q[N<<1];

bool cmp(node a,node b) {
	if(pos[a.l]^pos[b.l]) return a.l<b.l;
	else if(pos[a.l]&1) return a.r<b.r;
	else return a.r>b.r;
}

bitset<N+50> b,c,A,Q;
void add(int p) {
	int x=a[p];
	if(!siz[x]) b[x]=1,c[N-x]=1;
	siz[x]++;
}

void del(int p) {
	int x=a[p];
	if(siz[x]==1) b[x]=0,c[N-x]=0;
	siz[x]--;
}
signed main() {
	cin>>n>>m; int len=475;
	for(int i=1;i<=n;i++) pos[i]=(i-1)/len+1,a[i]=read();
	for(int i=1,x;i<=m;i++) {
		opt=read(),l=read(),r=read(),x=read();
		q[i]={l,r,opt,x,i};
	}
	sort(q+1,q+1+m,cmp);
	l=1,r=0;
	for(int i=1;i<=m;i++) {
		while(l>q[i].l) l--,add(l);
		while(r<q[i].r) r++,add(r);
		while(r>q[i].r) del(r),r--;
		while(l<q[i].l) del(l),l++;
		if(q[i].op==1) {
			Q=b&(b>>q[i].x);
			if(Q.count()) A[q[i].id]=1;
		}
		else if(q[i].op==2) {
			Q=b&(c>>N-q[i].x);
			if(Q.count()) A[q[i].id]=1;
		}
		else {
			for(int j=1;j*j<=q[i].x;j++) {
				if(q[i].x%j==0&&b[j]&&b[q[i].x/j]) A[q[i].id]=1;
			}
            // if(sqrt(q[i].x)*sqrt(q[i].x)==q[i].x&&siz[(int)sqrt(q[i].x)]>=2) 
            //     A[q[i].id]=1;
		}
	}
	for(int i=1;i<=m;i++) 
		if(A[i]) cout<<"hana"<<endl;
		else cout<<"bi"<<endl;
	return 0;
}

帶修莫隊

我是想把帶修莫隊講的通俗易懂一些，然而ta似乎也沒有什么很難的點

首先普通莫隊不能修改，因為一旦修改有的詢問會更改，而有的不會。

所以對于一些簡單的修改，我們可以把修改也離線下來，加一個時間維。

注意到這時莫隊的上限仍然很低，無法高效地處理修改

我們這時就需要重新分析塊長，一般把塊長設為
$n^{\frac 2 3}$，時間復雜度變為$O(n^{\frac 5 3})$，注意這時必須以左端點塊為第一關鍵字，右端點塊為第二關鍵字，時間維我們可以奇偶化亂排

bool cmp(node a,node b) {
	if(pos[a.l]^pos[b.l]) return a.l<b.l;
	else if(pos[a.r]^pos[b.r]) return a.r<b.r;
	else if(pos[a.r]&1) return a.t>b.t;
	else return a.t<b.t;
}
                         
for(int i=1,x,y;i<=m;i++) {
	cin>>opt;x=read(),y=read();
	if(opt=='R') u[++t]={x,y};
	else ++top,q[top]={x,y,t,top};
}
for(int i=1;i<=top;i++) {
	while(q[i].l<l) l--,add(a[l]);
	while(q[i].r>r) r++,add(a[r]);
	while(q[i].l>l) del(a[l]),l++;
	while(q[i].r<r) del(a[r]),r--;
	while(q[i].t>t) t++,upd(t,l,r);
	while(q[i].t<t) upd(t,l,r),t--;
	ans[q[i].id]=sum;
}

不過對于一些復雜的修改，帶修莫隊就無能為力了

P1903 [國家集訓隊] 數顏色 / 維護隊列

板子題，注意先將指針移到對應區間，再修改時間，修改時間時有一個很妙的操作

void add(int p) { if(!cnt[p]) sum++;cnt[p]++; }
void del(int p) { if(cnt[p]==1) sum--;cnt[p]--; }

void upd(int t,int l,int r) {
	if(l<=u[t].p&&u[t].p<=r) del(a[u[t].p]),add(u[t].x);
	swap(a[u[t].p],u[t].x);//下次修改肯定就改回來了，直接交換
}

CF940F Machine Learning

思路放開了就會很容易，觀察mex的性質，發現答案不會超過根號級別，每次暴力找就行

CF1476G Minimum Difference

首先還是上面那個性質，我們發現cnt的值只有根號級別，現在的問題就在于如何處理答案
，有一個比較顯然的思路就是維護一個 $muiltset$
，添上一個 $log$ 復雜度，然后雙指針求解

我們考慮能不能省掉這個log，發現鏈式結構就可以解決這個問題

void add(int x) {
	int h=la[siz[x]],t=nx[siz[x]];
	if(siz[x]&&num[siz[x]]==1) erase(siz[x]);
	num[siz[x]]--;
	siz[x]++;num[siz[x]]++;
	if(num[siz[x]]==1) {
		if(num[siz[x]-1]&&siz[x]-1>0) {
			h=siz[x]-1;
		}
		nx[h]=siz[x],la[siz[x]]=h;
		if(t)la[t]=siz[x];nx[siz[x]]=t;
//		insert(siz[x]);
	}
}
 
void del(int x) {
	int h=la[siz[x]],t=nx[siz[x]];
	if(siz[x]&&num[siz[x]]==1) erase(siz[x]);
	num[siz[x]]--;
	siz[x]--,num[siz[x]]++;
	if(siz[x]&&num[siz[x]]==1) {
		if(num[siz[x]+1]) t=siz[x]+1;
		nx[h]=siz[x],la[siz[x]]=h;
		if(t)la[t]=siz[x];nx[siz[x]]=t;
//		insert(siz[x]);
	}
}

int h=nx[0],j=0;
while(h) b[++j]=h,h=nx[h];
// Copy();
int p1=1,p2=0,ans=1e9,sum=0;
for(;p1<=j;p1++) {
	while(p2<j&&sum<q[i].k) p2++,sum+=num[b[p2]];
	if(sum>=q[i].k) ans=min(ans,b[p2]-b[p1]);
	sum-=num[b[p1]];
}
A[q[i].id]=ans;

回滾莫隊

回滾莫隊是一種神奇的莫隊，正常的莫隊是通過增加和刪除操作完成區間的轉移，但一些情況下，我們可能很難進行這其中的一個操作，即只能輕松進行增加或者刪除操作的一種

回滾莫隊的核心思想就是：既然只能實現一個操作，那么就只使用一個操作，剩下的交給回滾解決。

大致流程為：

按左端點所在塊為第一關鍵字，若相同，按右端點大小排序（若增加即為從小到大，刪除即為從大到小）
若左端點到了一個新塊，重新初始化
- 左右端點在一個塊內，暴力
- 拓展右端點，這部分答案為ans
- 拓展左端點，這部分答案為tmp
- 回滾左端點

復雜度同普通莫隊，同時注意到這時就不能用奇偶化排序了

JOISC 2014 Day1 歷史研究

容易發現刪除操作很難，但是增加很容易

bool cmp(node a,node b) {
	if(pos[a.l]^pos[b.l]) return a.l<b.l;
	else return a.r<b.r;
}

int ans,tmp;

void add(int x,int &y) {
	++cnt[x];
	y=max(y,cnt[x]*b[x]);
}

void del(int x) { --cnt[x]; }

void init() {
	len=n/sqrt(n);
	tot=n/len;
	for(int i=1;i<=tot;i++) L[i]=(i-1)*len+1,R[i]=i*len;
	R[tot]=n;
	for(int i=1;i<=tot;i++) 
		for(int j=L[i];j<=R[i];j++)
			pos[j]=i;
}


for(int i=1;i<=m;i++) {
        if(pos[q[i].l]!=pos[q[i-1].l]) {
        	while(r>R[pos[q[i].l]]) del(a[r]),--r;
        	while(r<R[pos[q[i].l]]) ++r,add(a[r],ans);
			while(l<R[pos[q[i].l]]+1) del(a[l]),++l;
			ans=0;
        }
//        cout<<q[i].l<<" "<<q[i].r<<" "<<l<<" "<<r<<" "<<ans<<endl;
//        for(int j=1;j<=3;j++) cout<<cnt[j]<<" ";cout<<endl;
        if(pos[q[i].l]==pos[q[i].r]) {
        	for(int j=q[i].l;j<=q[i].r;j++) add(a[j],A[q[i].id]);
        	for(int j=q[i].l;j<=q[i].r;j++) del(a[j]);
        	continue;
        }
		while(r<q[i].r) ++r,add(a[r],ans);
		tmp=ans;
		while(l>q[i].l) --l,add(a[l],tmp);
//        cout<<l<<" "<<r<<" "<<tmp<<endl;
		A[q[i].id]=tmp;
		while(l<R[pos[q[i].l]]+1) del(a[l]),++l;
	}

P5906 【模板】回滾莫隊&不刪除莫隊

自己做去

P4137 Rmq Problem / mex

容易發現mex刪除很容易但是增加很困難

這種是只支持刪除的回滾，我自己理解了一種寫法，僅供大家參考

bool cmp(node a,node b) {
	if(pos[a.l]^pos[b.l]) return a.l<b.l;
	else return a.r>b.r;
}

      for(int i=1;i<=m;i++) {
		if(pos[q[i].l]^pos[q[i-1].l]) {
			B=pos[q[i].l];
			l=L[B],r=q[i].r;
			for(int j=0;j<=n;j++) t[j]=0;
			for(int j=L[B];j<=q[i].r;j++) 
				if(a[j]<=n) t[a[j]]++;
			for(int j=0;j<=n;j++) if(!t[j]) { tmp=ans=j;break; }
		}
		if(pos[q[i].l]==pos[q[i].r]) {
			for(int j=q[i].l;j<=q[i].r;j++) 
				if(a[j]<=n) w[a[j]]++;
			for(int j=0;j<=n;j++) if(!w[j]) { A[q[i].id]=j;break; }
			for(int j=q[i].l;j<=q[i].r;j++) 
				if(a[j]<=n) w[a[j]]--;
			continue;
		}
		while(r>q[i].r) add(r,1),r--;
		tmp=ans;
		while(l<q[i].l) add(l,2),l++;
		A[q[i].id]=tmp;
		while(l>L[B]) l--,add(l,3);
	}

樹上莫隊

現在主流的樹上莫隊基本上都是將歐拉序跑下來然后在序列上跑正常莫隊

歐拉序是一個什么東東呢？

void dfs(int p,int f) {
	st[p]=++cnt,o[cnt]=p;
	for(int i:v[p]) {
		if(i==f) continue;
		dfs(i,p);
	}
	ed[p]=++cnt,o[cnt]=p;
}

注意要記錄每個點兩次被遍歷的位置

那這樣有什么用捏？

假如題目要求我們處理一條路徑（從 x 到 y ）

（有些題目要求處理子樹，那么跑dfs序即可，因為子樹中的dfs序是連續的）

這里我們規定 $st[x]<st[y]$，先說結論

$LCA(x,y)==x$,此時y在x子樹中，那么我們就把詢問壓成 $st[x]$ 到 $st[y] $
否則，將詢問壓成 $ed[x]$ 到 $st[y]$,并對 $LCA(x,y)$ 特殊處理

證明：

首先兩種情況都會有出現兩次的點，我們發現對于路徑而言，這些點毫無價值，我們去除這些貢獻
對于第一種情況，顯然路徑上的點只出現一次
對于第二種情況，我們顯然發現LCA的貢獻沒被考慮到，單獨處理即可

證畢。

SP10707 COT2 - Count on a tree II

樹上莫隊板子題，但是大家可能會疑惑上面所講的沒有貢獻的點如何處理，畢竟我們現在壓成了一個序列，~~總不能記錄次數吧（其實也可以起）~~，我們可以用一個vis數組來存儲目前這個位置的狀態（有貢獻 or 無貢獻），當我們再次遍歷到這個位置的時候就將狀態取反

//o 代表的是歐拉序
void Solve(int x) {
	vis[x]?del(c[x]):add(c[x]);vis[x]=vis[x]^1;
}
for(int i=1;i<=m;i++) {
	while(r<q[i].r) r++,Solve(o[r]);
	while(l>q[i].l) l--,Solve(o[l]);
	while(r>q[i].r) Solve(o[r]),r--;
	while(l<q[i].l) Solve(o[l]),l++;
	if(q[i].lca) Solve(q[i].lca);
	A[q[i].id]=ans;
	if(q[i].lca) Solve(q[i].lca);
}

P4074 [WC2013] 糖果公園

這個題目加上了修改操作，改為樹上帶修莫隊即可，值得一提的是筆者寫這個題的時候排序沒有用帶修莫隊的排序，而是用的普通莫隊的排序，~~然后還過了，導致筆者絲毫沒有意識到這件事然后寫另一個題時卡了半天常，最后發現排序鍋了~~，這啟發我們寫莫隊題要清醒（~~選擇大于努力~~）

  
//^ v ^  開心做題 快樂學習 
  
//好戲，開場! 
   
#include<bits/stdc++.h>
// #define int long long
using namespace std;
const int N=2e6+500,P=1e9+21;
int read() {
    int x=0;short f=1;char s=getchar();
    while(s<48||s>57){f=s=='-'?-1:1;s=getchar();}
    while(s>=48&&s<=57){x=x*10+s-48;s=getchar();}
    return x*f;
}

int n,m,T,V[N],w[N],c[N],pos[N];long long A[N],tmp;

vector<int > v[N];

int tim,tot;
struct Fix { int p,x; }u[N];
struct node {
	int l,r,t,lca,id;
}q[N];
int op,x,y;
bool cmp(node a, node b){
	if(pos[a.l]^pos[b.l]) return a.l<b.l;
	else if(pos[a.r]^pos[b.r]) return a.r<b.r;
	else if(pos[a.r]&1) return a.t>b.t;
	else return a.t<b.t;
}

int id[N],st[N],ed[N];
int siz[N],dep[N],top[N],fa[N],son[N];

void dfs1(int p,int f) {
	id[st[p]=++id[0]]=p;
	dep[p]=dep[fa[p]=f]+1,siz[p]++;
	for(int i:v[p]) {
		if(i^f) {
			dfs1(i,p);
			siz[p]+=siz[i];
			if(siz[i]>siz[son[p]]) son[p]=i;
		}
	}
	id[ed[p]=++id[0]]=p;
} 
void dfs2(int p,int t) {
	top[p]=t;
	if(son[p]) dfs2(son[p],t);
	for(int i:v[p]) {
		if(i==fa[p]||i==son[p]) continue;
		dfs2(i,i);
	}
}
int Lca(int x,int y) {
	while(top[x]^top[y]) {
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	return x;
}

bitset<N > vis;
int cnt[N];
void add(int x) { cnt[x]++,tmp+=1ll*w[cnt[x]]*V[x]; }
void del(int x) { tmp-=1ll*w[cnt[x]]*V[x],cnt[x]--; }

void solve(int x) {
	vis[x]?del(c[x]):add(c[x]);vis[x]=vis[x]^1;
} 

void upd(int t) {
	int p=u[t].p;
	if(vis[p]) {
		del(c[p]),add(u[t].x); 
	}
	swap(u[t].x,c[p]);
}


signed main() {
	cin>>n>>m>>T;
	for(int i=1;i<=m;i++) V[i]=read();
	for(int i=1;i<=n;i++) w[i]=read();
	for(int i=1;i<n;i++) {
		int x=read(),y=read();
		v[x].push_back(y),v[y].push_back(x);
	}
	dfs1(1,0),dfs2(1,1);
	int len=pow(id[0],0.666666666666);
	for(int i=1;i<=id[0];i++) 
		pos[i]=(i-1)/len+1; 
	for(int i=1;i<=n;i++) c[i]=read();
	for(int i=1;i<=T;i++) {
		op=read(),x=read(),y=read();
		if(!op) ++tim,u[tim]={x,y};
		else {
			if(st[x]>st[y]) swap(x,y);
			int lca=Lca(x,y);
			if(lca==x) ++tot,q[tot]={st[x],st[y],tim,0,tot};
			else ++tot,q[tot]={ed[x],st[y],tim,lca,tot};
		}
	}
	sort(q+1,q+1+tot,cmp);
	int l=1,r=0,t=0; 
	for(int i=1;i<=tot;i++) {
		while(r<q[i].r) r++,solve(id[r]);
		while(l>q[i].l) l--,solve(id[l]);
		while(l<q[i].l) solve(id[l]),l++;
		while(r>q[i].r) solve(id[r]),r--;
		while(t>q[i].t) upd(t),t--;
		while(t<q[i].t) t++,upd(t);
		int lca=q[i].lca;
		if(lca) add(c[lca]);
		A[q[i].id]=tmp;
		if(lca) del(c[lca]);
	}
	for(int i=1;i<=tot;i++) printf("%lld\n",A[i]);
	return 0;
}

相同類型，基本算是經驗：SP32952 Ada and Football（就是筆者卡了半天常的那個）

CF375D Tree and Queries

這個題就是子樹內問題了，我們直接dfs序即可

題目要求 $ \ge k $ 的數的個數，我們莫隊統計每個數的出現次數是簡單的，但是這個怎么辦的

還記得筆者前文提到過嗎：莫隊天生克制逐步增量的東西，你考慮實際上每個數出現次數加減是一個增量過程，我們設 $num_i$ 為出現次數大于i的數的個數，在增量過程中維護即可

int cnt[N],num[N];
void add(int x) { cnt[x]++,++num[cnt[x]]; }
void del(int x) { --num[cnt[x]],cnt[x]--; }

實際上因為莫隊的逐步增量特性，莫隊的可拓展性很高

在考場中，即使我們不會正解，也可以用莫隊來寫一些暴力，重點就在于思考增量怎么寫，增量代價是多少

筆者曾在模擬賽中利用莫隊拿到了全場最高的暴力分（~~可能是大家都會正解沒人寫暴力~~），其中增量代價也并不是 $O(1)$，而是 $O(log n)$ ,讀者在考場上也可以先思考普通暴力，然后觀察能不能轉為莫隊

莫隊二次離線

因為筆者時間原因（~~和實力原因~~），二離板子（第十四分塊前提）和第十四分塊并沒有寫，只帶來了兩道比較簡單的題目，而且目前讀者對二離的理解還不夠深刻，有些地方可能講解不清，還請讀者見諒

有些時候，我們會遇到一些看起來很適合莫隊的題目，但是轉移復雜度不是 $O(1)$，導致復雜度不對

并且這時候我們驚奇的發現增量的貢獻可以差分,我們用 $f(x,l,r)$ 表示x關于 $[l,r]$ 的貢獻

即 $f(x,l,r)=f(x,1,r)-f(x,1,l-1)$

這時候我們考慮將增量操作都離線下來，最后再一起處理

我們觀察到當區間 $[l,r]$ 擴展到 $[l,r+1]$ 時

$f(r+1,l,r)=f(r+1,1,r)-f(r+1,1,l-1)$

前一項顯然是可以預處理的，后一項發現l-1是固定的，可以把每個這樣的增量都離線到對應的 $[l - 1]$ 上，最后從小到大處理即可。其他幾個方向也是類似的

這樣，把增量操作離線下來，就叫二次離線啦

P5501 [LnOI2019] 來者不拒，去者不追

設 $f(x,l,r)$ 為 $[l,r]$ 中比a_x大的數的和，$g(x,l,r)$ 為 $[l,r]$ 中比 $a_x$ 小的個數

增量 $F(r+1,l,r)=f(x,l,r)+a_{r+1}*g(x,l,r)$

即 $F(r+1,l,r)=f(x,1,r)-f(x,1,l-1)+a_{r+1}*[ g(r+1,1,r)-g(r+1,1,l-1)]$

其中 $f(r+1,1,r)$ 和 $g(r+1,1,r)$ 可以預處理，剩下的我們離線

我們這里有一個優化空間技巧:我們發現每次指針移動都是連續的,所以我們只需要存連續的一段即可，空間復雜度從 $O(n \sqrt n)$ 降到了 $O(n)$

然后我們發現操作變為了：在集合中加入一個數，查詢一個數在集合中排名，查詢集合中比某個數大的數之和

其中加入操作只有 $O(n)$ 次，而查詢操作卻有 $O(n \sqrt n)$ 次，
使用 $O(\sqrt n)$ 修改, $O(1)$ 查詢的值域分塊即可,算上莫隊，總時間復雜度$O(n \sqrt n)$

其他幾個方向也是類似的

  
//^ v ^  開心做題 快樂學習 
  
//好戲，開場! 
   
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+500,P=1e9+21;
int read() {
    int x=0;short f=1;char s=getchar();
    while(s<48||s>57){f=s=='-'?-1:1;s=getchar();}
    while(s>=48&&s<=57){x=x*10+s-48;s=getchar();}
    return x*f;
}

int n,m,lsh[N],a[N],pos[N],lim,len,qz[N];

int f[N],g[N],S[N],A[N];
struct BIT {
	int t[N];
	void add(int x,int k) { for(;x<=lim;x+=x&-x) t[x]+=k; }
	int query(int x) { int sum=0; for(;x;x-=x&-x) sum+=t[x]; return sum; }
}F,G;

struct Query {
	int l,r,id,op;
}q[N];

bool cmp(Query a,Query b) {
	if(pos[a.l]^pos[b.l]) return a.l<b.l;
	else if(pos[a.l]&1) return a.r<b.r;
	else return a.r>b.r;
}


void LSH() {
	len=sqrt(n);
	for(int i=1;i<=n;i++) a[i]=read(),lim=max(lim,a[i]),pos[i]=(i-1)/len+1,qz[i]=qz[i-1]+a[i];
	for(int i=1;i<=n;i++) {
		F.add(a[i],a[i]);  f[i]=f[i-1]+F.query(lim)-F.query(a[i]);
		G.add(a[i],1);     g[i]=g[i-1]+a[i]*(G.query(a[i]-1));
//		cout<<F.query(lim)-F.query(a[i])<<" "<<a[i]*G.query(a[i]-1)<<endl;
	}
}

vector<Query > v[N];

int L[N],R[N],qf[N],qg[N],tf[N],tg[N];

int nf(int x) { return qf[x]+tf[pos[x]]; }
int ng(int x) { return qg[x]+tg[pos[x]]; }

void Block() {
	len=sqrt(lim);
//	cout<<lim<<" "<<len;
	int bcnt=lim/len;if(bcnt*len<lim) bcnt++;
	for(int i=1;i<=bcnt;i++) {
		L[i]=(i-1)*len+1,R[i]=i*len;
		for(int j=L[i];j<=R[i];j++) pos[j]=i;
	}R[bcnt]=lim;
//	cout<<pos[2]<<" ";
	for(int i=1;i<=n;i++) {
		for(int j=a[i]+1;j<=R[pos[a[i]]];j++) qg[j]++;
		for(int j=pos[a[i]]+1;j<=bcnt;j++) tg[j]++;
		for(int j=a[i]-1;j>=L[pos[a[i]]];j--) qf[j]+=a[i];
		for(int j=pos[a[i]]-1;j;j--) tf[j]+=a[i];
		// for(int j=1;j<=lim;j++) cout<<ng(j)<<" "<<nf(j)<<"   ";
		for(auto t:v[i]) {
			for(int j=t.l;j<=t.r;j++) {
				S[t.id]+=t.op*(nf(a[j])+a[j]*(ng(a[j])));
			}
		}
		// cout<<endl;
	}
}


signed main() {
	cin>>n>>m;LSH();
	for(int i=1;i<=m;i++) {
		q[i]={read(),read(),i,0};
	}
	sort(q+1,q+1+m,cmp);
	int l=1,r=0;
	for(int i=1;i<=m;i++) {
        // cout<<q[i].id<<" ";
		if(r<q[i].r) {
			S[i]+=f[q[i].r]-f[r];
			S[i]+=g[q[i].r]-g[r];
			v[l-1].push_back({r+1,q[i].r,i,-1});
			r=q[i].r;
		}
		if(l>q[i].l) {
			S[i]-=f[l-1]-f[q[i].l-1];
			S[i]-=g[l-1]-g[q[i].l-1];
			v[r].push_back({q[i].l,l-1,i,1});
			l=q[i].l;
		}
		if(r>q[i].r) {
			S[i]-=f[r]-f[q[i].r];
			S[i]-=g[r]-g[q[i].r];
			v[l-1].push_back({q[i].r+1,r,i,1});
			r=q[i].r;
		}
		if(l<q[i].l) {
			S[i]+=f[q[i].l-1]-f[l-1];
			S[i]+=g[q[i].l-1]-g[l-1];
			v[r].push_back({l,q[i].l-1,i,-1});
			l=q[i].l;
		}
	}
	// cout<<S[1]<<endl;
	Block();
	for(int i=1;i<=m;i++) S[i]+=S[i-1],A[q[i].id]=S[i]+qz[q[i].r]-qz[q[i].l-1];
	for(int i=1;i<=m;i++) printf("%lld\n",A[i]);
    return 0;
}

P5047 [Ynoi2019 模擬賽] Yuno loves sqrt technology II

題目要求逆序對數

我們設 $f(x,l,r)$ 為區間 $[l,r]$ 中比 $ a_x$ 大的數，設 $g(x,l,r)$ 為區間 $[l,r]$ 中比 $a_x$ 小的數

然后4個轉移方向隨便推一下，發現這個依舊可以使用上面提到的值域分塊，大家仿照著推一推，這道筆者就留作給大家的練習吧，貼一下代碼

  
//^ v ^  開心做題 快樂學習 
  
//好戲，開場! 
   
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+500,P=1e9+21;
int read() {
    int x=0;short f=1;char s=getchar();
    while(s<48||s>57){f=s=='-'?-1:1;s=getchar();}
    while(s>=48&&s<=57){x=x*10+s-48;s=getchar();}
    return x*f;
}

int n,m,lsh[N],a[N],pos[N],lim,len;

int f[N],g[N],S[N],A[N];
struct BIT {
	int t[N];
	void add(int x,int k) { for(;x<=lim;x+=x&-x) t[x]+=k; }
	int query(int x) { int sum=0; for(;x;x-=x&-x) sum+=t[x]; return sum; }
}SZ;

struct Query {
	int l,r,id,op;
}q[N];

bool cmp(Query a,Query b) {
	if(pos[a.l]^pos[b.l]) return a.l<b.l;
	else if(pos[a.l]&1) return a.r<b.r;
	else return a.r>b.r;
}


void LSH() {
	int b[N];
	len=sqrt(n);
	for(int i=1;i<=n;i++) a[i]=b[i]=read(),pos[i]=(i-1)/len+1;
	sort(b+1,b+1+n);
	len=unique(b+1,b+1+n)-b-1;
	for(int i=1;i<=n;i++) 
		a[i]=lower_bound(b+1,b+1+len,a[i])-b;
	lim=len;
	for(int i=1;i<=n;i++) {
		SZ.add(a[i],1);
		f[i]=i-SZ.query(a[i])+f[i-1];
		g[i]=SZ.query(a[i]-1)+g[i-1];
	}
}

vector<Query > v[N];

int L[N],R[N],qz[N],tag[N];
int num(int x) { return qz[x]+tag[pos[x]]; }
void Block() {
	len=sqrt(lim);
	int bcnt=lim/len;bcnt++;
	for(int i=1;i<=bcnt;i++) {
		L[i]=(i-1)*len+1;R[i]=i*len;
		for(int j=L[i];j<=R[i];j++) pos[j]=i;
	} R[bcnt]=lim;
	for(int i=1;i<=n;i++) {
		int x=a[i];
		for(int j=x;j<=R[pos[x]];j++) {
			qz[j]++;
		}
		for(int j=pos[x]+1;j<=bcnt;j++) tag[j]++;
		for(auto t:v[i]) {
			if(t.op==1) 
				for(int j=t.l;j<=t.r;j++) S[t.id]+=num(lim)-num(a[j]);
			else if(t.op==-1) 
				for(int j=t.l;j<=t.r;j++) S[t.id]-=num(lim)-num(a[j]);
			else if(t.op==2) 
				for(int j=t.l;j<=t.r;j++) S[t.id]+=num(a[j]-1);
			else if(t.op==-2) 
				for(int j=t.l;j<=t.r;j++) S[t.id]-=num(a[j]-1);
		}
	}
}

signed main() {
	cin>>n>>m;LSH();
	for(int i=1;i<=m;i++) {
		q[i]={read(),read(),i,0};
	}
	sort(q+1,q+1+m,cmp);
	int l=1,r=0;
	for(int i=1;i<=m;i++) {
		if(r<q[i].r) {
			S[i]+=(f[q[i].r]-f[r]);
			v[l-1].push_back({r+1,q[i].r,i,-1});
			r=q[i].r;
		}
		if(l>q[i].l) {
			S[i]-=(g[l-1]-g[q[i].l-1]);
			v[r].push_back({q[i].l,l-1,i,2});
			l=q[i].l;
		}
		if(r>q[i].r) {
			S[i]-=(f[r]-f[q[i].r]);
			v[l-1].push_back({q[i].r+1,r,i,1});
			r=q[i].r;
		}
		if(l<q[i].l) {
			S[i]+=(g[q[i].l-1]-g[l-1]);
			v[r].push_back({l,q[i].l-1,i,-2});
			l=q[i].l;
		}
	}
	Block();
	for(int i=1;i<=m;i++) {
		S[i]+=S[i-1];A[q[i].id]=S[i];
	}
	for(int i=1;i<=m;i++) printf("%lld\n",A[i]);
    return 0;
}

補充一些好題

由于這個課件筆者斷斷續續寫了好久，所以后來做了一些好題沒來得及放，就當做補充啦

P5268 [SNOI2017] 一個簡單的詢問

原式是這個 $\sum\limits_{x=0}^\infty get(l_1,r_1,x)*{get}(l_2,r_2,x)$

顯然可以化成 $(get(1,r_1,x)-get(1,l_1-1,x))*(get(1,r_2,x)-get(1,l_2-1,x))$

為了方便我們簡寫為 $g(r,x)$

然后變為 $\sum\limits_{x=1}^\infty g(r_1,x)g(r_2,x)-g(r_1,x)g(l_2-1,x)-g(l_1-1,x)g(r_2,x)+g(l_1-1,x)g(l_2-1,x)$

將一個詢問拆為4個跑即可，這個形式的莫隊處理增量其實也不太一樣

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+50,P=1e9+7;
int read() {
	int x=0;short f=1;char s=getchar();
	while(s<48||s>57){f=s=='-'?-1:1;s=getchar();}
	while(s>=48&&s<=57){x=x*10+s-48;s=getchar();}
	return x*f;
}

int n,m,l,r,a[N],b[N],A[N];
int len,tot,pos[N],cl[N],cr[N],ans;

struct node { int l,r,id,op; }q[N];
bool cmp(node a,node b) {
	if(pos[a.l]^pos[b.l]) return a.l<b.l;
	else if(pos[a.l]&1) return a.r<b.r;
	else return a.r>b.r;
}

void add(int p,int op) {
	int x=a[p];
	if(op==1) {
		ans+=cr[x];cl[x]++;
	}
	else ans+=cl[x],cr[x]++;
}

void del(int p,int op) {
	int x=a[p];
	if(op==1) {
		ans-=cr[x];cl[x]--;
	}
	else ans-=cl[x],cr[x]--;
}

signed main() {
	cin>>n;
	len=sqrt(n);
	for(int i=1;i<=n;i++) a[i]=read(),pos[i]=(i-1)/len+1;
	pos[n+1]=n;
	cin>>m;
	for(int i=1;i<=m;i++) {
		int l1=read(),r1=read(),l2=read(),r2=read();
		l1--,l2--;
		q[++tot]={min(r1,r2),max(r1,r2),i,1};
		if(l1) q[++tot]={min(l1,r2),max(l1,r2),i,-1};
		if(l2) q[++tot]={min(l2,r1),max(l2,r1),i,-1};
		if(l1&&l2) q[++tot]={min(l1,l2),max(l1,l2),i,1};
	}
	sort(q+1,q+1+tot,cmp);
	l=0,r=0;
	for(int i=1;i<=tot;i++) {
		while(r<q[i].r) r++,add(r,2);
		while(l<q[i].l) l++,add(l,1);
		while(l>q[i].l) del(l,1),l--;
		while(r>q[i].r) del(r,2),r--;
		A[q[i].id]+=ans*q[i].op;
	}
	for(int i=1;i<=m;i++) printf("%lld\n",A[i]);
	return 0;
}

P4689 [Ynoi Easy Round 2016] 這是我自己的發明

可以先思考一下根始終為1的情況，發現這不就是上一個題目的換皮嗎，就換成了dfn序而已

然后我們考慮換根

$rt=v$ ，此時v對應區間為整棵樹
rt不在v的子樹里，此時發現v的子樹不變，區間為 $[dfn_v,dfn_v+siz_v-1]$
rt在v的某個兒子x子樹內，那么 v 的子樹就是整棵樹去掉x這個兒子的子樹

這時候可能會出現子樹在我們跑出來的dfn序上不連續的情況，我們把dfn序復制一遍即可

~~聽說還有狠人把詢問拆成了16個或9個，感覺有點意思~~

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=4e6+50,P=1e9+7;
int read() {
	int x=0;short f=1;char s=getchar();
	while(s<48||s>57){f=s=='-'?-1:1;s=getchar();}
	while(s>=48&&s<=57){x=x*10+s-48;s=getchar();}
	return x*f;
}

long long A[N];
int n,m,l,r,a[N],b[N],opt,l1,r1,l2,r2;
int len,tot,pos[N],cl[N],cr[N],ans,o[N];
vector<int > v[N];

struct node { int l,r,id,op; }q[N];
bool cmp(node a,node b) {
	if(pos[a.l]^pos[b.l]) return a.l<b.l;
	else if(pos[a.l]&1) return a.r<b.r;
	else return a.r>b.r;
}

void add(int p,int op) {
	int x=a[p];
	if(op==1) {
		ans+=cr[x];cl[x]++;
	}
	else ans+=cl[x],cr[x]++;
}

void del(int p,int op) {
	int x=a[p];
	if(op==1) {
		ans-=cr[x];cl[x]--;
	}
	else ans-=cl[x],cr[x]--;
}

void Add(int l1,int r1,int l2,int r2) {
	++A[0];
	l1--,l2--;
	q[++tot]={min(r1,r2),max(r1,r2),A[0],1};
	if(l1) q[++tot]={min(l1,r2),max(l1,r2),A[0],-1};
	if(l2) q[++tot]={min(l2,r1),max(l2,r1),A[0],-1};
	if(l1&&l2) q[++tot]={min(l1,l2),max(l1,l2),A[0],1};
}

void Solve() {
	sort(q+1,q+1+tot,cmp);
	l=0,r=0;
	for(int i=1;i<=tot;i++) {
		while(r<q[i].r) r++,add(o[r],2);
		while(l<q[i].l) l++,add(o[l],1);
		while(l>q[i].l) del(o[l],1),l--;
		while(r>q[i].r) del(o[r],2),r--;
		A[q[i].id]+=ans*q[i].op;
	}
	for(int i=1;i<=A[0];i++) printf("%lld\n",A[i]);
}

int rt,dfn[N],siz[N],fa[N],top[N],dep[N],son[N];

void dfs1(int p,int f) {
	dep[p]=dep[fa[p]=f]+1;siz[p]++;
	for(int i:v[p]) {
		if(i==f) continue;
		dfs1(i,p);
		siz[p]+=siz[i];
		if(siz[son[p]]<siz[i]) son[p]=i;
	}
}

void dfs2(int p,int t) {
	top[p]=t;
	dfn[p]=++dfn[0],o[dfn[0]]=p;
	if(son[p]) dfs2(son[p],t);
	for(int i:v[p]) {
		if(i==son[p]||i==fa[p]) continue;
		dfs2(i,i);
	}
}

int get(int x,int y) {
	while(top[x]^top[y]) {
		if(dep[x]<dep[y]) swap(x,y);
		if(fa[top[x]]==y) break;
		x=fa[top[x]];
	}
	if(dep[x]<dep[y]) swap(x,y);
	return fa[top[x]]==y?top[x]:son[y];
}

signed main() {
	cin>>n>>m;
	for(int i=1;i<=n;i++) b[i]=a[i]=read();
	sort(b+1,b+1+n);
	len=unique(b+1,b+1+n)-b-1;
	for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+len,a[i])-b;
	len=sqrt(n);
	for(int i=1;i<=n+n;i++) pos[i]=(i-1)/len+1;
	for(int i=1;i<n;i++) {
		l=read(),r=read();
		v[l].push_back(r),v[r].push_back(l);
	}
	dfs1(1,0);
	dfs2(1,1);
	for(int i=1;i<=n;i++) o[i+n]=o[i];
	rt=1;
	for(int i=1;i<=m;i++) {
		opt=read();
		if(opt&1) rt=read();
		else {
			l=read(),r=read();
			if(rt==l) l1=1,r1=n;
			else if(dfn[rt]>=dfn[l]&&dfn[rt]<=dfn[l]+siz[l]-1) {
				l=get(l,rt);
				l1=dfn[l]+siz[l],r1=n+dfn[l]-1;
			}
			else l1=dfn[l],r1=dfn[l]+siz[l]-1;
			if(rt==r) l2=1,r2=n;
			else if(dfn[rt]>=dfn[r]&&dfn[rt]<=dfn[r]+siz[r]-1) {
				r=get(r,rt);
				l2=dfn[r]+siz[r],r2=n+dfn[r]-1;
			}
			else l2=dfn[r],r2=dfn[r]+siz[r]-1;
			Add(l1,r1,l2,r2);
		}
	}
	Solve();
	return 0;
}

P4688 [Ynoi Easy Round 2016] 掉進兔子洞

題意即為三個集合的大小之和除去三個集合的交集大小的3倍，肯定不能暴力做嗎，我們考慮用bitset，我們進行不去重的離散化（doge）,不去重的話意味著一個值在bitset里可以有多個相鄰下標，那我們就可以用bitset表示多個相同的數，再取交集就好了

然后lxl卡我們空間啊，分組做就好了

#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int T_T=1e4,N=1e5+50,P=1e9+7;
int read() {
	int x=0;short f=1;char s=getchar();
	while(s<48||s>57){f=s=='-'?-1:1;s=getchar();}
	while(s>=48&&s<=57){x=x*10+s-48;s=getchar();}
	return x*f;
}

int n,m,l,r,a[N],b[N];

int len,tot,L[N],R[N],pos[N],cnt[N],A[N];

struct node {
	int l,r,id;
}q[N];
bool cmp(node a,node b) {
	if(pos[a.l]^pos[b.l]) return a.l<b.l;
	else if(pos[a.l]&1) return a.r<b.r;
	else return a.r>b.r;
}

bitset<N > B[10050],tmp;


void add(int p) {
	int x=a[p];
	cnt[x]++;
	tmp[x+cnt[x]-1]=1;
}

void del(int p) {
	int x=a[p];
	cnt[x]--;
	tmp[x+cnt[x]]=0;
}

void init() {
	len=n/sqrt(m);tot=n/max(1,len);
	for(int i=1;i<=tot;i++) L[i]=(i-1)*len+1,R[i]=i*len;
	R[tot]=n;
	for(int i=1;i<=tot;i++) 
		for(int j=L[i];j<=R[i];j++)
			pos[j]=i;
}

signed main() {
	cin>>n;cin>>m;
	for(int i=1;i<=n;i++) b[i]=a[i]=read();
	sort(b+1,b+1+n);init();
	for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+n,a[i])-b;
	while(m>0) {
		int siz=min(m,T_T);
		tmp.reset();
		for(int i=1;i<=n;i++) cnt[i]=0;
		for(int i=1;i<=siz;i++) B[i].set(),A[i]=0;
		for(int i=1;i<=siz;i++) 
			for(int j=1;j<=3;j++) {
				l=read(),r=read();
				A[i]+=(r-l)+1;
				q[(i-1)*3+j]={l,r,i};
			}
		sort(q+1,q+1+3*siz,cmp);
		l=1,r=0;
		for(int i=1;i<=3*siz;i++) {
			while(l>q[i].l) l--,add(l);
			while(r<q[i].r) r++,add(r);
			while(l<q[i].l) del(l),l++;
			while(r>q[i].r) del(r),r--;
			B[q[i].id]&=tmp;
		}
		for(int i=1;i<=siz;i++) printf("%d\n",A[i]-3*B[i].count());
		m-=T_T;
	}
	return 0;
}

后記

以后可能會接著完善哦，比如補幾個二離的板子或者加幾個好題，可以關注我的博客：OvO

posted @ 2025-07-03 07:57 Mortis_Life 閱讀(130) 評論(8) 收藏舉報

刷新頁面返回頂部

Loading

MortisLife