As most of the ACMers, wy's next target is algorithms, too. wy is clever, so he can learn most of the algorithms quickly. After a short time, he has learned a lot. One day, mostleg asked him that how many he had learned. That was really a hard problem, so wy wanted to change to count other things to distract mostleg's attention. The following problem will tell you what wy counted.
Given 2N integers in a line, in which each integer in the range from 1 to N will appear exactly twice. You job is to choose one integer each time and erase the two of its appearances and get a mark calculated by the differece of there position. For example, if the first 3 is in position 86 and the second 3 is in position 88, you can get 2 marks if you choose to erase 3 at this time. You should notice that after one turn of erasing, integers' positions may change, that is, vacant positions (without integer) in front of non-vacant positions is not allowed.
Input
There are multiply test cases. Each test case contains two lines.
The first line: one integer N(1 <= N <= 100000).
The second line: 2N integers. You can assume that each integer in [1,N] will appear just twice.
Output
One line for each test case, the maximum mark you can get.
Sample Input
3
1 2 3 1 2 3
3
1 2 3 3 2 1
Sample Output
6
9
Hint
We can explain the second sample as this. First, erase 1, you get 6-1=5 marks. Then erase 2, you get 4-1=3 marks. You may notice that in the beginning, the two 2s are at positions 2 and 5, but at this time, they are at positions 1 and 4. At last erase 3, you get 2-1=1 marks. Therefore, in total you get 5+3+1=9 and that is the best strategy.
【分析】
比较水的一道题，根据题意可知，任何两个区间仅为相交或包含的关系。
相交无论先删除哪一个对结果都没有影响，包含当然要先删除外面的那一个，所以从后往前删不会有包含的关系。
具体用树状数组实现就可以了。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <utility>
#include <iomanip>
#include <string>
#include <cmath>
#include <map> const int MAXN = * + ;
using namespace std;
struct DATA{
int l, r;
}num[MAXN * ];
int data[MAXN * ];
int C[MAXN * ], cnt[MAXN * ];
int n;
bool get[MAXN * ]; int lowbit(int x){return x&-x;}
void add(int x, int val){
while (x <= * n){
C[x] += val;
x += lowbit(x);
}
return;
}
int sum(int x){
int cnt = ;
while (x > ){
cnt += C[x];
x -= lowbit(x);
}
return cnt;
}
void init(){
C[] = ;
for (int i = ; i <= * n; i++) C[i] = cnt[i] = ;
for (int i = ; i <= * n; i++){
scanf("%d", &data[i]);
if (cnt[data[i]] == ) {num[data[i]].l = i;cnt[data[i]]++;}
else num[data[i]].r = i;
add(i, );
}
long long Ans = ;
memset(get, , sizeof(get));
for (int i = * n; i >= ; i--){
if (get[i] == ) continue;
Ans += sum(i) - sum(num[data[i]].l);
add(i, -);
add(num[data[i]].l, -);
get[i] = get[num[data[i]].l] = ;
}
printf("%lld\n", Ans);
} int main(){
int T = ;
#ifdef LOCAL
freopen("data.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
while (scanf("%d", &n) != EOF){
init();
}
return ;
}