Description
一个叫做立方体大作战的游戏风靡整个 Byteotia。这个游戏的规则是相当复杂的,所以我们只介绍他的简单规则:给定玩家一个有 2n 个元素的栈,元素一个叠一个地放置。这些元素拥有 n 个不同的编号,每个编号正好有两个元素。玩家每次可以交换两个相邻的元素。如果在交换之后,两个相邻的元素编号相同.则将他们都从栈中移除,所有在他们上面的元素都会掉落下来并且可以导致连锁反应。玩家的目标是用最少的步数将方块全部消除。
Input
输入文件第一行包含一个正整数 n(1<=n<=50000)。接下来 2n 行每行一个数ai,从上到下描述整个栈,保证每个数出现且仅只出现两次(1<=ai<=n)。初始时,没有两个相同元素相邻。并且保证所有数据都能在 1000000 步以内出解。
Output
输出文件第一行包含一个数 m,表示最少的步数。
Sample Input #1
5
5
2
3
1
4
1
4
3
5
2
Sample Output #1
2
Sample Input #2
3
1
2
3
1
2
3
Sample Output
3
Solution
假设要消去第i个和第j个方块，那么当这两个方块消去时，只会影响有一个元素在区(i,j)中的两个元素的距离。那么我们需要以一种方式去消去这些方块。在决定两种方块的消去顺序时，假设其对应区间为包含关系，那么显然先消去被包含的区间要更优。若两个区间仅存在交集，那么无论先消去哪两个都一样。如果两个区间的交集为空，那么消去顺序对答案没有影响。综上所述，我们得到如下贪心策略：每当遇到一个重复出现的元素时就消去它。每次消去的操作次数即为区间中还没有消去的元素个数，可以转化为区间和用树状数组维护。如果一个点上有元素就设为1，消去后变为0。
#include <iostream>
#include <cstdio>
#define N 50002
using namespace std;
int n,i,pos[N],c[N],ans;
int lowbit(int x)
{
return x&(-x);
}
void modify(int x,int y)
{
for(int i=x;i<=2*n;i+=lowbit(i)) c[i]+=y;
}
int sum(int x)
{
int ans=0;
for(int i=x;i>=1;i-=lowbit(i)) ans+=c[i];
return ans;
}
int main()
{
freopen("tet.in","r",stdin);
freopen("tet.out","w",stdout);
cin>>n;
for(i=1;i<=2*n;i++){
int x;
cin>>x;
if(pos[x]==0){
pos[x]=i;
modify(i,1);
}
else{
ans+=sum(i)-sum(pos[x]);
modify(pos[x],-1);
}
}
cout<<ans<<endl;
fclose(stdin);
fclose(stdout);
return 0;
}