题目

其中n,q≤500000n,q\leq 500000n,q≤500000

题目大意

让你维护一个堆。支持一下操作：

在某个点的下面加上另一个点，然后进行上浮操作。

询问某一点的权值。

思考历程

一眼看这题，诶，不就是那道中学生数据结构题吗？

直接树链剖分，然后splay一波搞定！

思想还是很简单的！

但是感觉有点长……

正解

上面的这个解法算是一个正解吧。

但是我还是没打，因为代码可能很长……（想一想，又树链剖分，又splay的有点麻烦）

然后这题LCT也可以做！就是LCT和一个splay！由于LCT本来就是用splay来实现的，所以，在打板的时候还比较容易，只不过……

先不要说。现在说一说解法。

我们知道，上浮操作其实就是轮换操作。但是，如果我们直接在LCT中轮换，那么我们会将点的位置改变，不只是权值的改变！

所以说，我们要再用一个splay来维护一下链上点的权值。对于LCT上的每一条链（也就是LCT中的每一个splay），另外维护一个以权值为关键字的splay。这两个splay其中的顺序是一一对应的。当我们要轮换的时候，只需要轮换那个splay中的值。在查询的时候查与其对应位置的值就好了。

不过再想想，代码还是有点复杂的，虽然比较简单。我们再进行LCT操作的时候，我们还要维护一下那些splay，所以要加一些东西！当然，在宏观的意义上，这个还是比较好理解的。

然后还有一个比较简单的做法：离线，树链剖分和权值线段树！

这个似乎比较好打很多……在这里理清一下思路。

我们先将整棵树建出来（当然，是树的最后形态），然后树链剖分剖成许多条重链！

对于每一条重链，我们分别维护一个权值线段树。

在我们进行操作的时候，如果是询问，那就直接通过它在重链中的位置，在权值线段树中把它给找出来。

如果是插入一个点，那就将其加入权值线段树中（之前是无限大），然后和重链顶端的父亲上面的值对比一下，如果比它小，那就进行替换，然后继续往上跳。

其实不一定要使用权值线段树，平衡树也是一个不错的选择……

总感觉这题的正解有好多……

代码

using namespace std;

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 1000000

#define Q 500000

#define MAX 1000001

int n,nn,q;

struct EDGE{

	int to;

	EDGE *las;

} e[N+1];

int ne;

EDGE *last[N+1];

inline void link(int u,int v){

	e[++ne]={v,last[u]};

	last[u]=e+ne;

}

int a[N+1];

struct Oper{

	bool op;

	int x;

} o[Q+1];

int fa[N+1],siz[N+1],dep[N+1],hs[N+1];

void init1(int);

int top[N+1];

void init2(int,int);

struct Segment_Tree{

	int l,r;

	int sum;

} seg[20000001];

int cnt;

void add(int,int,int,int,int);

int kth(int,int,int,int);

int tos[N+1];//tos[i]表示i所在的重链对应的线段树根节点的编号

inline void insert(int);

int main(){

	freopen("heap.in","r",stdin);

	freopen("heap.out","w",stdout);

	scanf("%d%d",&n,&q);

	for (int i=1;i<=n;++i){

		scanf("%d%d",&fa[i],&a[i]);

		if (fa[i])

			link(fa[i],i);

	}

	nn=n;

	for (int i=1;i<=q;++i){

		int op;

		scanf("%d",&op);

		if (op==1){

			++nn;

			scanf("%d%d",&fa[nn],&a[nn]);

			link(fa[nn],nn);

			o[i]={0,nn};

		}

		else{

			int x;

			scanf("%d",&x);

			o[i]={1,x};

		}

	}

	init1(1);

	init2(1,1);

	for (int i=1;i<=nn;++i)

		if (top[i]==i){

			tos[i]=++cnt;

			seg[cnt]={0,0,0};

		}

	for (int i=1;i<=nn;++i)

		tos[i]=tos[top[i]];

	for (int i=1;i<=n;++i)

		add(tos[i],1,MAX,a[i],1);

	for (int i=1;i<=q;++i)

		if (o[i].op==0)

			insert(o[i].x);

		else

			printf("%d\n",kth(tos[o[i].x],1,MAX,dep[o[i].x]-dep[top[o[i].x]]+1));

	return 0;

}

void init1(int x){

	dep[x]=dep[fa[x]]+1;

	siz[x]=1;

	for (EDGE *ei=last[x];ei;ei=ei->las){

		init1(ei->to);

		siz[x]+=siz[ei->to];

		if (siz[ei->to]>siz[hs[x]])

			hs[x]=ei->to;

	}

}

void init2(int x,int t){

	top[x]=t;

	if (hs[x])

		init2(hs[x],t);

	for (EDGE *ei=last[x];ei;ei=ei->las)

		if (ei->to!=hs[x])

			init2(ei->to,ei->to);

}

void add(int k,int l,int r,int x,int c){

	seg[k].sum+=c;

	if (l==r)

		return;

	int mid=l+r>>1;

	if (x<=mid){

		if (!seg[k].l)

			seg[k].l=++cnt;

		add(seg[k].l,l,mid,x,c);

	}

	else{

		if (!seg[k].r)

			seg[k].r=++cnt;

		add(seg[k].r,mid+1,r,x,c);

	}

}

int kth(int k,int l,int r,int x){

	if (l==r)

		return l;

	int mid=l+r>>1;

	if (x<=seg[seg[k].l].sum)

		return kth(seg[k].l,l,mid,x);

	return kth(seg[k].r,mid+1,r,x-seg[seg[k].l].sum);

}

inline void insert(int x){

	add(tos[x],1,MAX,a[x],1);

	int v=a[x];

	while (fa[top[x]]){

		int y=fa[top[x]],mn=kth(tos[y],1,MAX,dep[y]-dep[top[y]]+1);//找出重链的父亲的值

		if (v<mn){

			//交换

			add(tos[x],1,MAX,v,-1);

			add(tos[x],1,MAX,mn,1);

			add(tos[y],1,MAX,mn,-1);

			add(tos[y],1,MAX,v,1);

			x=y;

		}

		else

			break;

	}

}

总结

树链剖分真是一个好东西……

LCT真是一个好东西……

……

巴特西

[JZOJ5977] 【清华2019冬令营模拟12.15】堆

题目

题目大意

思考历程

正解

代码

总结

最新文章

热门文章