发布于

lp4117 Ynoi2018 五彩斑斓的世界

虽然我没有玩过这个Galgame，但是就截图而言画风还是挺可爱的。
抱歉离题了。
这是一道由乃省的省选题。
大家都知道喜欢由乃的某人最喜欢的就是数据结构了。
仔细观察这道题的数据范围，我们可以想到分块。
对于每个块里面数值相同的数维护一个并查集，对于每一个并查集维护它的大小。那么我们每一次修改，如果是暴力修改就只需要改变一个元素所在的集合，如果是整块修改就将并查集合并。
查询的时候块外部分暴力更新，快内部分按块查询即可。
但是这一题的常数简直丧心病狂，毒瘤lxl简直是魔鬼。SIZE大了T，SIZE小了MLE。我卡了整整十九次，最终结合前人优秀经验，使用unsigned char成功卡了过去。
大家记住这组魔法的数字：253-410

#include<iostream>
#include<cstdio>
#include<cmath>
#define MAXNUM 410
int SIZE,NUM;
int bl[100005],lb[MAXNUM],rb[MAXNUM];
int a[100005],tgb[MAXNUM];
int val[100005],mx[100005],fa[100005];
unsigned char cnt[MAXNUM][100005],loc[MAXNUM][100005];
int n,m;
inline int fthr(int X){
	while(X^fa[X]){
		X=fa[X]=fa[fa[X]];
	}
	return X;
}
inline void uni(int X,int A,int B){
	//将X块中的A合并到B处。若B处存在则直接合并，否则将B移动到A并修改A的值。 
	loc[X][B]?fa[loc[X][A]+lb[X]-1]=loc[X][B]+lb[X]-1:(loc[X][B]=loc[X][A],val[loc[X][A]+lb[X]-1]=B);
	cnt[X][B]+=cnt[X][A],cnt[X][A]=loc[X][A]=0;
}
inline void del(int S,int X){
	//如果X比最大值的一半还要小，那么我们考虑将所有小于X的上移，并且修改标记；否则将所有大于X的下移。 
	if((X<<1)<=mx[S]-tgb[S]){
		for(int i=tgb[S]+1;i<=tgb[S]+X;++i){
			if(loc[S][i]){
				uni(S,i,i+X);
			}
		}
		tgb[S]+=X; 
	}else{
		for(int i=X+tgb[S]+1;i<=mx[S];++i){
			if(loc[S][i]){
				uni(S,i,i-X);
			}
		}
		mx[S]=std::min(mx[S],tgb[S]+X);
	}
}
inline void pshd(int X){
	for(int i=lb[X];i<=rb[X];++i){
		a[i]=val[fthr(i)];
		loc[X][a[i]]=cnt[X][a[i]]=0;
		//应当先清空再修改标记。 
		a[i]-=tgb[X];
	}
	for(int i=lb[X];i<=rb[X];++i){
		fa[i]=0;
	}
	tgb[X]=0;
}
inline void updt(int X){
	mx[X]=0;
	for(int i=lb[X];i<=rb[X];++i){
		mx[X]=std::max(mx[X],a[i]);
		loc[X][a[i]]?(fa[i]=loc[X][a[i]]+lb[X]-1):(fa[i]=i,val[i]=a[i],loc[X][a[i]]=i-lb[X]+1);
		++cnt[X][a[i]];
	}
}
inline void chng(int L,int R,int X){
	if(bl[L]^bl[R]){
		pshd(bl[L]),pshd(bl[R]);
		for(int i=L;i<=rb[bl[L]];++i){
			if(a[i]>X){
				a[i]-=X;
			}
		}
		for(int i=lb[bl[R]];i<=R;++i){
			if(a[i]>X){
				a[i]-=X;
			}
		}
		updt(bl[L]),updt(bl[R]);
		for(int i=bl[L]+1;i<=bl[R]-1;++i){
			del(i,X);
		}
	}else{
		pshd(bl[L]);
		for(int i=L;i<=R;++i){
			if(a[i]>X){
				a[i]-=X;
			}
		}
		updt(bl[L]);
	}
}
inline int qry(int L,int R,int X){
	if(bl[L]^bl[R]){
		int rt=0;
		for(int i=L;i<=rb[bl[L]];++i){
			if(val[fthr(i)]-tgb[bl[L]]==X){
				++rt;
			}
		}
		for(int i=lb[bl[R]];i<=R;++i){
			if(val[fthr(i)]-tgb[bl[R]]==X){
				++rt;
			}
		}
		//注意这里减去的是其所在块的lzytg 
		for(int i=bl[L]+1;i<=bl[R]-1;++i){
			rt+=((X+tgb[i]<=100000)?cnt[i][X+tgb[i]]:0);
		}
		return rt;
	}else{
		int rt=0;
		for(int i=L;i<=R;++i){
			if(val[fthr(i)]-tgb[bl[L]]==X){
				++rt;
			}
		}
		return rt;
	}
}
inline void DEBUG(){
	for(int i=1;i<=n;++i){
		printf("%d/%d ",val[fthr(i)],a[i]);
	}
	puts("");
	for(int i=1;i<=NUM;++i){
		printf("[%d %d|%d|%d],",lb[i],rb[i],tgb[i],mx[i]);
	}
	puts("");
	/*
	for(int i=1;i<=100;++i){
		if(loc[2][i]){
			printf("{%d} ",i);
		}
	} 
	*/
}
void init(){
	scanf("%d%d",&n,&m);
	SIZE=253;
	NUM=std::ceil((double)n/SIZE);
	for(int i=1;i<=NUM;++i){
		lb[i]=(i-1)*SIZE+1;
		rb[i]=i*SIZE;
		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);
	}
	for(int i=1;i<=NUM;++i){
		updt(i);
	}
	int op,l,r,x;
	for(int i=1;i<=m;++i){
//		DEBUG();
		scanf("%d%d%d%d",&op,&l,&r,&x);
		if(op==1){
			chng(l,r,x);
		}else{
			printf("%d\n",qry(l,r,x));
		}
	}
}

int main(){
//	freopen("test.out","w",stdout);
	init();
	return 0;
}
发布于

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;
}