CF600E Lomsat gelral

一道树上启发式合并的例题。
首先考虑暴力的做法。统计每一个子节点的信息,然后传到父节点。
我们发现这样做的复杂度是\(O(n^2)\)的。显然,复杂度是错误的。
我们考虑修改统计子节点的顺序。
重链剖分有一个很有意义的性质:一个点通向根的路径上的轻边的数量最多不会超过\(log_n\)。这利用重链剖分的性质可以轻松用反证法证明。
那么,依据这个性质,我们可以统计轻边、上传重边。这也就意味着,对于每一次访问,如果它是一条轻边,那么就把它的信息统计完了清空;如果是一条重边,那么把它的信息上传。
例如,我们现在有一个节点\(X\),那么我们先计算它的所有轻节点,然后我们再计算它的重节点,最后将它除了重节点以外的地方都搜一遍,这样就获得了它的所有信息。
为什么这样做复杂度是对的呢?这就可以基于刚刚那个性质来证明了。具体地来说,一个节点会被清理信息,当且仅当它是一个节点下面的一个轻节点。也就是说,它被清空的次数就是它通向根的路径上轻边的数量。
由刚才那个性质可得,这个值是对数级的,所以复杂度是对的。
注意sm数组的tp的控制。

#include<iostream>
#include<cstdio>
struct ee{
	int v;
	int nxt;
}e[200005];
int h[100005],et=0;
inline void add(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
int sn[100005],sz[100005],a[100005],cnt[100005];
bool kp[100005];
long long ans[100005];//ans表示每个节点的答案 
long long sm[100005];//sn表示出现次数为cnt次的颜色值的和 
int n;
inline void dfs1(int X,int FA){
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v!=FA){
			dfs1(e[i].v,X);
		}
	}
	sz[X]=1;
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v){
			sz[X]+=sz[e[i].v];
			if(sz[e[i].v]>sz[sn[X]]){
				sn[X]=e[i].v;
			}
		}
	}
}
int tp;
inline void rnw(int X,int FA,int V){
	sm[cnt[a[X]]]-=a[X];
	cnt[a[X]]+=V;
	sm[cnt[a[X]]]+=a[X];
	if(sm[tp+1]){
		++tp;
	}
	if(!sm[tp]){
		--tp;
	}
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v!=FA&&!kp[e[i].v]){
			rnw(e[i].v,X,V);
		}
	}
}
inline void dfs2(int X,int FA,int isSn){
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v!=FA&&e[i].v!=sn[X]){
			dfs2(e[i].v,X,0);
		}
	}
	if(sn[X]){
		dfs2(sn[X],X,1);
		kp[sn[X]]=1;
	}
	rnw(X,FA,1);
	kp[sn[X]]=0;
	ans[X]=sm[tp];
	if(!isSn){
		rnw(X,FA,-1);
	} 
}
void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	int u,v;
	for(int i=1;i<n;++i){
		scanf("%d%d",&u,&v);
		add(u,v),add(v,u);
	}
	dfs1(1,0);
	dfs2(1,0,1);
	for(int i=1;i<=n;++i){
		printf("%lld ",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;
}

lp1110 ZJOI2007 报表统计

事实上对于第一类询问和第二类询问我们可以分别处理。
第二类询问的处理方法是非常显然的。由于只有插入而没有删除操作,因此,第二类询问的答案只会缩小、不会增大。
故而,我们对整个数列的值维护一个Splay,每一次插入一个新的数以后,用它和它的前驱与它和它的后继的差的绝对值来更新第二类的答案。
这可以用multiset来简易地实现。
对于第一类询问,我们发现,维护这个值其实并不是难点——用线段树或者平衡树都可以轻松实现。问题在于,如何在插入新的数之后保持这个值。
我们仔细思考,发现,对于任意一段区间来说,它对答案的贡献只有三个:这个区间的答案,这个区间的左端点和这个区间的右端点。
故而,我们建一棵线段树或者平衡树,维护这三个信息(个人认为线段树比较科学。)每一次修改则修改对应的节点,然后递归向上更新即可。
这样就做完了,个人觉得实现难度还是比较低的。

#include<iostream>
#include<cstdio>
#include<set>
#define LS (X<<1)
#define RS (X<<1|1)
#define MID ((L+R)>>1)
inline int Abs(int X){
	return X>0?X:-X;
}

inline int Min(int A,int B){
	return A<B?A:B;
}

std::multiset<int> st;
int ansS=0x3f3f3f3f;
int n,m,a[500005];

class SegmentTree{
	private:
		class Node{
			public:
				int l;
				int r;
				int dlt;
			inline Node(){
				dlt=0x3f3f3f3f;
			}
			inline void init(int V){
				l=r=V;
			}
			inline void psh(int V){
				dlt=Min(dlt,Abs(r-V));
				r=V;
			}
		};
		Node tr[1100000];
		inline void updt(int X){
			tr[X].l=tr[LS].l;
			tr[X].r=tr[RS].r;
			tr[X].dlt=Min(Min(tr[LS].dlt,tr[RS].dlt),Abs(tr[LS].r-tr[RS].l));
		}
		inline void build(int L,int R,int X){
			if(L>R){
				return;
			}
			if(L==R){
				tr[X].init(a[L]);
				return;
			}
			build(L,MID,LS),build(MID+1,R,RS);
			updt(X);
		}
		inline void push(int L,int R,int X,int A,int V){
			if(L>R){
				return;
			}
			if(L==R){
				tr[X].psh(V);
				return;
			}
			A>MID?push(MID+1,R,RS,A,V):push(L,MID,LS,A,V);
			updt(X);
		}
		inline void prnt(int L,int R,int X){
			if(L>R){
				return;
			}
			if(L==R){
				printf("%d:[%d,%d,%d] ",X,tr[X].l,tr[X].r,tr[X].dlt);
				return;
			}
			prnt(L,MID,LS),prnt(MID+1,R,RS);
		}
	public:
		inline void PUSH(int X,int K){
			push(1,n,1,X,K);
		}
		inline void BUILD(){
			build(1,n,1);
		}
		inline int QUERYG(){
			return tr[1].dlt;
		}
		inline void PRINT(){
			prnt(1,n,1);
			puts("");
		}
};

inline void STPUSH(int K){
	st.insert(K);
	std::multiset<int> ::iterator it=st.find(K);
	int ans1,ans2;
	++it;
	if(it!=st.end()){
		ans1=*it;
	}else{
		ans1=0x3f3f3f3f;
	}
	--it;
	if(it!=st.begin()){
		--it;
		ans2=*it;
	}else{
		ans2=0x3f3f3f3f;
	}
	ans1=Abs(K-ans1),ans2=Abs(K-ans2);
	ansS=Min(ansS,Min(ans1,ans2));
}

SegmentTree T;
void init(){
	scanf("%d%d",&n,&m);
	int x;
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
		STPUSH(a[i]);
	}
	T.BUILD();
	char op[10];
	int k;
	for(int i=1;i<=m;++i){
		std::cin>>op;
		switch(op[4]){
			case 'R':{
				scanf("%d%d",&x,&k);
				T.PUSH(x,k);
				STPUSH(k);
				break;
			}
			case 'G':{
				printf("%d\n",T.QUERYG());
				break;
			}
			case 'S':{
				printf("%d\n",ansS);
				break;
			}
			case 'P':{
				T.PRINT();
				break;
			}
		}
	}
}

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