[BZOJ 2038]小Z的襪子 莫隊（Mo's Algorithm）模闆題

今天總算撸懂了莫隊

貼一個模闆題代碼 小Z的襪子

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int max_n=500005; 
int n,m,size;
int hose[max_n],pos[max_n];
long long tot[max_n];
class Query
{
	public:
		int l;int r;int id;long long a,b;
}q[max_n];
bool cmp(Query a,Query b)
{
	if(pos[a.l]==pos[b.l]) return a.r<b.r;
	else return pos[a.l]<pos[b.l];
}
int L=1,R=0;
long long ans=0;
void change(int val,int cl)
{
	ans-=tot[cl]*tot[cl];
	tot[cl]+=val;
	ans+=tot[cl]*tot[cl];
}
long long gcd(long long a,long long b) { return b==0?a:gcd(b,a%b); }
void work()
{
	for(register int i=1;i<=m;i++)
	{
		if(q[i].l==q[i].r) q[i].a=0,q[i].b=1;
		else
		{
			while(L<q[i].l) change(-1,hose[L]),L++;
			while(L>q[i].l) L--,change(1,hose[L]);
			while(R<q[i].r) R++,change(1,hose[R]);
			while(R>q[i].r) change(-1,hose[R]),R--;
			q[i].a=ans-(q[i].r-q[i].l+1);q[i].b=(long long)(q[i].r-q[i].l+1)*(q[i].r-q[i].l);
			long long k=gcd(q[i].a,q[i].b);
			q[i].a/=k;q[i].b/=k;
		}
	}
}
bool outcmp (Query a ,Query b) { return a.id<b.id;}
void output()
{
	sort(q+1,q+1+m,outcmp);
	for(register int i=1;i<=m;i++)
		printf("%lld/%lld\n",q[i].a,q[i].b);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(register int i=1;i<=n;i++)
		scanf("%d",&hose[i]);
	size=(int)sqrt(n+0.5);
	for(register int i=0;i<=n;i++)
		pos[i]=i/size;
	for(register int i=1;i<=m;i++)
		scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
	sort(q+1,q+1+m,cmp);
	work();
	output();
	return 0;
}
           

自己寫了一種比較舒服的區間增減

如果目前已知區間的左端點小于詢問區間的左端點，則需要将目前已知區間的左端點向右移。每次右移之前都需要先減去目前點對答案的影響。

如果目前已知區間的左端點大于詢問區間的左端點，則需要将目前已知區間的左端點向左移。每次左移之後都需要再加上目前點對答案的影響。

右區間同理

while(L<Q.L) Modify(L,-1),L++;
while(L>Q.L) L--,Modify(L,1);
while(R<Q.R) R++,Modify(R,1);
while(R>Q.R) Modify(R,-1),R--;
           

Modify操作的實作步驟：

在答案中減去目前狀态未被修改時對答案的貢獻，進行修改操作後，再在答案中加上該狀态被修改後對答案的新計算出的貢獻。