[文章目录]
Description
一个叫做立方体大作战的游戏风靡整个Byteotia。这个游戏的规则是相当复杂的，所以我们只介绍他的简单规则：给定玩家一个有2n个元素的栈，元素一个叠一个地放置。这些元素拥有n个不同的编号，每个编号正好有两个元素。玩家每次可以交换两个相邻的元素。如果在交换之后，两个相邻的元素编号相同，则将他们都从栈中移除，所有在他们上面的元素都会掉落下来并且可以导致连锁反应。玩家的目标是用最少的步数将方块全部消除。n<=50000
发现对于形如"ABAB"的，无论怎么交换，中间的BA都至少需要交换一次。同时，发现可以构造一种方案使得仅交换上述形态可以全部消除方块。
树状数组统计上述形态对数即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,f[101000];
void fix(int x,int y){while(x<=(n<<1)) f[x]+=y,x+=-x&x;}
int query(int x){int re=0; while(x>0) re+=f[x],x-=-x&x; return re;}
int pos[51000];
int main()
{
scanf("%d",&n); int i,x,ans=0;
for(i=1;i<=(n<<1);++i)
{
scanf("%d",&x);
if(pos[x])
{
ans+=query(i)-query(pos[x]);
fix(pos[x],-1);
}
else pos[x]=i,fix(i,1);
}
printf("%d",ans);
return 0;
}