LA 5902 - Movie collection 树状数组（Fenwick树）

看题传送门

题目大意：XXX喜欢看电影，他有好多好多的影碟，每个影碟都有个独立的编号。开始是从下往上影碟的顺序是n~1，他每次拿出影碟的时候，你需要输出压在该影碟上的有几个。（拿出后其他影碟顺序不变）看完影碟后，XXX会把影碟放在最上面。

感冒了，不好玩T T

这题依旧是Fenwick树的应用。

但是有点奇怪是吗？我们要如何表示出来？

我们可以取向上为正方向。（→_→喂，我不是在做物理，我不要受力分析~\(≧▽≦)/~）

然后呢？Position[ 1 ]存的是n 也就是倒序存，为什么这么做呢？可以这么想，Position[ index] 这个数组，Index 就是影碟的编号，而里面存的内容越大，表示越在上面。

那么C[x]呢，存的是x到底部的距离。（最底下的为1）

好，那么当他要拿出影碟（编号为id）的时候，我们就可以直接用position[id] 获取他的位置并且用Fenwick来计算答案t了，此时t是到底部距离，需要n-t

之后放到顶部呢？

编号大于id的才需要-1（即压在id上的），所以直接update(position[id],-1)即可。

详见代码吧。

#include<cstdio>

const int MAXN=200000+10;

int position[MAXN],C[MAXN];

inline int lowbit(int x)

{

	return x&(-x);

}

void update(int x,int d)

{

	while(x<=MAXN)

	{

		C[x]+=d;

		x+=lowbit(x);

	}

}

int sum(int x)

{

	int ans=0;

	while(x>0)

	{

		ans+=C[x];

		x-=lowbit(x);

	}

	return ans;

}

int main()

{

	int T;

	scanf("%d",&T);

	while(T--)

	{

		int n,m;

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

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

			position[i]=n-i+1;      //取向上为正方向。→_→你在做物理？

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

			C[i]=lowbit(i);			//C记录到底部距离

		int top=n;

		for(int i=0;i<m;i++)

		{

			int id;

			scanf("%d",&id);

			if(i!=0)

				printf(" ");

			printf("%d",n-sum( position[id] ) );

			update(position[id],-1);

			position[id]=++top;

		}

		printf("\n");

	}

}

巴特西

LA 5902 - Movie collection 树状数组（Fenwick树）

最新文章

热门文章