莫隊學(xué)習(xí)筆記

概念

莫隊是一種幽雅的暴力。用于處理區(qū)間問題。

核心思想就是把詢問離線下來，然后維護雙指針按一定順序處理每個詢問。精髓就在于一定順序。

首先確定一個塊長，然后將左端點的位置除以塊長，把詢問分成若干塊。在每個塊里按右端點排序。發(fā)現(xiàn)當(dāng)塊長為 \(\sqrt n\) 時兩個指針各移動 \(n\sqrt n\) 次，然后做即可。

模板

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#include<map>
#define int long long
using namespace std;
int n,m,a[100001];
int ans[100001];
int sq;
struct item
{
	int l,r,md,i;
}fucl[1000001];
bool cmp(item a,item b)
{
	if(a.md==b.md) return a.r<b.r;
	return a.md<b.md;
}
void add(int w)
{
	//some
}
void del(int w)
{
	//some
}
signed main()
{
	freopen("god.in","r",stdin);
	freopen("god.out","w",stdout);
//	freopen("D:\\Astro\\C++\\GDOI\\down\\down\\sample\\A\\sample3.in","r",stdin);
//	freopen("D:\\Astro\\C++\\GDOI\\down\\down\\sample\\A\\sample3.out","w",stdout);
	scanf("%lld%lld",&n,&m);
	sq=500;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%lld%lld",&fucl[i].l,&fucl[i].r);
		fucl[i].md=fucl[i].l/sq;
		fucl[i].i=i;
	}
	sort(fucl+1,fucl+m+1,cmp);
	int l,r=0;
	l=1;
	for(int i=1;i<=m;i++)
	{
		while(r<fucl[i].r)
		{
			r++;
			add(a[r]);
		}
		while(r>fucl[i].r)
		{
			del(a[r]);
			r--;
		}
		while(l<fucl[i].l)
		{
			del(a[l]);
			l++;
		}
		while(l>fucl[i].l)
		{
			l--;
			add(a[l]);
		}
		ans[fucl[i].i]=/*some*/;
	}
	for(int i=1;i<=m;i++)
	{
		printf("%lld\n",ans[i]);
	}
}

回滾莫隊

回滾莫隊可以面對刪點麻煩的情況，核心操作是撤銷操作。

與普通莫隊一樣，我們對詢問離線并按值域分塊。假如我們在處理的塊是左端點在 \([l,r]\) 中的。我們最開始把右端點放到 \(r\) 并初始化所有東西。因為右端點有序，所以直接掃過去。每次處理詢問時先處理好右端點，然后左端點從 \(r\) 開始前移到目標(biāo)位置，此時就獲得了答案。再把左端點移動產(chǎn)生的貢獻(xiàn)撤銷。時間復(fù)雜度是 \(n\sqrt n\)。需要注意的是撤銷的時間復(fù)雜度問題。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define int long long
using namespace std;
int n,m,len,answ[200001],a[200001],lsh[200001],sq,fi[200001],la[200001],fii[200001],laa[200001],ans;
struct qw
{
	int l,r,md,i;
}q[200001];
bool vis[200001];
int use[200001],lenn;
bool cmp(qw a,qw b)
{
	if(a.md==b.md) return a.r<b.r;
	return a.md<b.md;
}
void add(int w,int i)
{
	la[w]=max(la[w],i);
	fi[w]=min(fi[w],i);
	ans=max(ans,la[w]-fi[w]);
}
signed main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		lsh[i]=a[i];
	}
	sort(lsh+1,lsh+n+1);
	for(int i=1;i<=n;i++)
	{
		a[i]=lower_bound(lsh+1,lsh+n+1,a[i])-lsh;
	}
	scanf("%lld",&m);
	sq=sqrt(n);
	for(int i=1;i<=m;i++)
	{
		scanf("%lld%lld",&q[i].l,&q[i].r);
		q[i].md=q[i].l/sq;
		q[i].i=i;
	}
	sort(q+1,q+m+1,cmp);
	int l,r;
	q[0].md=-1;
	for(int z=1;z<=n;z++)
	{
		la[z]=-100000000;
		fi[z]=100000000;
	}
	r=(q[1].md+1)*sq;
	r--;
	for(int i=1;i<=m;i++)
	{
		if(q[i].md!=q[i-1].md)
		{
			r=(q[i].md+1)*sq;
			r--;
			for(int z=1;z<=n;z++)
			{
				la[z]=-100000000;
				fi[z]=100000000;
			}
			ans=0;
		}
		if(q[i].r<=(q[i].md+1)*sq) continue;
		while(r<q[i].r)
		{
			r++;
			add(a[r],r);
		}
		l=(q[i].md+1)*sq;
		int anss=ans;
		while(l>q[i].l)
		{
			l--;
			if(!vis[a[l]])
			{
				laa[a[l]]=la[a[l]];
				use[++lenn]=a[l];
				fii[a[l]]=fi[a[l]];
				vis[a[l]]=true;
			}
			laa[a[l]]=max(laa[a[l]],l);
			fii[a[l]]=min(fii[a[l]],l);
			anss=max(anss,laa[a[l]]-fii[a[l]]);
		}
		for(int z=1;z<=lenn;z++)
		{
			vis[use[z]]=false;
		}
		lenn=0;
		answ[q[i].i]=anss;
	}
	for(int i=1;i<=m;i++)
	{
		if(q[i].r<=(q[i].md+1)*sq)
		{
			int anss=0;
			for(int z=q[i].l;z<=q[i].r;z++)
			{
				if(!vis[a[z]])
				{
					laa[a[z]]=-100000000;
					use[++lenn]=a[z];
					fii[a[z]]=100000000;
					vis[a[z]]=true;
				}
				laa[a[z]]=max(laa[a[z]],z);
				fii[a[z]]=min(fii[a[z]],z);
				anss=max(anss,laa[a[z]]-fii[a[z]]);
			}
			answ[q[i].i]=anss;
			for(int z=1;z<=lenn;z++)
			{
				vis[use[z]]=false;
			}
			lenn=0;
		}
	}
	for(int i=1;i<=m;i++)
	{
		printf("%lld\n",answ[i]);
	}
}