题目

题目大意

有一堆点，每个点都有其权值\(c_i\)。

每次插入边\((u,v)\)，\(u\)和\(1\)连通，\(v\)和\(1\)不连通。最后保证形成一棵树。

每次插入的时候询问\(1\)到\(u\)的路径上逆序对的个数。然后将\(1\)到\(u\)的路径上的所有节点的权值设为\(c_v\).

思考历程

一看就知道是什么数据结构题了……

然而刚了很久都不知道怎么做……

于是就直接打暴力。暴力跳\(fa\)，用树状数组计算逆序对的个数。

后来还有点时间，于是看准了\(c_i\leq 2\)的数据。

于是打了个树链剖分加线段树来维护。线段树上每个区间维护的是个大小为\(3\)的桶和答案，区间合并的时候就是左右两边的答案加上左边权值大于右边的个数。

打完了之后急着去吃饭，完全没有调过……

后来发现这个树链剖分没有分……倒是覆盖了我的暴力……原来暴力是可以吃掉\(c_i\leq 2\)的数据的……

正解

看到正解的时候我也震惊了……

请用脑子模拟一下操作的画面。

然后试着跟\(LCT\)建立联系。

于是我们就发现这个操作过程与\(LCT\)神似！

每个\(splay\)维护权值相同的一条链，修改的时候相当于\(access\)上去……

将它到祖先的路径全部变成同一个权值。

我们也知道\(LCT\)的时间复杂度是均摊\(\lg n\)的。虽然不会证明。

那么我们可以理解成出现过的颜色相同的段数是\(O(n\lg n)\)级别的。

询问的时候用树状数组来维护。模拟\(access\)的过程就可以了。

于是这题就非常轻松地AC了。而且由于这题完全不需要\(mroot\)操作，所以也不用翻转……

\(LCT\)短得跟树链剖分差不多……

代码

using namespace std;

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 100010

int n;

int c[N],maxc;

int *p[N];

inline bool cmpp(int *x,int *y){

	return *x<*y;

}

int t[N];

#define lowbit(x) ((x)&(-(x)))

inline void add(int x,int c){

	for (;x<=maxc;x+=lowbit(x))

		t[x]+=c;

}

inline int query(int x){

	int res=0;

	for (;x;x-=lowbit(x))

		res+=t[x];

	return res;

}

inline void clear(int x){

	for (;x<=maxc && t[x];x+=lowbit(x))

		t[x]=0;

}

struct Node{

	Node *fa,*c[2];

	int is_root;

	int siz;

	inline void update(){siz=c[0]->siz+c[1]->siz+1;}

	inline bool getson(){return fa->c[0]!=this;}

	inline void rotate(){

		Node *y=fa,*z=y->fa;

		if (y->is_root){

			is_root=y->is_root;

			y->is_root=0;

		}

		else

			z->c[y->getson()]=this;

		int k=getson();

		fa=z;

		y->c[k]=c[k^1];

		c[k^1]->fa=y;

		c[k^1]=y;

		y->fa=this;

		siz=y->siz,y->update();

	}

	inline void splay(){

		while (!is_root){

			if (!fa->is_root){

				if (getson()!=fa->getson())

					rotate();

				else

					fa->rotate();

			}

			rotate();

		}

	}

} d[N],*null;

int main(){

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

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

	scanf("%d",&n);

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

		scanf("%d",&c[i]),p[i]=&c[i];

	sort(p+1,p+n+1,cmpp);

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

		if (*p[i]!=last){

			maxc++;

			last=*p[i];

		}

		*p[i]=maxc;

	}

	null=d;

	*null={null,null,null,0,0};

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

		d[i]={null,null,null,c[i],1};

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

		int u,v;

		scanf("%d%d",&u,&v);

		Node *x,*y;

		long long ans=0;

		for (x=&d[u];x!=null;x=x->fa){

			x->splay();

			ans+=(long long)query(x->is_root-1)*(x->c[0]->siz+1);

			add(x->is_root,x->c[0]->siz+1);

		}

		printf("%lld\n",ans);

		d[v].fa=&d[u];

		for (x=&d[v],y=null;x!=null;y=x,x=x->fa){

			x->splay();

			clear(x->is_root);

			x->c[1]->is_root=x->is_root;

			x->c[1]=y;

			y->is_root=0;

			x->update();

		}

		y->is_root=c[v];

	}

	return 0;

}

思考历程

在分析复杂度的时候，可以试着结合自己学过的数据结构……

巴特西

[JZOJ6257] 【省选模拟8.9】修路

题目

题目大意

思考历程

正解

代码

思考历程

最新文章

热门文章