暴力

莫队

区间问题

Posted by JU on May 13, 2018

莫队，乃离线处理区间询问(修改)，(可能是)万能的算法。

仅查询

例题：洛谷P2709
很明显，若已经求出了[L,R]区间中，每个数出现的次数(c[])，那么就可以用O(1)的时间转移到｛[L-1,R]/[L+1,R]/[L,R-1]/[L,R+1]｝这些区间，并求出这些区间的答案与c[]。然后，也可以用这种近乎暴力的方式转移到下一个区间，并一个一个地求出所有答案。
然而，这与暴力实际上没啥区别，甚至比暴力还慢。容易想到，通过调整每个询问的顺序，可以优化该算法的时间复杂度。于是，将n个数分成block(block=sqrt(n))段，每段有block个数，并按照(左端点位于的块小 || 左端点位于的块相同但右端点小)的方法排序：

bool W1 (MD a,MD b)
{
	long long a1=a.l/block,b1=b.l/block;
	return (a1<b1) || (a1==b1)&&(a.r<b.r);
}

经过玄学排序后，可以证明，莫队算法的时间复杂度已经变成了惊人的O(n^(3/2))。。。

#include <bits/stdc++.h>
using namespace std;
const int N=100100;
struct MD
{
	long long l,r,id,ans;long long an;
}s[N];
long long block;
long long lin[N],v[N],ANS,L,R;
bool W1 (MD a,MD b)
{
	long long a1=a.l/block,b1=b.l/block;
	return (a1<b1) || (a1==b1)&&(a.r<b.r);
}
bool W2 (MD a,MD b)
{
	return (a.id<b.id);
}
void add (long long x,long long add)
{
	long long ol=lin[v[x]],ne=lin[v[x]]+add;
	ANS-=ol*ol; ANS+=ne*ne;
	lin[v[x]]=ne;
}
int main()
{
	//freopen (".in","r",stdin);
	//freopen (".out","w",stdout);
	long long n,m,k;
	cin>>n>>m>>k;
	block=sqrt (n);
	for (int i=1; i<=n; i++) cin>>v[i];
	for (int i=1; i<=m; i++) cin>>s[i].l>>s[i].r,s[i].id=i;
	sort (s+1,s+m+1,W1);
	L=1,R=0;
	for (int i=1; i<=m; i++)
	{
		while (L<s[i].l) add (L,-1),L++;
		while (L>s[i].l) add (L-1,1),L--;
		while (R<s[i].r) add (R+1,1),R++;
		while (R>s[i].r) add (R,-1),R--;
		s[i].an=ANS;
	}
	sort (s+1,s+m+1,W2);
	for (int i=1; i<=m; i++)
	cout<<s[i].an<<"\n";
	return 0;
}

带修改

例题：洛谷P1903
实际上，带修改的莫队仍然十分暴力。
将block(每块长度)改为n的2/3次方(可以证明此时时间最优)，排序时则按照如下规则：
关键字(左端点所在块，右端点所在块，求当前区间之前修改操作的个数tim)

bool mmp (LGJ q1,LGJ q2)
{
	if (q1.l/block<q2.l/block) return  1;
	if (q1.l/block==q2.l/block && q1.r/block<q2.r/block) return 1;
	if (q1.l/block==q2.l/block && q1.r/block==q2.r/block && q1.tim<q2.tim) return 1;
	return 0;
}//有点丑

然后每当处理一个区间时，先将所有的修改变回求当前区间之前的状态(当然也是一个一个还原啦)，然后再进行与上面不带修改相同的操作。

#include <bits/stdc++.h>
#define sc(p) scanf("%d",&p)
#define pr(p) printf("%d",p)
const int oo=0x7FFFFFFF;
const int o=0x3FFFFFFF;
const int N=1000100;
using namespace std;
int a[N];
struct LGJ
{
	int l,r,tim,an,id;
}s[N];
struct JGL
{
	int old,now,w;
}c[N];
int block;
bool mmp (LGJ q1,LGJ q2)
{
	if (q1.l/block<q2.l/block) return  1;
	if (q1.l/block==q2.l/block && q1.r/block<q2.r/block) return 1;
	if (q1.l/block==q2.l/block && q1.r/block==q2.r/block && q1.tim<q2.tim) return 1;
	return 0;
}
bool nmmp (LGJ q1,LGJ q2)
{
	return q1.id<q2.id;
}
int ans=0,sum[2*N];
void change (int w,int j)
{
	sum[a[w]]+=j;
	if (j==1&&sum[a[w]]==1) ans++;
	if (j==-1&&sum[a[w]]==0) ans--;
}
int L,R,T;
void pre (int w,int col)//将位置在w的数修改为col
{
	if (L<=w&&R>=w)
	{
		sum[a[w]]--; if (sum[a[w]]==0) ans--;
		sum[col]++; if (sum[col]==1) ans++;
	}
	a[w]=col;
}
int last[2*N];
int main()
{
	//freopen (".in","r",stdin);
	//freopen (".out","w",stdout);
	int n,m;
	sc(n),sc(m);
	for (int i=1; i<=n; i++) sc(a[i]),last[i]=a[i];
	int ask=0,ch=0;
	for (int i=1; i<=m; i++)
	{
		char sb; int x,y;
		cin>>sb; sc(x),sc(y);
		if (sb=='Q') s[++ask].l=x,s[ask].r=y,s[ask].tim=ch,s[ask].id=i;
		else c[++ch].w=x,c[ch].old=last[x],c[ch].now=y,last[x]=y;
		//记录修改操作(位置，修改前后的值)
		//last[]记录当前所有值
	}
	block=pow (n,2.0/3.0);
	sort (s+1,s+ask+1,mmp);
	L=1,R=0,T=0;
	for (int i=1; i<=ask; i++)
	{
		while (T<s[i].tim) { T++; pre (c[T].w,c[T].now); }
		while (T>s[i].tim) { pre (c[T].w,c[T].old); T--; }
		while (L>s[i].l) L--,change (L,1);
		while (L<s[i].l) change (L,-1),L++;
		while (R>s[i].r) change (R,-1),R--;
		while (R<s[i].r) R++,change (R,1);
		s[i].an=ans;
	}
	sort (s+1,s+ask+1,nmmp);
	for (int i=1; i<=ask; i++)
	cout<<s[i].an<<endl;
	return 0;
}

时间复杂度

无修查询O(n^(3/2))　 带修改 O(n^(5/3))

CC 原创文章采用CC BY-NC-SA 4.0协议进行许可，转载请注明：“转载自：莫队”
CATALOG
    FRIENDS