首页 > 代码库 > BZOJ 1106 [POI2007]立方体大作战tet（树状数组）
BZOJ 1106 [POI2007]立方体大作战tet（树状数组）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1106
【题目大意】
给定玩家一个有2n个元素的栈，元素一个叠一个地放置。
这些元素拥有n个不同的编号，每个编号正好有两个元素。
玩家每次可以交换两个相邻的元素。如果在交换之后，两个相邻的元素编号相同，
则将他们都从栈中移除，所有在他们上面的元素都会掉落下来并且可以导致连锁反应。
玩家的目标是用最少的步数将方块全部消除。
【题解】
我们发现如果有一对可消除的方块在另一对中间，那么肯定是这一对先消除更优
因此我们用模拟消除的过程，对于每种颜色，记录其上次出现的位置，
如果一个方块未被消除，则在树状数组中记录为1，否则记录为0，
那么一个颜色与其上一次出现的位置在树状数组中的查询前缀和之差就是消除时要消耗的移动距离。
【代码】
#include <cstdio>#include <algorithm>#include <cstring>using namespace std;typedef long long LL;const int N=50010;int pre[N],c[N<<1],n;void add(int x,int val){while(x<=2*n)c[x]+=val,x+=x&-x;}int query(int x){int s=0;while(x)s+=c[x],x-=x&-x;return s;}int main(){ while(~scanf("%d",&n)){ memset(pre,0,sizeof(pre)); memset(c,0,sizeof(c)); LL ans=0; for(int i=1;i<=n*2;i++){ int x; scanf("%d",&x); if(pre[x]){ ans+=query(i)-query(pre[x]); add(pre[x],-1); }else add(pre[x]=i,1); }printf("%lld\n",ans); }return 0;}BZOJ 1106 [POI2007]立方体大作战tet（树状数组）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。