发布于

AT1219 历史研究

一道回滚莫队的例题。
莫队算法能够解决很多类似于求和的询问问题。但是对于求最值的询问它无能为力。这是因为莫队需要一个区间既能够拓展又能够收缩。
对于求最值类的问题，它只能够拓展，不能够收缩。
这时候我们可以使用一种被称为「回滚莫队」的算法。
具体来说，对于每个块内的询问，我们都分成两部分来处理。一部分是将右端点推进，另一部分则是将左端点推进。对于每一个询问，我们在求得它向右端点推进的值以后，暴力统计上左端点对它的贡献即可。
请注意回滚莫队不能奇偶分块。结合回滚莫队的性质可以很容易理解。 

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
int BLOCK,NUM;
int bl[100005],lb[100005],rb[100005];
struct Query{
	int l;
	int r;
	int id;
	inline bool operator<(const Query &B)const{
		return (bl[l]^bl[B.l])?(bl[l]<bl[B.l]):(r<B.r);
	}
}q[100005];
int n,m,a[100005],cnt1[100005],cnt2[100005],loc[100005],typ[100005];
long long ans[100005];
void init(){
	scanf("%d%d",&n,&m);
	BLOCK=std::sqrt(n);
	NUM=std::ceil((double)n/BLOCK);
	for(int i=1;i<=NUM;++i){
		lb[i]=BLOCK*(i-1)+1;
		rb[i]=BLOCK*i;
		for(int j=lb[i];j<=rb[i];++j){
			bl[j]=i;
		}
	}
	rb[NUM]=n;
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
		loc[i]=a[i];
	}
	std::sort(loc+1,loc+1+n);
	int tot=std::unique(loc+1,loc+1+n)-loc-1;
	for(int i=1;i<=n;++i){
		typ[i]=std::lower_bound(loc+1,loc+1+tot,a[i])-loc;
	}
	for(int i=1;i<=m;++i){
		scanf("%d%d",&q[i].l,&q[i].r);
		q[i].id=i;
	}
	std::sort(q+1,q+1+m);
	int p=1;
	for(int i=0;i<=NUM;++i){
		int l=rb[i]+1,r=rb[i];
		long long nw=0;
		for(int j=1;j<=n;++j){
			cnt1[j]=0;
		}
		for(;bl[q[p].l]==i;++p){
			int ql=q[p].l,qr=q[p].r;
			long long tmp=0;
			if(bl[ql]==bl[qr]){
				for(int j=ql;j<=qr;++j){
					cnt2[typ[j]]=0;
				}
				for(int j=ql;j<=qr;++j){
					++cnt2[typ[j]];
					tmp=std::max(tmp,1ll*cnt2[typ[j]]*a[j]);
				}
				ans[q[p].id]=tmp;
				continue;
			}
			while(r<qr){
				++r;
				++cnt1[typ[r]];
				nw=std::max(nw,1ll*cnt1[typ[r]]*a[r]);
			}
			tmp=nw;
			while(l>ql){
				--l;
				++cnt1[typ[l]];
				nw=std::max(nw,1ll*cnt1[typ[l]]*a[l]);
			}
			ans[q[p].id]=nw;
			while(l<rb[i]+1){
				--cnt1[typ[l]];
				++l;
			}
			nw=tmp;
		}
	}
	for(int i=1;i<=m;++i){
		printf("%lld\n",ans[i]);
	}
}

int main(){
	init();
	return 0;
}
发布于

lp1494 国家集训队 小Z的袜子

令颜色为\(c_i\)为第\(i\)种颜色在给定区间内出现的次数。
则，题目所求为：
$$\frac{\sum_{i=1}^{n}c_{i}(c_{i}-1)}{(r-l)(r-l+1)}$$
展开可以得到：
$$\frac{\sum_{i=1}^{n}c_{i}^2-\sum_{i=1}^{n}c_{i}}{(r-l)(r-l+1)}$$
由性质可得：
$$\sum_{i=1}^{n}c_{i}=r-l+1$$
故而，我们需要求的仅有：
$$\sum_{i=1}^{n}c_{i}^2$$
对于这个式子的求法，我们很容易可以想到莫队。
我们考虑一个区间添加上一个数与删除一个数造成的影响。
令修改的颜色为\(x\)，则：
$$\Delta v=\sum_{i=1}^{n}c_{i}^2-c_{x}^{2}+(c_{x}±1)^2-\sum_{i=1}^{n}c_{i}^2$$
展开可得：
$$\Delta v=1±2c_{x}$$

下面考虑莫队。
莫队的原理大致是，将原数列分块，然后将询问以左端点在原数列中的块为第一关键字，右端点为第二关键词来排序。
虽然说它是一种优化后的暴力，但是，若令一次修改的复杂度是\(f_{n}\)，根据最小直线斯坦纳树的性质，可以证明这么做的复杂度是 \(O(f_{n} n \sqrt{m})\)，可以通过此题。
依据毒瘤lxl的说法，莫队最快的分块大小是\(n/\sqrt{m*2/3}\)
故而我们对原数列分块完以后，将询问排序。然后开始移动区间。
扫一遍即可。
另外就是一个小优化，排序的时候分奇偶排序，也就是说，奇数块右端点递增，偶数块右端点递减。
原理很简单，就是移过去再移回来，路上的点都扫了一遍。 

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
int BLOCK;
int belong[50005];
struct Query{
	int l;
	int r;
	int id;
	int len;
	inline bool operator <(const Query &B)const{
		return (belong[l]^belong[B.l])?(belong[l]<belong[B.l]):((belong[l]&1)?r<B.r:r>B.r);
	}
}q[50005];
long long tot=0;
int cnt[50005];
inline void add(int X){
	tot+=(cnt[X]<<1|1);
	++cnt[X];
}
inline void del(int X){
	tot+=(1-(cnt[X]<<1));
	--cnt[X];
}
inline long long Gcd(long long A,long long B){
	return B?Gcd(B,A%B):A;
}
long long ans1[50005],ans2[50005];
int n,m,a[50005];
void init(){
	scanf("%d%d",&n,&m);
	BLOCK=n/std::sqrt(m*2.0/3.0); 
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
	}
	for(int i=1;i<=m;++i){
		scanf("%d%d",&q[i].l,&q[i].r);
		q[i].id=i;
		q[i].len=q[i].r-q[i].l+1;
		ans2[i]=1;
	}
	for(int i=1;i<=n;++i){
		belong[i]=(i-1)/BLOCK+1;
	}
	std::stable_sort(q+1,q+1+m);
	int l=q[1].l,r=q[1].l-1;
	long long nwgcd;
	for(int i=1;i<=m;++i){
		while(l<q[i].l){
			del(a[l]);
			++l;
		}
		while(l>q[i].l){
			--l;
			add(a[l]);
		}
		while(r>q[i].r){
			del(a[r]);
			--r;
		}
		while(r<q[i].r){
			++r;
			add(a[r]);
		}
		if(tot!=q[i].len){
			ans1[q[i].id]=tot-q[i].len,ans2[q[i].id]=1LL*(q[i].r-q[i].l)*q[i].len;
			nwgcd=Gcd(ans1[q[i].id],ans2[q[i].id]);
			ans1[q[i].id]/=nwgcd,ans2[q[i].id]/=nwgcd;
		}
	}
	for(int i=1;i<=m;++i){
		printf("%lld/%lld\n",ans1[i],ans2[i]);
	}
}

int main(){
	init();
	return 0;
}