[資料結構] 莫隊

[資料結構] 莫隊

莫隊是一種基于分塊思想的離線算法。

本文章介紹初等莫隊。

今天才學會帶修

普通莫隊

[國家集訓隊]小Z的襪子

一個闆子題，要求維護平方和。

直接給出公式吧：

\(ans=\frac{\sum_{i=1}^c x_i^2-(R-L+1)}{(R-L+1)(R-L)}\)

莫隊的基本思想

對左右端點進行分塊，左端點所在塊為第一關鍵字，右端點所在塊為第二關鍵字，這樣就保證了普通莫隊的複雜度是 \(\text O(n\sqrt{n})\) .

初始時 \(l=1,r=0\)，意義是 \([l,r]\) 這段區間已經處理過了，然後根據詢問的左右端點不斷擴充或者撤銷。（具體用四個循環實作）

細節部分

• 特判 \(l=r\) 的情況。
• 防止死循環。
• 一定注意左右端點 \(l,r\) 的把控，細節想到位。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template <typename T>
inline T read(){
	T x=0;char ch=getchar();bool fl=false;
	while(!isdigit(ch)){if(ch=='-')fl=true;ch=getchar();}
	while(isdigit(ch)){
		x=(x<<3)+(x<<1)+(ch^48);ch=getchar();
	}
	return fl?-x:x;
}
const int maxn = 5e4 + 10;
#define LL long long
int c[maxn],t[maxn];
struct node{
	int l,r,id;
	LL a,b;
}a[maxn];
LL gcd(LL a,LL b){
	if(!b)return a;
	return gcd(b,a%b);
}
int block[maxn],n1,n,m;
#define read() read<int>()
#include <cmath>
inline bool cmp(node a,node b){
	if(block[a.l]!=block[b.l])return a.l<b.l;
	return a.r<b.r;
}
inline bool cmp_id(node a,node b){
	return a.id<b.id;
}
LL ans;
inline void update(int p,int val){
	ans-=t[c[p]]*t[c[p]];
	t[c[p]]+=val;
	ans+=(LL)t[c[p]]*t[c[p]];
}
void solve(){
	for(int i=1,l=1,r=0;i<=m;i++){
		while(r<a[i].r)update(r+1,1),r++;
		while(l>a[i].l)update(l-1,1),l--;
		while(r>a[i].r)update(r,-1),r--;
		while(l<a[i].l)update(l,-1),l++;
		if(a[i].l==a[i].r){
			a[i].a=0;a[i].b=1;continue;
		}
		a[i].a=ans-(a[i].r-a[i].l+1);
		a[i].b=1LL*(a[i].r-a[i].l+1)*(a[i].r-a[i].l);
		LL g=gcd(a[i].a,a[i].b);
		a[i].a/=g;a[i].b/=g;
	}
}
int main(){
	n=read();m=read();n1=(int)sqrt(n+0.5);
	for(int i=1;i<=n;i++)c[i]=read();
	for(int i=1;i<=n;i++)block[i]=(i-1)/n1+1;
	for(int i=1;i<=m;i++){
		a[i].l=read();a[i].r=read();a[i].id=i;
	}
	sort(a+1,a+1+m,cmp);
	solve();
	sort(a+1,a+1+m,cmp_id);
	for(int i=1;i<=m;i++)printf("%lld/%lld\n",a[i].a,a[i].b);
	return 0;
}
           

帶修改莫隊

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

與普通莫隊不同的是，帶修改莫隊會 在一個特定的時間點進行對資訊的修改 ，這就需要我們把二進制組改為三元組 \((l,r,time)\) 。

其中時間按照第三關鍵字排序，塊長改為 \(n^{\frac{2}{3}}\)。

複雜度為 \(\text O(n^{\frac{5}{3}})\) 。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template <typename T>
inline T read(){
	T x=0;char ch=getchar();bool fl=false;
	while(!isdigit(ch)){if(ch=='-')fl=true;ch=getchar();}
	while(isdigit(ch)){
		x=(x<<3)+(x<<1)+(ch^48);ch=getchar();
	}
	return fl?-x:x;
}
const int maxn = 1333333 + 10;
#include <cmath>
int n,m,c[maxn],ct[maxn];
int mem[maxn][3],c1,c2,tot[maxn];
int Ans[maxn],n1;
struct node{
	int l,r,t,id;
	bool operator <(const node &x)const{
		if(l/n1 == x.l/n1){
			if(r/n1 == x.r/n1)
				return t<x.t;
			return r<x.r;
		}
		return l<x.l;
	}
}a[maxn];
int ans;
#define read() read<int>()
inline void del(int x){
	if(--tot[x]==0)ans--;
}
inline void add(int x){
	if(++tot[x]==1)ans++;
}
int main(){
	n=read();m=read();n1=pow(n,0.666666);
	for(int i=1;i<=n;i++){
		c[i]=read();ct[i]=c[i];
	}
	for(int i=1;i<=m;i++){
		char op;cin>>op;int x=read(),b=read();
		if(op=='Q'){
			c1++;a[c1]=(node){x,b,c2,c1};
		}
		else {
			c2++;mem[c2][0]=x;mem[c2][1]=ct[x];mem[c2][2]=ct[x]=b;//鏇存敼浣嶇疆锛屽師鏉ワ紝鐜闆湪棰滆壊
		}
	}
	sort(a+1,a+1+c1);
	int l=1,r=0,last=1;
	for(int i=1;i<=c1;i++){
		while(last<=a[i].t){
			if(l<=mem[last][0] && mem[last][0]<=r)
				del(mem[last][1]),add(mem[last][2]);
			c[mem[last][0]]=mem[last][2];
			last++;
		}
		while(last-1>a[i].t){
			if(l<=mem[last-1][0] && mem[last-1][0]<=r)
				del(mem[last-1][2]),add(mem[last-1][1]);
			c[mem[last-1][0]]=mem[last-1][1];
			last--;
		}
		while(r<a[i].r)add(c[r+1]),r++;
		while(l>a[i].l)add(c[l-1]),l--;
		while(r>a[i].r)del(c[r]),r--;
		while(l<a[i].l)del(c[l]),l++;
		Ans[a[i].id]=ans;
	}
	for(int i=1;i<=c1;i++)printf("%d\n",Ans[i]);
	return 0;
}