lp3225 HNOI2012 矿场搭建

这实际上是一个 Tarjan 求割点的裸题。

具体来说是这样的。首先,对于每一个连通块,答案显然是独立的。然后,一个连通块至少要有两个出口——这也是容易理解的。

接下来,我们把所有点双都缩成一个点,这时候整张图就一定是一棵无根树。

我们观察这棵树。如果树上只有一个节点,那么两个出口就都必须设在这个点双中;如果树上有多个节点,那么有且仅有叶子节点要各自设一个出口:这是因为,对于非叶子节点,它都有多条路走向叶子节点。

现在问题是如何求出这棵树。我们不妨用 Tarjan 来求。

Tarjan 是一种用于求点双联通分量的常用算法,以其发明者 Tarjan 所命名。特别需要注意的是,这里用到的是 Tarjan 求割点的部分,而不是像圆方树那样求点双的部分。

对于一个点,我们记两个数组,dfn 和 lw,分别表示它的 dfs 序和它在 dfs 树的子树内的所有节点的返祖边中 dfs 最小的节点。

如果某一个节点,它是根节点,并且它在 dfs 树上有超过一个子节点,那么它必然是割点——这是由 dfs 树的性质决定的。

如果一个节点,它的子节点的 lw 总是大等于它的 dfn ,那么就说明它的这棵子树内的所有节点只能抵达它或者它子树内的点,因而它必然是割点。

结合这两条性质即可找出点双。

然后统计一下即可。存在一定的细节。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N=505;
struct ee{
	int v;
	int nxt;
}e[N<<2];
struct Data{
	int u;int v;
}lst[N<<2];
int g[N],h[N],et=0;
inline void Eadd(int U,int V,int *H){
	e[++et]=(ee){V,H[U]};
	H[U]=et;
}
inline void add(int U,int V,int *H){
	Eadd(U,V,H);
	Eadd(V,U,H);
}
int n;
int dfn[N],lw[N],dfsid=0,cnt=0,ag[N],sn[N];
inline void dfs0(int X,int FA){
	dfn[X]=lw[X]=++dfsid;sn[X]=0;
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==FA){
			continue;
		}
		if(!dfn[e[i].v]){
			++sn[X];
			dfs0(e[i].v,X);
			lw[X]=min(lw[X],lw[e[i].v]);
			if((FA&&lw[e[i].v]>=dfn[X])){
				ag[X]=1;
			}
		}else{
			lw[X]=min(lw[X],dfn[e[i].v]);
		}
	}
	if(!FA&&sn[X]>1){
		ag[X]=1;
	}
}
ll vis[N],sm[N],tot[N],cal,sz,nv,deg[N];
inline void dfs1(int X){
	vis[X]=nv;++sz;
	for(int i=h[X];i;i=e[i].nxt){
		if(vis[e[i].v]==nv){
			continue;
		}
		if(ag[e[i].v]){
			vis[e[i].v]=nv;++cal;
			continue;
		}
		dfs1(e[i].v);
	}
}
ll ans,cans,nt;
void init(){
	cnt=et=dfsid=nt=0;
	for(int i=1;i<=n;++i){
		h[i]=dfn[i]=lw[i]=vis[i]=sm[i]=tot[i]=deg[i]=ag[i]=0;
	}
	int u,v;
	for(int i=1;i<=n;++i){
		scanf("%d%d",&u,&v);
		add(u,v,h);
		++deg[u];++deg[v];
		lst[i]=(Data){u,v};
		nt=max(nt,1ll*u);nt=max(nt,1ll*v);
	}
	for(int i=1;i<=nt;++i){
		if(!dfn[i]){
			dfs0(i,0);
		}
	}
//	for(int i=1;i<=nt;++i){
//		printf("%d ",ag[i]);
//	}
//	puts("");
	ans=0,cans=1;
	for(int i=1;i<=nt;++i){
		if(ag[i]){
			if(deg[i]<=1){
				++ans;
			}
		}else if(!vis[i]){
			nv=i;cal=0;sz=0;
			dfs1(i);
			if(cal==1){
				++ans;cans*=sz;
			}else if(cal==0){
				ans+=(sz==1?1:2),cans*=(sz==1?1:sz*(sz-1)/2);
			}
		}
	}
}
int main(){
	scanf("%d",&n);
	int T=0;
	while(n){
		++T;
		init();
		printf("Case %d: %lld %lld\n",T,ans,cans);
		scanf("%d",&n);
	}
	init();
	return 0;
}

lp4577 FJOI2018 领导集团问题

我们尝试类比序列上的情况来看这一题。

对于序列上的情况,我们维护一个集合 \(S\) ,其中 \(S_i\) 表示,长度为 \(i\) 的最长不下降子序列的最后一项的最小值。 那么,对于新的点,我们考虑两种情况:它能加长序列,那么就加长;否则,就尽可能地更新最小值。

对于树上的情况,我们首先尝试考虑一种 \(O(n^2logn)\) 的做法。我们对于每一个节点维护一个集合 \(S_i\), 其中 \(S_{i,j}\) 表示仅用到这个节点及其子树内的所有点,能够构造的大小为 \(j\) 的集合的最小项的最大值。

如果我们把所有子节点的 \(S\) 都已经整合在一起了,那么更新根节点是比较容易的:类比于序列即可。 问题在于子节点要如何合并。

仔细观察,发现,子节点的合并是一个类似于归并的操作。 这样我们就有了一个 \(O(n^2logn)\) 的「高」效做法。

怎么优化这个做法呢? 我们不妨考虑重链剖分启发式合并。这样就将复杂度优化到了 \(O(nlog^2n)\) ,足以通过此题。 具体来说,我们对于每个节点开一个map,然后暴力合并。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#include<set>
using namespace std;
const int N=200005;
struct ee{
	int v;
	int nxt;
}e[N];
int h[N],et=0;
inline void add(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
int w[N],sz[N],sn[N],dep[N],fa[N];
int id[N];
multiset<int> lst[N];
int n;
inline void dfs0(int X){
	sn[X]=0,sz[X]=1;
	for(int i=h[X];i;i=e[i].nxt){
		dfs0(e[i].v);
		sz[X]+=sz[e[i].v];
		if(sz[sn[X]]<sz[e[i].v]){
			sn[X]=e[i].v;
		}
	}
}
inline void dfs1(int X){
	if(sn[X]){
		dfs1(sn[X]);
		id[X]=id[sn[X]];
	}
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==sn[X]){
			continue;
		}
		dfs1(e[i].v);
		lst[id[X]].insert(lst[id[e[i].v]].begin(),lst[id[e[i].v]].end());
	}
	lst[id[X]].insert(w[X]);
	multiset<int>::iterator it=lst[id[X]].lower_bound(w[X]);
	if(it!=lst[id[X]].begin()){
		--it;lst[id[X]].erase(it);
	}
}
void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&w[i]);
		id[i]=i;
	}
	int x;
	for(int i=2;i<=n;++i){
		scanf("%d",&x);
		fa[i]=x;add(x,i);
	}
	dfs0(1);
	dfs1(1);
	printf("%d\n",lst[id[1]].size());
}
int main(){
	init();
	return 0;
}

lp2564 SCOI2009 生日礼物

尺取法即可。
开一个桶维护珍珠的颜色,然后扫一遍。每一次将最前端的点弹出,然后移动至下一个合法点。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

const int N=1000005;
struct data{
	int id;
	int val;
}a[N];
inline bool cmp(const data &A,const data &B){
	return A.val<B.val;
}
int n,K,tp=0;
int bckt[65],cnt=0;
void init(){
	scanf("%d%d",&n,&K);
	int T;
	for(int i=1;i<=K;++i){
		scanf("%d",&T);
		for(int j=1;j<=T;++j){
			++tp;
			scanf("%d",&a[tp].val);
			a[tp].id=i;
		}
	}
	std::sort(a+1,a+1+n,cmp);
	int ans=2147483647;
	int l=1,r=0;
	while(r<n){
		while(r<n){
			++r;
			if(!bckt[a[r].id]){
				++cnt;
			}
			++bckt[a[r].id];
			if(cnt==K){
				break;
			}
		}
		if(cnt==K){
			ans=min(ans,a[r].val-a[l].val);
		}
		while(l<=r){
			--bckt[a[l].id];
			if(!bckt[a[l].id]){
				--cnt;
				++l;
				break;
			}
			++l;
			if(cnt==K){
//				printf("%d %d %d\n",ans,l,r);
				ans=min(ans,a[r].val-a[l].val);
			}
			
		}
	}
	printf("%d\n",ans);
}
int main(){
	init();
	return 0;
}

lp2219 HAOI2007 修筑绿化带

我们知道,如果我们确定了每个大矩形包含的权值最小的小矩形,那么我们只需要枚举一遍每一个大矩形并比较它们的回形部分的最大值。

那么我们考虑用单调队列来预处理出每一个小矩形的权值,然后用二维线段树来维护这个权值,那么我们可以在\(n^2log^2n\)的时间复杂度内完成这道题。
但仔细观察我们感觉\(n^2log^2n\)的时间复杂度对于\(1000\)的数据范围存在一定的困难。我们考虑是否存在一种\(n^2\)复杂度的做法。
有这样一道题叫做理想的正方形。这一题要求的是平面上矩形内最大值和最小值之差。显然,我们可以维护2n个单调队列来计算这个最大值。
那么,对于这题的强化板,我们该怎么做呢?
如果确定了右下角,那么整个矩形的权值是已经固定了的。那么,我们要求的就是那个矩形里面权值最小的子矩形。这一方面是和理想的正方形相同的。
我们不妨设\(c_{i,j}\)表示以(i,j)为右下角的绿化带能包括的花坛的最小值。问题就转变为怎么求出\(c_{i,j}\)。
仔细考虑这个问题,我们发现,每个花坛的最小值是可以预处理的。这样,我们就把这一题转化为了理想的正方形。
同样用二维单调队列维护即可。
需要注意边界条件较为复杂,且不要混淆单调队列里的数的意义。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

const int N=1005;

int n,m,A,B,C,D;
int val[N][N],sm[N][N],a[N][N],b[N][N];
deque<int> q[N],qq;
void init(){
	scanf("%d%d%d%d%d%d",&n,&m,&B,&A,&D,&C);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			scanf("%d",&val[i][j]);
		}
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			sm[i][j]=val[i][j]+sm[i][j-1]+sm[i-1][j]-sm[i-1][j-1];
		}
	}
	for(int i=B;i<=n;++i){
		for(int j=A;j<=m;++j){
			b[i][j]=sm[i][j]-sm[i-B][j]-sm[i][j-A]+sm[i-B][j-A];
//			printf("%d ",b[i][j]);
		}
//		puts("");
	}
	for(int i=D;i<=n;++i){
		for(int j=C;j<=m;++j){
			a[i][j]=sm[i][j]-sm[i-D][j]-sm[i][j-C]+sm[i-D][j-C];
//			printf("%d ",a[i][j]);
		}
//		puts("");
	}
	int ans=0;
	for(int i=D+1;i<n;++i){
		for(int j=C+1;j<m;++j){
//			printf("%d %d\n",i,j);
			while(!q[j].empty()&&a[q[j].back()][j]>a[i][j]){q[j].pop_back();}
			q[j].push_back(i);
			while(!q[j].empty()&&i-q[j].front()>B-D-2){q[j].pop_front();}
		}
		while(!qq.empty()){qq.pop_back();}
		for(int j=C+1;j<m;++j){
			while(!qq.empty()&&a[q[qq.back()].front()][qq.back()]>a[q[j].front()][j]){qq.pop_back();}
			qq.push_back(j);
			while(!qq.empty()&&j-qq.front()>A-C-2){qq.pop_front();}
			if(!qq.empty()&&i>=B-1&&j>=A-1){ans=max(ans,b[i+1][j+1]-a[q[qq.front()].front()][qq.front()]);}
		}
	}
	printf("%d\n",ans);
}
int main(){
	init();
	return 0;
}

lp3313 SDOI2014 旅行

虽然这一题被划在主席树下面,但是一眼看过去这不就是树链剖分动态开点线段树的模板题么。
树链剖分后我们考虑对每一条链,建很多棵线段树,每棵线段树表示这条链上某种颜色的情况,然后大力合并。复杂度显然是对的。
关键是如何动态开点。本质上动态开点长得就和主席树差不多(这可能是为什么这题会被放在主席树下面),但是可能存在很多细节。
另:我的线段树区间查询写成依次单点查询,居然跑到了1.2s,让我一度以为是我常数问题…甚至差点卡进去了。精彩。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

inline int rd(){
	char ch=getchar();int r=0;
	while(!isdigit(ch)){ch=getchar();}
	while(isdigit(ch)){r=r*10+ch-'0';ch=getchar();}
	return r;
}
const int N=100005;
inline int Max(int A,int B){
	return A>B?A:B;
}
inline void Swap(int &A,int &B){
	A^=B^=A^=B;
}
struct ee{
	int v;
	int nxt;
}e[N<<1];
int h[N],et=0;
inline void Eadd(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
inline void add(int U,int V){
	Eadd(U,V);Eadd(V,U);
}
int n,m;
int val[N],clr[N],dep[N],sz[N],sn[N],fa[N],dfn[N],cnt=0,tp[N];
inline void dfs0(int X){
	dep[X]=dep[fa[X]]+1;sz[X]=1;sn[X]=0;
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==fa[X]){continue;}
		fa[e[i].v]=X;
		dfs0(e[i].v);
		if(sz[e[i].v]>sz[sn[X]]){
			sn[X]=e[i].v;
		}
		sz[X]+=sz[e[i].v];
	}
}
inline void dfs1(int X){
	dfn[X]=++cnt;
	if(sn[X]){tp[sn[X]]=tp[X];dfs1(sn[X]);}
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v==sn[X]||e[i].v==fa[X]){continue;}
		tp[e[i].v]=e[i].v;dfs1(e[i].v);
	}
}
#define MID ((L+R)>>1)
struct Node{
	int l;int r;int sm;int mx;
}tr[4000005];
int rt[N];
int tcnt=0;
inline void chg(int &NW,int L,int R,int P,int V){
	if(!NW){NW=++tcnt;}
	if(L==R){tr[NW].sm=V,tr[NW].mx=V;return;}
	P<=MID?(chg(tr[NW].l,L,MID,P,V)):(chg(tr[NW].r,MID+1,R,P,V));
	tr[NW].sm=tr[tr[NW].l].sm+tr[tr[NW].r].sm;tr[NW].mx=Max(tr[tr[NW].l].mx,tr[tr[NW].r].mx);
}
inline int qryMx(int X,int A,int B,int L,int R){
	if(A>R||B<L||!X){return 0;}
	if(A<=L&&B>=R){return tr[X].mx;}//此处不应写成L==R 
	return Max((A<=MID?qryMx(tr[X].l,A,B,L,MID):0),(B>MID?qryMx(tr[X].r,A,B,MID+1,R):0));
}
inline int qrySm(int X,int A,int B,int L,int R){
	if(A>R||B<L||!X){return 0;}
	if(A<=L&&B>=R){return tr[X].sm;}
	return (A<=MID?qrySm(tr[X].l,A,B,L,MID):0)+(B>MID?qrySm(tr[X].r,A,B,MID+1,R):0);
}
inline void ADD(int X,int P,int V){
	chg(rt[X],1,n,P,V);
}
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		val[i]=rd(),clr[i]=rd();
	}
	int u,v;
	for(int i=1;i<n;++i){
		u=rd(),v=rd();
		add(u,v);
	}
	sz[0]=0;fa[1]=0;
	dfs0(1);
	tp[1]=1;
	dfs1(1);
	for(int i=1;i<=n;++i){
		ADD(clr[i],dfn[i],val[i]);
	}
	char ch[10];
	int x,y,c;
	for(int i=1;i<=m;++i){
		std::cin>>ch+1;
		switch(ch[2]){
			case 'C':{
				x=rd(),y=rd();
				ADD(clr[x],dfn[x],0);
				ADD(clr[x]=y,dfn[x],val[x]);
				break;
			}
			case 'W':{
				x=rd(),y=rd();
				ADD(clr[x],dfn[x],val[x]=y);
				break;
			}
			case 'S':{
				x=rd(),y=rd();
				int RT=0;c=clr[x];
				while(tp[x]!=tp[y]){
					if(dep[tp[x]]<dep[tp[y]]){Swap(x,y);}
					RT+=qrySm(rt[c],dfn[tp[x]],dfn[x],1,n);
					x=fa[tp[x]];
				}
				if(dep[x]<dep[y]){Swap(x,y);}
				RT+=qrySm(rt[c],dfn[y],dfn[x],1,n);
				printf("%d\n",RT);
				break;
			}
			case 'M':{
				x=rd(),y=rd();
				int RT=0;c=clr[x];
				while(tp[x]!=tp[y]){
					if(dep[tp[x]]<dep[tp[y]]){Swap(x,y);}
					RT=Max(RT,qryMx(rt[c],dfn[tp[x]],dfn[x],1,n));
					x=fa[tp[x]];
				}
				if(dep[x]<dep[y]){Swap(x,y);}
				RT=Max(RT,qryMx(rt[c],dfn[y],dfn[x],1,n));
				printf("%d\n",RT);
				break;
			}
		}
	}
}
int main(){
//	freopen("33132.in","r",stdin);
//	freopen("33132.ans","w",stdout);
	init();
	return 0;
}

lp3285 SCOI2014 方伯伯的OJ

题目要求维护一个编号序列和一个排名序列,并支持四种操作:
1.按照编号修改编号,并返回该编号的排名。
2.将一个节点的排名提升到第一个。
3.将一个节点的排名降低到最后一个。
4.查询某个排名的编号。
很显然是用Splay维护排名,然后开一个数组存编号咯。
然而我们观察到这一题的数据范围是n<=10^8,那么用上述的方法显然会MLE。
故而我们考虑一个Splay节点「真的维护」一个区间。然后每一次要用到一个新的点就把原有的区间剖开。
而数组存编号也就很套路地换成map存编号。
【冬天来了手都在发抖啊】
续:这一题是我在190103的时候写完的,然而直到191003我才调出来。期间经过了十个月。
调试的突破性进展来自于对调试工具的学习使用,这使得我在巨大数据的情况下得以想办法调试。
我首先发现了size发生了错误,进而发现某个节点的size不等于其两孩子的大小之和加上它本身的大小。然后,经由此处,我发现有个节点的相邻节点是一个大小为空的节点,进而发现这个节点在被分配下标之前就被访问了。
最终,我注意到它第一次出现所相接的节点,并发现这个数事实上是一个标号。
紧接着我就顺利地调出另一个错,并通过了此题。
注意点:
1.对于空节点的情况一定要认真考虑,因为如果空节点操作不慎的话很可能会导致一些莫名其妙的错误。
2.要注意适时更新节点。
3.千万不要搞混「标号」和「排名」!!!!!!
4.如果一个点本来就是排名最后的点而要移到排名最后,有可能会出错。

#include<iostream>
#include<cstdio>
#include<map>
#define error(X) printf("ERROR: %d",X)
#define debug(P) printf("(%d):%d,%d,sn:[%d,%d],FA:%d,SZ:%d\n",P,tr[P].l,tr[P].r,tr[P].sn[0],tr[P].sn[1],tr[P].fa,tr[P].sz);

bool bo=0;
class Splay{
	public:
		class Node{
			public:
				int l;
				int r;
				int sz;
				int sn[2];
				int fa;
				inline void set(int L,int R,int FA){
					l=L,r=R,fa=FA,sz=R-L+1,sn[0]=sn[1]=0;
				}
		};
		//i表示mp[i]这个节点的右端点的标号。 
		std::map<int,int> mp;
		Node tr[400005];
		int cnt,rt;
		//寻找当前节点与父亲的关系。 
		inline int fndD(int X){
			return tr[tr[X].fa].sn[1]==X;
		}
		//更新当前节点。 
		inline void updt(int X){
			tr[X].sz=tr[tr[X].sn[0]].sz+tr[tr[X].sn[1]].sz+tr[X].r-tr[X].l+1;
//			if(X==10619&&tr[X].sz<=30){prnt(tr[X].fa);}
		}
		//旋转套装。 
		inline void splayOne(int X){
			if(!X){return;}
			int D=fndD(X),D2=fndD(tr[X].fa);
//			if(X==65505||tr[X].fa==65505||tr[tr[X].fa].sn[D^1]==65505){
//				puts("FKFKFK");
//				printf("X");debug(X);
//				printf("FA");debug(tr[X].fa);
//				printf("BR");debug(tr[tr[X].fa].sn[D^1]);
//			}
			tr[tr[X].sn[D^1]].fa=tr[X].fa,tr[tr[X].fa].sn[D]=tr[X].sn[D^1];
			tr[X].sn[D^1]=tr[X].fa,tr[X].fa=tr[tr[X].sn[D^1]].fa;
			tr[tr[X].fa].sn[D2]=X,tr[tr[X].sn[D^1]].fa=X;
			updt(tr[X].sn[D^1]),updt(X);
		}
		inline void splayTwo(int X){
//			if(bo&&X==38190){debug(X);}
			int D=fndD(X),D2=fndD(tr[X].fa);
			tr[X].fa?(tr[tr[X].fa].fa?(D==D2?(splayOne(tr[X].fa),splayOne(X),0):(splayOne(X),splayOne(X),0)):(splayOne(X),0)):0;
		}
		inline void splayRnw(int X){
			while(tr[X].fa){splayTwo(X);}
			rt=X;
		}
//		inline void splayRnw(int X){
//			while(tr[X].fa){
//				int F=tr[X].fa,FF=tr[tr[X].fa].fa;
//				if(!FF)
//			}
//		}
		//找到排名为X的元素。 
		inline int fnd(int X){
			int P=rt;
			while(P){
				if(X>tr[tr[P].sn[0]].sz+tr[P].r-tr[P].l+1){
					X-=tr[tr[P].sn[0]].sz+tr[P].r-tr[P].l+1;
					P=tr[P].sn[1];
				}else if(X>tr[tr[P].sn[0]].sz){
					X-=tr[tr[P].sn[0]].sz;
					splayRnw(P);
//					debug(P);
					return tr[P].l+X-1;
				}else{
					P=tr[P].sn[0];
				}
			}
			return -1; 
		}
		//开一个新节点,以X为它的父亲。 
		inline int nwlc(int X,int L,int R){
			int P=++cnt;
//			if(P==65505){
//				printf("START:");
//				debug(P);
//			}
			tr[P].set(L,R,X);
			return P;
		}
		//将编号为X的节点单独弄成一个新的节点,然后将它的两个子节点接到它的左右,并更改相应的编号的映射 
		inline int split(int P,int X){
			if(tr[P].l==tr[P].r){return P;}
			if(P==-1){return error(192600404),192600404;}
			if(X>tr[P].l){
				int L=tr[P].sn[0];
				L?(cut(L),0):(tr[0].fa=0);
				tr[P].sn[0]=nwlc(P,tr[P].l,X-1);
				L?(cnnct(L,tr[P].sn[0],0),0):0;
				mp[X-1]=tr[P].sn[0];
//				updt(tr[P].sn[0]);
			}
			if(X<tr[P].r){
				int R=tr[P].sn[1];
				R?(cut(R),1):(tr[0].fa=0);
				tr[P].sn[1]=nwlc(P,X+1,tr[P].r);
				R?(cnnct(R,tr[P].sn[1],1),1):1;
				mp[tr[P].r]=tr[P].sn[1];
//				updt(tr[P].sn[1]);
			}
			tr[P].l=tr[P].r=X;mp[X]=P;
			updt(P);
			return P;
		}
		inline int fndMn(int X){
			int P=X,FP=tr[X].fa;
			while(P){
				FP=P;
				P=tr[P].sn[0]; 
			}
			return FP;
		}
		inline int fndMx(int X){
			int P=X,FP=tr[X].fa;
			while(P){
				FP=P;
				P=tr[P].sn[1];
			}
			return FP;
		}
		inline void cut(int X){
			int D=fndD(X);
			tr[tr[X].fa].sn[D]=0,tr[X].fa=0;
		}
		inline void cnnct(int X,int Y,int D){
			tr[Y].sn[D]=X,tr[X].fa=Y;
			updt(Y);
		}
		inline void prnt(int X,int dep=0){
			if(!X){return;}
			for(int i=1;i<=dep;++i){
				printf(" ");
			}debug(X);
			prnt(tr[X].sn[0],dep+1);
			prnt(tr[X].sn[1],dep+1);
		}
	public:
		inline int CHANGE(int X,int Y){
			int P=mp.lower_bound(X)->second;
			P=split(P,X);
			tr[P].l=tr[P].r=Y;
			mp[Y]=P;
			splayRnw(P);
			return tr[tr[P].sn[0]].sz+1;
		}
		inline int LST(int X){
			int P=mp.lower_bound(X)->second;
			P=split(P,X);
			splayRnw(P);
			int L=tr[P].sn[0],R=tr[P].sn[1],RT=tr[tr[P].sn[0]].sz+1;
			if(!L){
				return RT;
			}
			R?(R=fndMn(R),cut(L),cnnct(L,R,0),splayRnw(L)):(cut(L),cnnct(L,P,1));//此处P写成X,调了我一年。 
			return RT;
		}
		inline int RST(int X){
			int P=mp.lower_bound(X)->second;
			P=split(P,X);
			splayRnw(P);
			int L=tr[P].sn[0],R=tr[P].sn[1],RT=tr[tr[P].sn[0]].sz+1;
			if(!R){
				return RT;
			}
			L?(L=fndMx(L),cut(R),cnnct(R,L,1),splayRnw(R)):(cut(R),cnnct(R,P,0));
			return RT;
		}
		inline int ARNK(int X){
			return fnd(X);
		} 
		//初始化。 
		inline void INIT(int N){
			cnt=1;
			rt=1;
			tr[1].set(1,N,0);
			mp[N]=1;
		}
};
/*
Error:
192600404: 指定的节点不存在。
192600500: 切割的节点不是区间节点。 
*/

int n,m;
Splay T;
void init(){
	int code=0;
	scanf("%d%d",&n,&m);
	T.INIT(n);
	int op,x,y;
	for(int i=1;i<=m;++i){
		scanf("%d",&op);
		switch(op){
			case 1:{
				scanf("%d%d",&x,&y);
				x-=code,y-=code;
				printf("%d\n",code=T.CHANGE(x,y));
//				if(code==95204&&i>=80000){
//					puts("fk1");
//					printf("%d\n",x);
//					return;
//				}
				break;
			}
			case 2:{
				scanf("%d",&x);
				x-=code;
				printf("%d\n",code=T.LST(x));
				break;
			}
			case 3:{
				scanf("%d",&x);
				x-=code;
				printf("%d\n",code=T.RST(x));
				break;
			}
			case 4:{
				scanf("%d",&x);
				x-=code;
				printf("%d\n",code=T.ARNK(x));
				break;
			}
		}
//		printf("CORESIZE:%d\n",T.tr[54567].sz);
	}
}

int main(){
//	freopen("input1.in","r",stdin);
//	freopen("output1.out","w",stdout);
	init();
	return 0;
} 

lp3168 CQOI2015 任务查询系统

观察题面,我们发现这是一道变态题:区间加点,单点查询第k大,强制在线——这tm不是变态题么!别的不说,权值怎么离散化我都不会。
仔细一看,真的是这样么?
我们发现,先是m个修改,后面再跟着n个询问!这意味着什么?这意味着所谓的区间修改事实上是fake的,因为我们事实上只要对最后一个版本进行询问。
经验上,多次区间修改后求单点值,我们使用差分+前缀和来维护。在这里同样是生效的,只需把每一次修改拆成两次即可。
修改可以用一些妙妙方式储存,比如说Vector或者手写邻接表。
那就是主席树裸题了。

注意:每一次修改的时候修改的仅仅是L和R+1两个点,但是这并不是正确的!在把修改排序之后,每一个修改是从它的上一个点复制版本,但上一个版本可能并没有任何修改,这也就意味着,上一个版本可能是空的!这就完全不是前缀和了。
应当如何做呢?每一个点应当预先从前一个点复制。这样哪怕这个点没有被修改,也仍然能保持它的性质。
另外,离散化的时候不应该把点离散化在一起。在这里,把值相同的点离散化到不同的位置并不会影响答案。事实上,如果把值相同的点离散化到相同的位置,反而会更麻烦。这是因为如果离散化到相同的位置,那么这三个点在线段树上就存在同一个点里了。这时候,倘若这个点的大小为3,而你需要查询前2大的和,你就无法处理了。这平白增加了实现的复杂度。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector> 
using namespace std;

typedef long long ll; 
const int N=100005;
inline int Abs(int X){
	return X>0?X:-X;
}
#define MID ((L+R)>>1) 
vector<int> lst[N];
struct data{
	int l;int r;int val;
}a[N];
inline bool cmp(const data &A,const data &B){
	return A.val<B.val;
}
int loc[N],vl[N];
int n,m;
class CMT{
	private:
		class Node{
			public:
				int l;int r;int sz;ll sm;
		}tr[N*160];
		int cnt,rt[N];
		inline void bld(int LST,int &NW,int L,int R,ll V){
			NW=++cnt;tr[NW].sz=tr[LST].sz+(V>0?1:-1);tr[NW].sm=tr[LST].sm+(V>0?loc[V]:-loc[-V]);
			if(L==R){return;}
			Abs(V)<=MID?(bld(tr[LST].l,tr[NW].l,L,MID,V),tr[NW].r=tr[LST].r):(bld(tr[LST].r,tr[NW].r,MID+1,R,V),tr[NW].l=tr[LST].l);
		}
		inline ll qry(int X,int L,int R,ll V){
			ll RT=0;
			while(L<R){
//				printf("%lld %d %d %d %lld %d\n",RT,X,L,R,V,tr[X].sz);
				(tr[tr[X].l].sz<V)?(L=MID+1,V-=tr[tr[X].l].sz,RT+=tr[tr[X].l].sm,X=tr[X].r):(R=MID,X=tr[X].l);
			}
			RT+=tr[X].sm;
			return RT;
		}
		inline void prnt(int X){
			if(!X){
				return;
			}
			printf("%d|%lld ",tr[X].sz,tr[X].sm);
			prnt(tr[X].l);prnt(tr[X].r);
		}
	public:
		inline void ADD(int X,ll V){
			int nw;
			if(!rt[X]){
				bld(rt[X-1],rt[X],1,100000,V);
			}else{
				bld(rt[X],nw,1,100000,V);
				rt[X]=nw;
			}
		}
		inline ll QRY(int X,int V){
//			printf("qry:%d %d %d\n",X,V,tr[rt[X]].sz);
			return V>tr[rt[X]].sz?tr[rt[X]].sm:qry(rt[X],1,100000,V);
		}
		inline void RNW(int X){
			if(!rt[X]){
				rt[X]=rt[X-1];
			}
		}
		inline void PRNT(int X){
			prnt(rt[X]);
		}
		inline void prpr(){
			cnt=0;
			tr[0].sz=tr[0].sm=0;
			for(int i=1;i<=n;++i){
				rt[i]=0;
			}
		}
}TR;
void init(){
	TR.prpr();
	scanf("%d%d",&m,&n);
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].val);
	}
	std::sort(a+1,a+1+m,cmp);
	vl[0]=0,a[0].val=0;
	for(int i=1;i<=m;++i){
		vl[i]=vl[i-1]+1;
		loc[vl[i]]=a[i].val;
	}
	for(int i=1;i<=m;++i){
		lst[a[i].l].push_back(vl[i]);
		lst[a[i].r+1].push_back(-vl[i]);
	}
	for(int i=1;i<=n;++i){
		TR.RNW(i);
		for(int j=0;j<lst[i].size();++j){
			TR.ADD(i,lst[i][j]);
		}
	}
	int x,a,b,c,v;ll lans=1;
	for(int i=1;i<=n;++i){
		scanf("%d%d%d%d",&x,&a,&b,&c);
		v=(1ll*lans*a+b)%c+1;
		printf("%lld\n",lans=TR.QRY(x,v));
	}
}
int main(){
	init();
	return 0;
}

lp3302 SDOI2013 森林

我们发现,树上的链上第k大是可以使用主席树来维护的。对于每一个节点,我们从它的父亲复制一个版本,然后每一次求出LCA以后对链的两个端点、链的LCA、链的父亲分别查询。之后统计答案即可。
对于有连边操作的树,我们可能可以想到用LCT来维护。但是代码难度太高,而且事实上我也不知道要怎么写。所以我们可以考虑一种类似于按秩合并的操作,也就是说,每一次,我们把子树大小较小的子树合并到子树大小较大的子树。对于较小的那棵树,我们暴力更新其中的每一个节点。于是可以证明,每个节点的被更新次数最多不超过log次。
这样我们就有了一个\(O(nlog^2n)\)的做法。
注意:主席树的L,R本身就是节点位置;合并的时候要记得更新小树的根节点;返回的值是第k大的值而非第k大的排名因而要逆离散化。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
using namespace std;

const int N=80005;
struct data{
	int id;
	int val;
}a[N];
inline bool cmp(const data &A,const data &B){
	return A.val<B.val;
}
inline bool cmp2(const data &A,const data &B){
	return A.id<B.id;
}
struct ee{
	int v;
	int nxt;
}e[N<<1];
int h[N],et=0;
inline void Eadd(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
inline void add(int U,int V){
	Eadd(U,V),Eadd(V,U);
}
#define MID (L+R>>1)
class CMT{
	private:
		class Node{
			public:
				int l;int r;int sz;
		};
		Node tr[30000000];
		int cnt,rt[N];
		inline void bld(int LST,int &NW,int L,int R,int V){
			NW=++cnt;tr[NW].sz=tr[LST].sz+1;
			if(L==R){return;}
			V<=MID?(bld(tr[LST].l,tr[NW].l,L,MID,V),tr[NW].r=tr[LST].r):(bld(tr[LST].r,tr[NW].r,MID+1,R,V),tr[NW].l=tr[LST].l);
		}
		inline int qry(int A,int B,int C,int D,int L,int R,int V){
			while(L<R){
//				printf("nw:%d %d %d %d %d\n",A,B,C,D,V);
				(tr[tr[B].l].sz-tr[tr[A].l].sz+tr[tr[D].l].sz-tr[tr[C].l].sz<V)?
				(V-=tr[tr[B].l].sz-tr[tr[A].l].sz+tr[tr[D].l].sz-tr[tr[C].l].sz,L=MID+1,A=tr[A].r,B=tr[B].r,C=tr[C].r,D=tr[D].r):
				(R=MID,A=tr[A].l,B=tr[B].l,C=tr[C].l,D=tr[D].l);
			}
			return L;
		}
		inline void prnt(int X){
			if(!X){
				return;
			}
			prnt(tr[X].l);
			prnt(tr[X].r);
			printf("%d ",tr[X].sz);
		}
	public:
		inline void ADD(int LST,int VER,int V){
			bld(rt[LST],rt[VER],1,80000,V);
		}
		inline int QRY(int A,int B,int C,int D,int V){
			return qry(rt[A],rt[B],rt[C],rt[D],1,80000,V);
		}
		inline void prpr(){
			cnt=0;
		}
		inline void pt(int X){
			prnt(rt[X]);
		}
}TR;
int vis[N],fa[N][20],sz[N],dep[N],loc[N];
inline void dfs0(int X){
//	printf("\t\t\tdfs0(%d)%d\n",X,dep[X]);
	vis[X]=sz[X]=1;
	for(int i=h[X];i;i=e[i].nxt){
		if(vis[e[i].v]){
			continue;
		}
		fa[e[i].v][0]=X;
		dep[e[i].v]=dep[X]+1;
		for(int j=1;j<=18;++j){
			fa[e[i].v][j]=fa[fa[e[i].v][j-1]][j-1];
		}
		TR.ADD(X,e[i].v,a[e[i].v].val);
		dfs0(e[i].v);
		sz[X]+=sz[e[i].v];
	}
}
inline void dfs1(int X){
	vis[X]=0;
	for(int i=h[X];i;i=e[i].nxt){
		if(!vis[e[i].v]){
			continue;
		}
		dfs1(e[i].v);
	}
}
inline int szq(int X){
	for(int i=18;i>=0;--i){
		if(fa[X][i]!=0){
			X=fa[X][i];
		}
	}
	return sz[X];
}
inline void uni(int X,int Y){
	int SZ=szq(X);
	dfs1(X);
	add(X,Y);
	fa[X][0]=Y;
	dep[X]=dep[Y]+1;
	TR.ADD(Y,X,a[X].val);
	for(int i=1;i<=18;++i){
		fa[X][i]=fa[fa[X][i-1]][i-1];
	}
	int RT=X;
	for(int i=18;i>=0;--i){
		if(fa[RT][i]){
			RT=fa[RT][i];
		}
	}
	sz[RT]+=SZ;
	dfs0(X);
}
inline int lca(int X,int Y){
	if(dep[X]<dep[Y]){
		X^=Y^=X^=Y;
	}
	for(int i=18;i>=0;--i){
		if(dep[fa[X][i]]>=dep[Y]){
			X=fa[X][i];
		}
	}
	if(X==Y){
		return X;
	}
	for(int i=18;i>=0;--i){
		if(fa[X][i]!=fa[Y][i]){
			X=fa[X][i],Y=fa[Y][i];
		}
	}
	return fa[X][0];
}
int n,m,q,tid;
void init(){
	scanf("%d",&tid);
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i].val);
		a[i].id=i;
	}
	std::sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;++i){
		loc[i]=a[i].val;
	}
	for(int i=1;i<=n;++i){
		if(a[i].val!=a[i-1].val){
			a[i].val=a[i-1].val+1;
		}else{
			a[i].val=a[i-1].val;
		}
	}
	std::sort(a+1,a+1+n,cmp2); 
	int u,v;
	for(int i=1;i<=m;++i){
		scanf("%d%d",&u,&v);
		add(u,v);
	}
	TR.prpr();
	for(int i=1;i<=n;++i){
		if(!vis[i]){
			dep[i]=1;
			TR.ADD(0,i,a[i].val);
			dfs0(i);
		}
	}
//	for(int i=1;i<n;++i){
//		printf("%d:",i);
//		TR.pt(i);
//		puts("");
//	}
	int lans=0,x,lc;
	char ch[10];
	for(int i=1;i<=q;++i){
		cin>>ch+1;
		switch(ch[1]){
			case 'Q':{
				scanf("%d%d%d",&u,&v,&x);
				u^=lans,v^=lans,x^=lans;
				lc=lca(u,v);
//				printf("\t\t\t%d %d %d\n",u,v,x);
				printf("%d\n",lans=loc[TR.QRY(fa[lc][0],u,lc,v,x)]);
				break; 
			}
			case 'L':{
				scanf("%d%d",&u,&v);
				u^=lans,v^=lans;
//				printf("\t\t\t%d %d\n",u,v);
				if(szq(u)>szq(v)){
					u^=v^=u^=v;
				}
				uni(u,v);
				break;
			}
		}
	}
}
int main(){
	init();
	return 0;
}

lp2501 HAOI2006 数字序列

我们分别考虑一二问。
对于第一问,我们思考一个子序列是合法的「不用修改」的子序列的充要条件。
容易想到的,这个条件是:
$$ \forall i,j\in S, i=j-i$$
自然语言化地说,就是,对于这个不用修改的子序列中的任意两个元素,它们的值的差距至少要大于它们间的元素个数,这样才能放得下它们中间的元素。
移项,我们得到:
$$a_j-j>=a_i-i$$
所以,我们令\(b_i=a_i-i\),那么第一问中不用修改的个数就是\(b\)的最长不下降子序列长度。
对于第二问,首先,它可以被转化为「最小修改代价求\(b\)单调不减」。
我们有一个结论:相邻两关键点\(i,j\)间一定可以找到一条分界线,使得线左端的所有点变化成\(b_i\),右端所有点变化成\(b_j\)会最优。
这是如何证明的呢?
首先,我们知道,\(i,j\)之间的任意一个点,它的值必然要小于\(b_i\)或者大于\(b_j\),否则选取这个点只会让答案更优。
然后,我们尝试进行反证。如果有一个点修改以后位于中间,并且它可以被修改到某一边,那么显然修改到某一边之后答案会更小。
如果将分界线定在某处,会使得某些点与它们的最优处于的边不相同,那么考虑这些点与分界点之间的其他点的数量。
如果其他点的数量小于这些点,那么不妨把这些点修改后的位置换到另一边,这样答案就变小了点数差*上下两边距离。
否则,不如不修改。
所以我们证明了这个结论。
然后是关于时间复杂度的。可以证明,在序列随机的情况下,最长不下降子序列的期望长度是logn级别的。(我不会证,也找不到文章。求大佬教教我)

注意:要提前把\(b_0\)设成\(-INF\),并在末尾插入一个\(INF\)的点。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

typedef long long ll;
const int N=35005;
const int INF=0x3f3f3f3f;
inline ll Abs(ll X){
	return X>=0?X:-X;
}
inline ll Min(ll A,ll B){
	return A<B?A:B;
}
int n,a[N],b[N],nm[N];
ll f[N],sm1[N],sm2[N];
struct ee{
	int v;
	int nxt;
}e[N];
int h[N],et=0;
inline void add(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		b[i]=a[i]-i;
	}
	int cnt=0,nw;
	b[0]=-INF;f[0]=-INF;
	b[++n]=INF;
	for(int i=1;i<=n;++i){
		if(b[i]>=f[cnt]){
			f[++cnt]=b[i];
			nm[i]=cnt;
		}else{
			nw=upper_bound(f+1,f+cnt,b[i])-f;
			f[nw]=b[i];
			nm[i]=nw;
		}
	}
	printf("%d\n",n-cnt);
	for(int i=n;i>=0;--i){
		add(nm[i],i);
		f[i]=INF;
	}
	f[0]=0;
	int v;
	for(int i=1;i<=n;++i){
		for(int j=h[nm[i]-1];j;j=e[j].nxt){
			v=e[j].v;
			if(v>i||b[v]>b[i]){
				continue;
			}
			sm1[v]=0;
			for(int k=v+1;k<=i;++k){
				sm1[k]=sm1[k-1]+Abs(b[k]-b[v]);
			}
			sm2[i-1]=0;
			for(int k=i-2;k>=v;--k){
				sm2[k]=sm2[k+1]+Abs(b[k+1]-b[i]);
			}
			for(int k=v;k<i;++k){
				f[i]=Min(f[i],f[v]+sm1[k]+sm2[k]);
			}
		}
	}
	printf("%lld\n",f[n]);
}
int main(){
	init();
	return 0;
}

lp3233 HNOI2014 世界树

让我们来分析这道题。
我们很容易地可以发现,如果一个节点是末端节点,那么它肯定是由它祖先中的第一个节点管辖更优。
由此我们继续推导,可以发现,假如只有两个关键点的话,它们之间的链上一定可以找到一个分界线,使得这条分界线的一段——以及所有与链上这一端相邻的节点——放在一个关键点上,并把剩下的放在另一个关键点上。这样是最优的。
然后我们考虑有三个关键点的情况。如果有三个关键点的话,问题似乎就复杂了很多,这是因为这条分界线必须是基于三个节点共同决定的。
我们换一个思路考虑。求出三个关键点两两的LCA。那么,这一分界线就必然可以在这六个点(最多六个)两两之间的链上找到。
存在一种叫做「虚树」的数据结构。这个数据结构本质上就是将所有关键点以及关键点两两之间的LCA建成一个数。
我们如此考虑,如果有一个点是关键点,那么它向下能够管辖的点的数量就是它的子树大小减去它的所有子节点能管辖的点数之和。
它向上能够管辖的点的数量则相对比较复杂。
我们考虑每一条边,假设我们已经预处理出了虚树上每一个点相邻最近的关键点,那么,如果这条边两端的点相邻最近的关键点是相同的,那么这条边(以及和这条边相邻的所有点)都划归到那个关键点下管辖。
如果这条边两段的点相邻最近的关键点不同,则需要使用倍增来确定这条边要如何被划分成两个部分。

接下来要考虑如何确定虚树上每一个点相邻最近的关键点。
我们不妨这样考虑:一个点相邻最近的关键点如果在它的下方,那么这可以通过树形DP求得;如果在它的上方或者其他子树内呢?
显然,如果这个点的相邻最近关键点在它的上方或者和它不在同一子树内,那么它的父亲的最近关键点一定与这个点的最近关键点相同。
于是,我们不妨从上而下DP,求得这个点在上方或者不在同一子树的最近关键点。

现在我们来梳理一下这一题的思路。
首先,我们进行预处理,处理出每个点的深度和dfn。
然后,我们进行两次树形DP,求出每个点的最近关键点。
第三,我们预处理出所有「末端节点」——也就是所有「是一个虚树上节点的直接儿子且子树内没有关键点的原树上的点」。这些点的贡献可以直接统计到它们父亲的最近关键点。
最后,我们依次考虑剩下的虚树边上的点。如果两段的最近关键点相同,那么就统计到那个最近关键点。否则就进行倍增寻找答案。

顺便讲一下如何建虚树。
我们将所有关键点按照dfs序排序,然后建一个栈,代表当前正在向下延长的链。
如果当前的点与栈顶的LCA的深度小等于次栈顶,那么就说明当前点不在栈顶的子树里,也就意味着栈顶处于当前应该维护的链外。
于是,我们需要就可以将新的这个点加入虚树和栈中。
否则,就说明原来的栈顶需要被弹出,那么就处理完它应该连的边然后将它弹出。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#define Fv(i,X) for(int i=h[X];i;i=e[i].nxt)
#define Fv2(i,X) for(int i=g[X];i;i=e[i].nxt)
using namespace std;

typedef pair<int,int> pii;
const int N=300005;
const int INF=0x3f3f3f3f;
struct ee{
	int v;
	int nxt;
}e[1200005];
int h[N],g[N],et=0;
inline void add(int *H,int U,int V){
	e[++et]=(ee){V,H[U]};
	H[U]=et;
}

int dfn[N],cnt=0,sz[N],dep[N],fa[N][20];
inline void dfs0(int X){
	dfn[X]=++cnt;sz[X]=1;
	Fv(i,X){
		if(e[i].v==fa[X][0]){
			continue;
		}
		fa[e[i].v][0]=X;dep[e[i].v]=dep[X]+1;
		dfs0(e[i].v);
		sz[X]+=sz[e[i].v];
	}
}
int usd[N],pt[N],ppt[N],hr[N],ans[N],up[N];
pii nr[N];
inline void dfs1(int X){
	nr[X]=(usd[X]?pii(0,X):pii(INF,0));
	Fv2(i,X){
		dfs1(e[i].v);
		nr[X]=min(nr[X],pii(nr[e[i].v].first+dep[e[i].v]-dep[X],nr[e[i].v].second));
	}
}
inline void dfs2(int X,int D,int P){
	if(pii(D,P)<nr[X]){
		nr[X]=pii(D,P);
	}else{
		D=nr[X].first,P=nr[X].second;	
	}
	Fv2(i,X){
		dfs2(e[i].v,D+dep[e[i].v]-dep[X],P);
	}
}
//子节点中所有子树中有虚树上节点的点都是不可以选取的。
//我们不妨逆向考虑,枚举每一个虚树上的子节点,然后从那个节点开始倍增,一直倍增到这棵树的子节点,然后把这些子节点的子树挖掉。 
inline void dfs3(int X){
	ans[hr[X]=nr[X].second]+=sz[X];
	Fv2(i,X){
		int nw=e[i].v;
		for(int j=18;j>=0;--j){
			if(fa[nw][j]&&dep[fa[nw][j]]>dep[X]){
				nw=fa[nw][j];
			}
		}
		ans[hr[X]]-=sz[up[e[i].v]=nw];
		dfs3(e[i].v);
	}
}
//现在剩下的末端节点就只有虚树上的节点了。 
//如果子节点的dfs序大于当前节点,那么分割点就偏上;否则偏下。 
inline void dfs4(int X){
	Fv2(i,X){
		if(hr[e[i].v]==hr[X]){
			ans[hr[X]]+=sz[up[e[i].v]]-sz[e[i].v];
		}else{
			int len=dep[hr[e[i].v]]+dep[X]-nr[X].first;
			len=((len&1)?(len+1)>>1:((len>>1)+(int)(hr[e[i].v]>hr[X])));
//			这里比较的是编号!!! 
			int nw=e[i].v;
			for(int j=18;j>=0;--j){
				if(dep[fa[nw][j]]>=len){
					nw=fa[nw][j];
				}
			}
			ans[hr[e[i].v]]+=sz[nw]-sz[e[i].v];
			ans[hr[X]]+=sz[up[e[i].v]]-sz[nw];
		}
		dfs4(e[i].v);
	}
}
inline void dfs5(int X){
	up[X]=hr[X]=0;
	Fv2(i,X){
		dfs5(e[i].v);
	}
	g[X]=0;
}
inline bool cmp(int A,int B){
	return dfn[A]<dfn[B];
}
inline int lca(int X,int Y){
	if(dep[X]<dep[Y]){
		swap(X,Y);
	}
	for(int i=18;i>=0;--i){
		if(dep[fa[X][i]]>=dep[Y]){
			X=fa[X][i];
		}
	}
	if(X==Y){
		return X;
	}
	for(int i=18;i>=0;--i){
		if(fa[X][i]!=fa[Y][i]){
			X=fa[X][i],Y=fa[Y][i];
		}
	}
	return fa[X][0];
}
int st[N],tp=0;
void init(){
	int n,Q;
	scanf("%d",&n);
	int u,v;
	for(int i=1;i<n;++i){
		scanf("%d%d",&u,&v);
		add(h,u,v);
		add(h,v,u);
	}
	dep[1]=1;
	dfs0(1);
	for(int j=1;j<=18;++j){
		for(int i=1;i<=n;++i){
			fa[i][j]=fa[fa[i][j-1]][j-1];
		}
	}
	scanf("%d",&Q);
	int m,X,Y;
	while(Q--){
		scanf("%d",&m);
		for(int i=1;i<=m;++i){
			scanf("%d",&pt[i]);
			ppt[i]=pt[i],usd[pt[i]]=1;
		}
		sort(pt+1,pt+1+m,cmp);
		st[tp=1]=pt[1];
		for(int i=2;i<=m;++i){
			X=pt[i],Y=lca(X,st[tp]);
			while(tp>1&&dep[Y]<=dep[st[tp-1]]){
				add(g,st[tp-1],st[tp]);
				--tp;
			}
			if(Y!=st[tp]){
				add(g,Y,st[tp]);st[tp]=Y;
			}
			st[++tp]=X;
		}
		while(tp>1){
			add(g,st[tp-1],st[tp]);
			--tp;
		}
		dfs1(st[1]);
		dfs2(st[1],nr[st[1]].first,nr[st[1]].second);
		dfs3(st[1]);
		dfs4(st[1]);
		ans[hr[st[1]]]+=sz[1]-sz[st[1]];
		for(int i=1;i<=m;++i){
			printf("%d ",ans[ppt[i]]);
		}
		puts("");
		dfs5(st[1]);
		for(int i=1;i<=m;++i){
			ans[pt[i]]=0,usd[pt[i]]=0;
		}
	}
}
int main(){
	init();
	return 0;
}

lp2519 HAOI2011 problem a

我们为每个考生设置一个可能的区间。这个区间的左端点是l=a+1,右端点是r=n-b。
仔细观察,会发现,这个可能的区间,就是和这个考生同分(包括这个考生)的考生的数量。
那么显然,如果这个可能的区间不存在,那么这个考生在撒谎;如果在同一个区间里面有超过区间长度的考生数,那么也是不合法的。
我们仔细想想,还有什么情况是冲突的。我们发现,说真话的考生所在的区间是不能重合的。
于是问题就转化为一个类似于背包的问题。我们可以将这些区间排序,那么不妨设f[i]表示第i个区间为真的情况下的最大数量。
首先,如果右端点递减,我们可以考虑用一个单调队列来维护这个东西。
在这种情况下,可以维护一个r值递增,f值递增的单调队列。
每一次把新的右端点插入到单调队列的右端,然后如果右端的f值比当前的f值小,那么就把右端的f值给干掉。
然而,实际上,右端点是无单调性的,所以可能存在这样一种情况:新插入的点的r值更小,而f值也更小。这时候就没有办法判断是否要删掉单调队列末端的点了。
想象一下在这种情况下要怎么做。在这种情况下,我们可以将新插入的点插到r值刚好比它小的那个点前面,然后把所有r值比它大而f值比它小的点都删掉。
要如何维护呢?直观地想是使用平衡树,但是我们可以使用map来完成这个操作。
然而,这样涉及到复杂的iterator操作。我并不是很会。
我们考虑另外一种想法。我们令f[i]表示以i为当前访问过的最右端点的情况下的最优值。
那么,我们可以记录每一个右端点的所有左端点,然后枚举这些左端点并转移,就可以得出答案。
注意:一个区间的权值要与它的长度取min!
注意:这样求出来的答案是真的数量,要用n减去它!

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
using namespace std;

inline int Max(int A,int B){
	return A>B?A:B;
}
inline int Min(int A,int B){
	return A<B?A:B;
}
typedef pair<int,int> pii;
const int N=100005;
int n;
int f[N];
vector<int> lst[N];
map<pii,int> mp;
void init(){
	scanf("%d",&n);
	int x,y,l,r;
	for(int i=1;i<=n;++i){
		scanf("%d%d",&x,&y);
		l=x+1,r=n-y;
		if(l>r){
			continue;
		}
		if(++mp[(pii){l,r}]==1){
			lst[r].push_back(l);
		}
	}
	for(int i=1;i<=n;++i){
		f[i]=f[i-1];
		for(int j=0;j<lst[i].size();++j){
			f[i]=Max(f[i],f[lst[i][j]-1]+Min(i-lst[i][j]+1,mp[(pii){lst[i][j],i}]));
		}
	}
	printf("%d\n",n-f[n]);
}
int main(){
	init();
	return 0;
}

lp2486 SDOI2011 染色

考虑这一题在链上的情况。
显然,可以建一棵线段树,修改是打标记下传,查询是左右相加特判左右相邻处颜色是否相同。
看起来在树上也可以这么做。但是仔细想想会发现不太对。
这是因为,根据树链剖分的原理,每两条剖开的链是独立查询的。
因此,在树上查询的时候,需要额外查询两个相接的链的接驳处的颜色是否相同。
这大概就做完了。

然后我们发现实时查询接驳处的颜色不仅很傻,而且容易错。
所以我们考虑开两个数组:lc和rc,储存一个区间内左端颜色和右端颜色。

另外就是链上接驳处的颜色问题。一种容易想到的方法是每一次记录它来的那个点,然后比较来的那个点和自身。
然而这么做同样是不仅傻而且容易错的。于是我们考虑另一种方法:每一次比较链顶和链顶的父亲这两个点,并将它的负贡献预先扣除。这样可以有效简化代码。

#include<iostream>
#include<cstdio>
#define Fv(i,X) for(int i=h[X];i;i=e[i].nxt)

inline void Swap(int &A,int &B){
    A^=B^=A^=B;
}
int n,m;
const int N=100005;
struct ee{
    int v;
    int nxt;
}e[N<<1];
int h[N],et=0;
inline void Eadd(int U,int V){
    e[++et]=(ee){V,h[U]};
    h[U]=et;
} 
inline void add(int U,int V){
    Eadd(U,V);
    Eadd(V,U);
}
int sn[N],sz[N],fa[N],dep[N];
inline void dfs0(int X,int FA){
    fa[X]=FA;sz[X]=1;dep[X]=dep[FA]+1;sn[X]=0;
    Fv(i,X){
        if(e[i].v==FA){
            continue;
        }
        dfs0(e[i].v,X);
        if(sz[e[i].v]>sz[sn[X]]){
            sn[X]=e[i].v;
        }
        sz[X]+=sz[e[i].v];
    }
}
int dfn[N],tp[N],cnt=0;
inline void dfs1(int X,int FA,int TP){
    dfn[X]=++cnt;tp[X]=TP;
    if(sn[X]){
        dfs1(sn[X],X,TP);
    }
    Fv(i,X){
        if(e[i].v==FA||e[i].v==sn[X]){
            continue;
        }
        dfs1(e[i].v,X,e[i].v);
    }
}
int clr[N];
#define MID ((L+R)>>1)
#define LS (X<<1)
#define RS (X<<1|1)
int tr[N<<2],tg[N<<2],val[N<<2],lc[N<<2],rc[N<<2];
inline void mdf(int X,int C){
    tr[X]=tg[X]=lc[X]=rc[X]=C;
    val[X]=1;
}
inline void pshd(int X,int L,int R){
	if(L==R){
		return;
	}
    if(tg[X]){
        mdf(LS,tg[X]),mdf(RS,tg[X]);
        tg[X]=0;
    }
}
inline int qryc(int X,int L,int R,int P){
    if(L==R){
        return tr[X];
    }
    pshd(X,L,R);
    return P<=MID?qryc(LS,L,MID,P):qryc(RS,MID+1,R,P);
}
inline void updt(int X,int L,int R){
    val[X]=(val[LS]+val[RS]-(rc[LS]==lc[RS]));
    lc[X]=lc[LS],rc[X]=rc[RS];
}
inline void chg(int X,int L,int R,int A,int B,int C){
    if(A<=L&&R<=B){
        mdf(X,C);
        return;
    }
    if(L>B||R<A){
        return;
    }
    pshd(X,L,R);
    chg(LS,L,MID,A,B,C);chg(RS,MID+1,R,A,B,C);
    updt(X,L,R);
}
inline int qryv(int X,int L,int R,int A,int B){
    if(A<=L&&R<=B){
        return val[X];
    }
    if(L>B||R<A){
        return 0;
    }
    pshd(X,L,R);
    return qryv(LS,L,MID,A,B)+qryv(RS,MID+1,R,A,B)-((A<=MID&&B>MID)?(rc[LS]==lc[RS]):0);
}
void init(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&clr[i]);
    }
    int u,v;
    for(int i=1;i<n;++i){
        scanf("%d%d",&u,&v);
        add(u,v);
    }
    sz[0]=0,dep[0]=0;
    dfs0(1,0);
    dfs1(1,0,1);
    for(int i=1;i<=n;++i){
        chg(1,1,n,dfn[i],dfn[i],clr[i]);
    }
    char ch[4];
    int c,ans;
    for(int i=1;i<=m;++i){
        std::cin>>ch+1;
        switch(ch[1]){
            case 'Q':{
                scanf("%d%d",&u,&v);
                ans=0;
                while(tp[u]!=tp[v]){
                    if(dep[tp[u]]<dep[tp[v]]){
                        Swap(u,v);
                    }
                    ans+=qryv(1,1,n,dfn[tp[u]],dfn[u]);
                    ans-=(qryc(1,1,n,dfn[tp[u]])==qryc(1,1,n,dfn[fa[tp[u]]]));
                    u=fa[tp[u]];
                }
                if(dep[u]<dep[v]){
                    Swap(u,v);
                }
                ans+=qryv(1,1,n,dfn[v],dfn[u]);
                printf("%d\n",ans);
                break;
            }
            case 'C':{
                scanf("%d%d%d",&u,&v,&c);
                while(tp[u]!=tp[v]){
                    if(dep[tp[u]]<dep[tp[v]]){
                        Swap(u,v);
                    }
                    chg(1,1,n,dfn[tp[u]],dfn[u],c);
                    u=fa[tp[u]];
                }
                if(dep[u]<dep[v]){
                    Swap(u,v);
                }
                chg(1,1,n,dfn[v],dfn[u],c);
                break;
            }
        }
    }
}

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

lp5290 十二省联考2019 春节十二响

首先我们考虑一种n^2logn的做法:将所有的子程序根据内存消耗来排序,然后每一次选中内存消耗最大且尚未被选中的,将所有内存比它小并且可以被同时选中的选中,然后统计贡献。
于是问题转化为如何用logn的复杂度查询祖先-后代关系。
我们考虑将整棵树展开为DFS序列,那么可以用树状数组维护祖先-后代关系。

如何优化这个做法呢?
我们注意到存在一种链的部分分。这种情况是容易解决的:搞两个堆,先把两条子链各自加到堆里,然后每次将它们的堆顶各自提出来,然后取较大值加入最终答案。
这启发我们用类似的方法处理一般的树状情况。
对于任意一个节点,我们建一个堆代表这个节点的子树的数值情况,每一次使用类似链的方法合并。
然而,这样并不能从本质上提升时间复杂度,它仍然需要n^2logn的时间复杂度,只不过不满。
考虑到这是树上的合并问题,因此尝试使用启发式合并,每次只合并两个节点,并将大小较小的那个节点的堆里的东西塞到大小较大的那个节点的堆里。
均摊而言,每个点的位置只会被转移一次——这是因为每一次有且仅有较小的那个堆会被合并,而较大的那个堆不会动。于是,如果一个点被转移了两次,那么一定意味着一个或者更多的节点在这一层的合并中没有被转移。所以均摊共转移不到n次。
对于每一次节点的位置转移,复杂度是logn,因此总复杂度是\(O(n*logn)\)

#include<iostream>
#include<cstdio>
#include<queue>

typedef long long ll;
const int N=200005;
inline void Swap(int &A,int &B){
	A^=B^=A^=B;
}
inline int Max(int A,int B){
	return A>B?A:B;
}
struct ee{
	int v;
	int nxt;
}e[N<<1];
int h[N],et=0;
inline void add(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
int fa[N],n;
ll ans=0;
int val[N],id[N],st[N],tp=0;
std::priority_queue<int> q[N];
inline void uni(int X,int Y){
	if(q[id[X]].size()<q[id[Y]].size()){
		Swap(id[X],id[Y]);
	}
	while(!q[id[Y]].empty()){
		st[++tp]=Max(q[id[X]].top(),q[id[Y]].top());
		q[id[X]].pop(),q[id[Y]].pop();
	}
	while(tp){
		q[id[X]].push(st[tp--]);
	} 
}
inline void dfs(int X){
	for(int i=h[X];i;i=e[i].nxt){
		dfs(e[i].v);
		uni(X,e[i].v);
	}
	q[id[X]].push(val[X]);
}
void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&val[i]);
		id[i]=i;
	}
	for(int i=2;i<=n;++i){
		scanf("%d",&fa[i]);
		add(fa[i],i);
	}
	dfs(1);
	while(!q[id[1]].empty()){
		ans+=q[id[1]].top();
		q[id[1]].pop();
	}
	printf("%lld\n",ans);
}

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

lp2590 ZJOI2008 树的统计

树剖套线段树裸题。

#include<iostream>
#include<cstdio>
#define Fv(i,X) for(int i=h[X];i;i=e[i].nxt)
using namespace std;
inline int Max(int A,int B){
	return A>B?A:B;
}
inline void Swap(int &A,int &B){
	A^=B^=A^=B;
}
const int N=30005;
const int INF=2147483647;
struct ee{
	int v;
	int nxt;
}e[N<<1];
int h[N],et=0;
inline void add(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
int dep[N],fa[N],sz[N],sn[N],tp[N],dfn[N];
int val[N],n;
inline void dfs0(int X,int FA){
	sz[X]=1,sn[X]=0;
	fa[X]=FA;dep[X]=dep[FA]+1;
	Fv(i,X){
		if(e[i].v==FA){
			continue;
		}
		dfs0(e[i].v,X);
		sz[X]+=sz[e[i].v];
		if(sz[e[i].v]>sz[sn[X]]){
			sn[X]=e[i].v;
		}
	}
}
int cnt=0;
inline void dfs1(int X,int FA,int TP){
	tp[X]=TP;
	dfn[X]=++cnt;
	if(sn[X]){
		dfs1(sn[X],X,TP);
	}
	Fv(i,X){
		if(e[i].v==FA||e[i].v==sn[X]){
			continue;
		}
		dfs1(e[i].v,X,e[i].v);
	}
}

#define MID ((L+R)>>1)
#define LS (X<<1)
#define RS (X<<1|1)
int tr[240005],mx[240005];
inline void updt(int X){
	tr[X]=tr[LS]+tr[RS];
	mx[X]=Max(mx[LS],mx[RS]);
}
inline void chg(int X,int L,int R,int P,int V){
	if(L==R){
		tr[X]=mx[X]=V;
		return;
	}
	P<=MID?chg(LS,L,MID,P,V):chg(RS,MID+1,R,P,V);
	updt(X);
	return;
}
inline int qrySm(int X,int L,int R,int A,int B){
	if(L>=A&&R<=B){
		return tr[X];
	}
	if(R<A||L>B){
		return 0;
	}
	return qrySm(LS,L,MID,A,B)+qrySm(RS,MID+1,R,A,B);
}
inline int qryMx(int X,int L,int R,int A,int B){
	if(L>=A&&R<=B){
		return mx[X];
	}
	if(R<A||L>B){
		return -INF;
	}
	return Max(qryMx(LS,L,MID,A,B),qryMx(RS,MID+1,R,A,B));
}

void init(){
	scanf("%d",&n);
	int u,v;
	for(int i=1;i<n;++i){
		scanf("%d%d",&u,&v);
		add(u,v),add(v,u);
	}
	sz[0]=0;
	dfs0(1,0);
	dfs1(1,0,1);
	for(int i=1;i<=n;++i){
		scanf("%d",&val[i]);
		chg(1,1,n,dfn[i],val[i]);
	}
	char ch[6];
	int q,ans;
	scanf("%d",&q);
	for(int i=1;i<=q;++i){
		std::cin>>ch+1;
		scanf("%d%d",&u,&v);
		switch(ch[2]){
			case 'H':{
				val[u]=v;
				chg(1,1,n,dfn[u],v);
				break;
			}
			case 'S':{
				ans=0;
				while(tp[u]!=tp[v]){
					if(dep[tp[u]]<dep[tp[v]]){
						Swap(u,v);
					}
					ans+=qrySm(1,1,n,dfn[tp[u]],dfn[u]);
					u=fa[tp[u]];
				}
				if(dep[u]>dep[v]){
					Swap(u,v);
				}
				ans+=qrySm(1,1,n,dfn[u],dfn[v]);
				printf("%d\n",ans);
				break;
			}
			case 'M':{
				ans=-INF;
				while(tp[u]!=tp[v]){
					if(dep[tp[u]]<dep[tp[v]]){
						Swap(u,v);
					}
					ans=Max(ans,qryMx(1,1,n,dfn[tp[u]],dfn[u]));
					u=fa[tp[u]];
				}
				if(dep[u]>dep[v]){
					Swap(u,v);
				}
				ans=Max(ans,qryMx(1,1,n,dfn[u],dfn[v]));
				printf("%d\n",ans);
				break;
			}
		}
	}
} 

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

lp4582 FJOI2014 树的重心

两个重心的情况想想都麻。我们首先考虑一个重心的情况。 我们把 假设我们现在已经求出了每个子树的大小,那么我们发现,一棵子树有且仅有它的大小是对答案有影响的。所以我们可以预处理出每棵子树的不同大小的联通结构数,然后枚举子树大小瞎统计一下。 那么想想要怎么预处理。我们令\(f_{i,j}\)表示以\(i\)为根节点的子树中选取\(j\)个节点的联通子树的个数,\(g_{i,j}\)表示当前子树前\(i\)个儿子选取\(j\)个的联通子树的个数。 那么,根据定义我们有: $$g_{nw,j}=\sum_{k=1}^{j}g_{nw-1,k}f_{v,j-k}$$ $$f_{X,i}=g_{sum\_of\_sons,i-1}$$ 然后树形DP即可。 仔细想想,如果有两个重心,那么把两个重心的连边断开,两边的答案的统计是互不干扰的。 故而我们可以将原树分成两棵树统计答案,再把答案相乘。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define Fv(A,X) for(int A=h[X];A;A=e[A].nxt)

const int MOD=10007;
const int INF=0x3f3f3f3f;
inline int Max(int A,int B){
	return A>B?A:B;
}
inline int Min(int A,int B){
	return A<B?A:B;
}
struct ee{
	int v;
	int nxt;
}e[404];
int h[205],et=0;
inline void Eadd(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
inline void add(int U,int V){
	Eadd(U,V);
	Eadd(V,U);
}
int sz[205],mx[205],rt=0,rt2=0,totsz,Tid=0,n;
inline void dfs0(int X,int FA){
	sz[X]=1;mx[X]=0;
	Fv(i,X){
		if(e[i].v==FA){
			continue;
		}
		dfs0(e[i].v,X);
		sz[X]+=sz[e[i].v];
		mx[X]=Max(mx[X],sz[e[i].v]);
	}
	mx[X]=Max(mx[X],totsz-sz[X]);
	if(mx[X]<mx[rt]){
		rt=X;
		rt2=0;
	}else if(mx[X]==mx[rt]){
		rt2=X;
	}
}
int f[205][205],g[205][205];
inline void dfs1(int X,int FA){
	Fv(i,X){
		if(e[i].v==FA){
			continue;
		}
		dfs1(e[i].v,X);
	}
	for(int i=0;i<=n;++i){
		for(int j=0;j<=n;++j){
			g[i][j]=0;
		}
	}
	f[X][1]=f[X][0]=g[0][0]=sz[X]=1;
	int nw=1;
	Fv(i,X){
		if(e[i].v==FA){
			continue;
		}
		sz[X]+=sz[e[i].v];
		for(int j=0;j<=sz[X];++j){
			for(int k=0;k<=j;++k){
				g[nw][j]=(g[nw][j]+g[nw-1][j-k]*f[e[i].v][k]%MOD)%MOD;
			}
		}
		++nw;
	}
	--nw;
	for(int i=1;i<=sz[X];++i){
		f[X][i]=g[nw][i-1];
	}
}
int ans=0;
inline void calc1(){
	ans=1;
	for(int i=0;i<=n;++i){
		sz[i]=0;
		for(int j=0;j<=n;++j){
			f[i][j]=0;
		}
	}
	dfs1(rt,0);
	for(int i=2;i<=n;++i){
		for(int j=0;j<=n;++j){
			for(int k=0;k<=n;++k){
				g[j][k]=0;
			}
		}
		g[0][0]=1;int nw=1;sz[rt]=1;
		Fv(E,rt){
			sz[rt]+=sz[e[E].v];
			for(int j=0;j<=Min(i-1,sz[rt]);++j){
				for(int k=0;k<=j;++k){
					if(2*k>=i){
						break;
					}
					g[nw][j]=(g[nw][j]+g[nw-1][j-k]*f[e[E].v][k]%MOD)%MOD;
				}
			}
			++nw;
		}
		--nw;
		ans=(ans+g[nw][i-1])%MOD;
	}
}
inline void calc2(){
	for(int i=0;i<=n;++i){
		sz[i]=0;
		for(int j=0;j<=n;++j){
			f[i][j]=0;
		}
	}
	dfs1(rt,rt2);dfs1(rt2,rt);
	ans=0;
	for(int i=1;i<=n/2;++i){
		ans=(ans+f[rt][i]*f[rt2][i]%MOD)%MOD;
	}
}
void init(){
	scanf("%d",&n);
	int u,v;
	et=rt=rt2=0;
	for(int i=1;i<=n;++i){
		h[i]=sz[i]=0;
	}
	for(int i=1;i<n;++i){
		scanf("%d%d",&u,&v);
		add(u,v);
	}
	totsz=n;
	mx[0]=INF;
	dfs0(1,0);
	if(!rt2){
		calc1();
	}else{
		calc2();
	}
	printf("Case %d: %d\n",Tid,ans);
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		++Tid;
		init();
	}
	return 0;
}

lp1337 JSOI2004 平衡点 or 吊打XXX

首先我们认识一种算法——爬山算法。这种算法总是贪心地接受更优秀的解。
但是,我们知道,并不是所有的解都是一个单峰函数。因此我们有了非常具有魔力的模拟退火算法。
我们想到一种随机化的优化方案,就是对于一个新的解,如果是更优的,就一定接受它;否则,有概率去接受它。
然而这样并不是特别优的,因为如果概率固定,那么它很大意义上还是在瞎JB跳。我们有一种被称为「模拟退火」的算法。我们定义一个全局变量T,令瞎JB跳的概率是\(e^{\frac{\Delta ans}{T}}\),然后我们令\(T\)不断降低,使得最后的答案趋于稳定。
我们相信,只要T足够大、尝试的次数足够多,那么总是能找到最优解。
然而,我们必须明白的是,模拟退火本质上是一种以时间换正确性的算法,因此要如何在时间和正确性之间取得平衡,就成为一个很困难的问题了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<cstdlib>
#include<ctime>
#define RD() (T*(rand()*2-RAND_MAX))
using namespace std;

typedef double db;
typedef long double ldb;
const int N=1005;
const ldb dlT=0.97;
const ldb eps=1E-14;
db x[N],y[N],w[N];
int n;
inline ldb calc(db X,db Y){
	db dx,dy,rt=0;
	for(int i=1;i<=n;++i){
		dx=x[i]-X,dy=y[i]-Y;
		rt+=sqrt(dx*dx+dy*dy)*w[i];
	}
	return rt;
}
void init(){
	scanf("%d",&n);
	db smx=0,smy=0;
	int tms=100;
	for(int i=1;i<=n;++i){
		scanf("%lf%lf%lf",x+i,y+i,w+i);
		smx+=x[i],smy+=y[i];
	}
	smx/=n,smy/=n;
	db ans,bst,x0,y0,x1,y1,nw;
	ans=bst=calc(smx,smy);
	srand(time(0));
	while(tms--){
		ans=bst,x0=smx,y0=smy;
		for(db T=100000;T>eps;T*=dlT){
			x1=x0+RD(),y1=y0+RD();
			nw=calc(x1,y1);
//			printf("%lf %lf\n",x1,y1);
			if(nw<bst){
				bst=nw;
				smx=x1,smy=y1;
			}
			if(nw<ans||(exp((ans-nw)/T)>(long double)rand()/RAND_MAX)){
				ans=nw;
				x0=x1,y0=y1;
			}
		}
	}
	printf("%.3lf %.3lf\n",smx,smy);
}
int main(){
	init();
	return 0;
}

lp4332 SHOI2014 三叉神经树

我们知道,每一个\(x_{i}\)各不相同。这启发我们,这一题的点将形成一棵树的结构。
仔细观察题目描述,我们发现,对于每一个点,它的修改影响到的有且仅有它的祖先。
我们不妨设一个点的权值为它的子节点们中信号为1的个数。那么根据题目给出的性质,当且仅当某个节点的权值为1的时候它的某个0子节点变成1,或者某个节点的权值为2的时候它的某个1子节点变成0,这个信号才会继续向上传输。容易发现,这样的传输覆盖的是且总是某一条竖直上下的全1/全2链。
详细地说,如果修改的叶子节点是0变成1,那么影响到的就是从它拉出的一条竖直向上的全1链以及这条链的父亲;如果修改的叶子节点是1变成0,那么影响到的就是从它拉出的一条竖直向上的全2链以及这条链的父亲。
因此,我们可以考虑在LCT剖出的实链上维护全1链以及全2链,然后修改的时候修改一整条链。这就完成了这题的要求。
但是仔细想想,我们会发现,维护全1链和全2链会显得很麻。所以我们不妨改为维护深度最深的非1节点和非2节点。对于将0变为1的操作,我们找到深度最深的非1节点,把它旋到根,然后修改即可,如果深度最深的非1节点不存在,那就意味着根节点也是1,那么答案就会发生变化;对于将1变为0的操作,如法炮制。
另外,由于这一题只有竖直上下的链的操作,所以我们甚至不需要写换根函数。当然,由于这一题没有分离和合并操作,因此,我们也不需要写分离和合并函数。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

inline void Swap(int &A,int &B){
	A^=B^=A^=B;
}
const int N=500005;
int fa[N*3],ch[N*3][2],val[N*3],n1[N*3],n2[N*3],lzy[N*3];
//先看右子节点(下方)是否存在,再看本节点是否满足要求,然后看左子节点(上方)是否存在。 
inline void updt(int X){
	n1[X]=n1[ch[X][1]]?n1[ch[X][1]]:(val[X]==1?n1[ch[X][0]]:X);
	n2[X]=n2[ch[X][1]]?n2[ch[X][1]]:(val[X]==2?n2[ch[X][0]]:X);
}
inline void rnw(int X,int V){
	val[X]^=3,Swap(n1[X],n2[X]),lzy[X]+=V;
}
inline void pshd(int X){
	if(lzy[X]!=0){
		rnw(ch[X][0],lzy[X]);rnw(ch[X][1],lzy[X]);lzy[X]=0;
	}
}
inline bool fndD(int X){
	return ch[fa[X]][1]==X;
}
inline bool ntrt(int X){
	return ch[fa[X]][0]==X||ch[fa[X]][1]==X;
}
inline void splayOne(int X){
	int Y=fa[X],Z=fa[Y],D=fndD(X),D2=fndD(Y),C=ch[X][D^1];
	if(ntrt(Y)){
		ch[Z][D2]=X;
	}
	ch[X][D^1]=Y,ch[Y][D]=C;
	if(C){
		fa[C]=Y;
	}
	fa[Y]=X,fa[X]=Z;
	updt(Y),updt(X);
}
int st[N*3];
inline void splay(int X){
	int Y=X,Z=0;
	st[++Z]=Y;
	while(ntrt(Y)){
		Y=fa[Y];
		st[++Z]=Y;
	}
	while(Z){
		pshd(st[Z--]);
	} 
	while(ntrt(X)){
		Y=fa[X],Z=fa[Y];
		if(ntrt(Y)){
			splayOne(fndD(X)^fndD(Y)?X:Y);
		}
		splayOne(X);
	}
}
inline void access(int X){
	for(int Y=0;X;Y=X,X=fa[X]){
		splay(X),ch[X][1]=Y,updt(X);
	}
}
int n,Q,in[N*3];
std::queue<int> q;
void init(){
	scanf("%d",&n);
	int x,y,z;
	for(int i=1;i<=n;++i){
		scanf("%d%d%d",&x,&y,&z);
		fa[x]=fa[y]=fa[z]=i;
		in[i]=3;
	}
	for(int i=1;i<=(n<<1|1);++i){
		scanf("%d",&x);
		q.push(i+n);
		val[i+n]=x<<1;
	}
	while(!q.empty()){
		x=q.front();
		q.pop();
		if(x<=n){
			updt(x);
		}
		val[fa[x]]+=val[x]>>1;
		--in[fa[x]];
		if(!in[fa[x]]){
			q.push(fa[x]);
		}
	}
	scanf("%d",&Q);
	int tp,nwrt=val[1]>>1;
	for(int i=1;i<=Q;++i){
		scanf("%d",&x);
		tp=(val[x]^=2)-1;
		x=fa[x];
		access(x),splay(x);
		if((~tp?n1:n2)[x]){
			x=(~tp?n1:n2)[x];
			splay(x);
			rnw(ch[x][1],tp),updt(ch[x][1]);
			val[x]+=tp;updt(x);
		}else{
			rnw(x,tp);updt(x);
			nwrt^=1;
		}
		puts(nwrt?"1":"0");
	}
}
int main(){
	init();
	return 0;
}

lp3203 HNOI2010 弹飞绵羊

依照题意,我们发现,题目求的就是指定点到根的路径长度。
于是,我们对于每一个修改弹力的操作,都可以转化为断边和连边的操作。
那么,我们用Splay维护大小,就可以实现了。
注意:sz数组需要初始化。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
inline void Swap(int &A,int &B){
	A^=B^=A^=B;
}
const int N=200005;
int fa[N],ch[N][2],sz[N];
inline void updt(int X){
	sz[X]=sz[ch[X][0]]+sz[ch[X][1]]+1;
}
inline bool fndD(int X){
	return ch[fa[X]][1]==X;
}
inline bool ntrt(int X){
	return ch[fa[X]][0]==X||ch[fa[X]][1]==X;
}
inline void splayOne(int X){
	int Y=fa[X],Z=fa[Y],D=fndD(X),D2=fndD(Y),C=ch[X][D^1];
	if(ntrt(Y)){
		ch[Z][D2]=X;
	}
	ch[X][D^1]=Y,ch[Y][D]=C;
	if(C){
		fa[C]=Y;
	}
	fa[Y]=X,fa[X]=Z;
	updt(Y),updt(X);
}
int st[N];
inline void splay(int X){
	int Y=X;
	while(ntrt(X)){
		Y=fa[X];
		if(ntrt(Y)){
			splayOne(fndD(X)^fndD(Y)?X:Y);
		}
		splayOne(X);
	} 
}
inline void access(int X){
	for(int Y=0;X;Y=X,X=fa[X]){
		splay(X),ch[X][1]=Y,updt(X);
	}
}
//令X在Y的上方。 
//由于这里保证存在有边,所以直接断边即可。 
inline void cut(int X){
	access(X),splay(X);
//	splay(Y);
//	fa[X]=ch[Y][0]=0;
	ch[X][0]=fa[ch[X][0]]=0;
}
inline void link(int X,int Y){
	fa[Y]=X;
	updt(X);
}
int a[N];
int n,q;
void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		sz[i]=1;
//		记得初始化sz数组 
		scanf("%d",&a[i]);
		if(i+a[i]<=n){
			link(i+a[i],i);
		}
	}
	scanf("%d",&q);
	int X,Y,op;
	for(int i=1;i<=q;++i){
		scanf("%d",&op);
		if(op==1){
			scanf("%d",&X);++X;
			access(X),splay(X);
			printf("%d\n",sz[X]);
		}else{
			scanf("%d%d",&X,&Y);++X;
			if(X+a[X]<=n){
				cut(X);
			}
			access(X),splay(X);
			if(X+Y<=n){
				link(X+Y,X);
			}
			a[X]=Y;
		}
	}
}
int main(){
//	freopen("3203.in","r",stdin);
//	freopen("3203.myout","w",stdout);
	init();
	return 0;
}

lp2147 SDOI2008 洞穴勘测

维护链接和断开,LCT裸题,(看起来)也可以用按秩合并优化并查集。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>


inline void Swap(int &A,int &B){
	A^=B^=A^=B;
} 
const int N=10005;

int fa[N],ch[N][2],rev[N]; 

inline void updt(int X){
	return;
}
inline void flp(int X){
	Swap(ch[X][0],ch[X][1]);
	rev[X]^=1;
}
inline void pshd(int X){
	if(rev[X]){
		flp(ch[X][0]),flp(ch[X][1]);
		rev[X]=0;
	}
}
inline int ntrt(int X){
	return ch[fa[X]][0]==X||ch[fa[X]][1]==X;
}
inline int fndD(int X){
	return ch[fa[X]][1]==X;
}
inline void splayOne(int X){
	int Y=fa[X],Z=fa[Y],D=fndD(X),D2=fndD(Y),C=ch[X][D^1];
	if(ntrt(Y)){
		ch[Z][D2]=X;
	}
	ch[X][D^1]=Y,ch[Y][D]=C;
	if(C){
		fa[C]=Y;
	}
	fa[Y]=X,fa[X]=Z;
	updt(Y),updt(X);
}
int st[N];
inline void splay(int X){
	int Y=X,Z=0;
	st[++Z]=Y;
	while(ntrt(Y)){
		Y=fa[Y],st[++Z]=Y;
	}
	while(Z){
		pshd(st[Z--]);
	}
	while(ntrt(X)){
		Y=fa[X],Z=fa[Y];
		if(ntrt(Y)){
			splayOne(fndD(X)^fndD(Y)?X:Y);
		}
		splayOne(X);
	}
}
inline void access(int X){
	for(int Y=0;X;Y=X,X=fa[X]){
		splay(X),ch[X][1]=Y,updt(X);
	}
}
inline void chgrt(int X){
	access(X),splay(X),flp(X);
}
inline int qryrt(int X){
	access(X),splay(X);
	while(ch[X][0]){
		pshd(X);
		X=ch[X][0];
	}
	splay(X);
	return X;
}
inline void split(int X,int Y){
	chgrt(X);
	access(Y),splay(Y);
}
inline bool cut(int X,int Y){
	split(X,Y);
	if(ch[Y][0]!=X||ch[X][1]){
		return 0;
	}
	fa[X]=ch[Y][0]=0;
	return 1;
}
inline bool link(int X,int Y){
	chgrt(X);
	if(qryrt(Y)==X){
		return 0;
	}
	fa[X]=Y;
	return 1;
}
int n,q;
char op[20]; 
void init(){
	scanf("%d%d",&n,&q);
	int x,y;
	for(int i=1;i<=q;++i){
		std::cin>>op;
		scanf("%d%d",&x,&y);
		switch(op[0]){
			case 'C':{
				link(x,y);
				break;
			}
			case 'D':{
				cut(x,y);
				break;
			}
			case 'Q':{
				chgrt(x);
				puts(qryrt(y)==x?"Yes":"No");
				break;
			}
		}
	} 
}
int main(){
	init();
	return 0;
}

lp3320 SDOI2015 寻宝游戏

我们找到了这样一个结论:
「一个树上点集构成的最小生成树中,若两点间有路径,则此两点的DFS序在树上相近。」
这个结论的证明是较为困难的,但是感性理解还是比较容易的。
有了这个结论,我们就可以解决这一题。
每当一个新的点x即将加入点集的时候,我们只需要计算点集中DFS序刚好比它小的点y和DFS序刚好比它大的点z,然后将答案加上如下的式子:
$$dis_{x,y}+dis_{x,z}-dis_{y,z}$$
删去的时候逆向操作即可。
维护点集可以使用set。(善用STL(大雾))计算路径长度可以LCA+容斥。

注意:记得开long long

#include<iostream>
#include<cstdio>
#include<set>

struct ee{
	int v;
	int w;
	int nxt;
}e[200005];
int h[100005],et=0;
inline void add(int U,int V,int W){
	e[++et]=(ee){V,W,h[U]};
	h[U]=et;
}
int fa[100005][30],dfn[100005],loc[100005],dep[100005],cnt=0;
long long val[100005];
//注意将两种深度分开。 
inline void dfs(int X,int FA){
	fa[X][0]=FA,dfn[X]=++cnt,loc[cnt]=X,dep[X]=dep[FA]+1;
	for(int i=h[X];i;i=e[i].nxt){
		if(e[i].v!=FA){
			val[e[i].v]=val[X]+e[i].w;
			dfs(e[i].v,X);
		}
	}
}

inline int lca(int X,int Y){
	if(dep[X]<dep[Y]){
		std::swap(X,Y);
	}
	for(int i=20;i>=0;--i){
		if(dep[X]-(1<<i)>=dep[Y]){
			X=fa[X][i];
		}
	}
	if(X==Y){
		return X;
	}
	for(int i=20;i>=0;--i){
		if(fa[X][i]!=fa[Y][i]){
			X=fa[X][i];
			Y=fa[Y][i];
		}
	}
	return fa[X][0];
}

inline long long dis(int X,int Y){
	return val[X]+val[Y]-(val[lca(X,Y)]<<1);
}

int n,m;
long long ans=0;
bool vis[100005];
std::set<int> s;
void init(){
	scanf("%d%d",&n,&m);
	int u,v,w;
	for(int i=1;i<n;++i){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
		add(v,u,w);
	}
	dfs(1,0);
	for(int j=1;j<=20;++j){
		for(int i=1;i<=n;++i){
			fa[i][j]=fa[fa[i][j-1]][j-1];
		}
	}
	int x,y,z;
	long long d;
	std::set<int>::iterator it;
	for(int i=1;i<=m;++i){
		scanf("%d",&x);
		x=dfn[x];
		if(!vis[loc[x]]){
			s.insert(x);
		}
		y=loc[(it=s.lower_bound(x))==s.begin()?*--s.end():*--it];
		z=loc[(it=s.upper_bound(x))==s.end()?*s.begin():*it];
		//注意运算符优先级。 
		if(vis[loc[x]]){
			s.erase(x);
		}
		x=loc[x];
		d=dis(x,y)+dis(x,z)-dis(y,z);
		if(!vis[x]){
			vis[x]=1;
			ans+=d;
		}else{
			vis[x]=0;
			ans-=d;
		}
		//注意前后的x不是一个x 
		printf("%lld\n",ans);
	}
}

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