链接
http://acm.hit.edu.cn/problemset/2430
题意
给你一个由
1
−
n
,
n
1-n\ ,n
1−n ,n个数组成的长度为
2
n
2n
2n的整数序列，其中
1
−
n
1-n
1−n每个数出现两次，现在定义一个数产生的一个
v
a
l
u
e
value
value为它出现的两个位置的差值，如
x
x
x出现在
a
、
b
a、b
a、b两个位置，那么
v
a
l
u
e
=
b
−
a
(
b
>
a
)
value=b-a(b>a)
value=b−a(b>a)，之后你需要从序列中删除掉这两个数，并且你需要把序列整合即需要填充空位，每次求值之后你都需要这样进行整合，现在需要你求所有数的最大
v
a
l
u
e
value
value和；
分析
对于一个序列1、2、2、1，那么我们肯定不能先计算2，因为2计算之后会导致1的间距变小，所以我们需要先计算外面的，对于1、3、2、1、3、2，我们也肯定不能计算3，因为3计算后会导致1与2的结果都变小，虽然先计算1或者2也会变小，但是它只会减少1，多举几个例子发现需要贪心的从外往里进行计算（从右往左或从左往右都可以）； 考虑每个数产生的值可以转换为区间和，代表两个位置之间整数的个数，每删除一个数，就在它的两个位置插入一个-1； 之后我们使用树状数组，树状数组的下标代表位置，开始的时候我们需要在每个位置都插入一个1，因为序列还没有进行删除操作；对于同一个数我们记录下它的两个位置，然后我们便开始从右往左或者从左往右遍历，遇到一个数我们就计算它产生的值即
s
u
m
(
b
)
−
s
u
m
(
a
)
(
b
>
a
)
sum(b)-sum(a)(b>a)
sum(b)−sum(a)(b>a)，其中a、b即是该数出现的两个位置，之后我们在树状数组的这两个位置插入-1，表明该位置数已被删除，然后将该数字标记说明已经计算了，累加所有数的结果即可；
代码
#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#define INF 0x7f7f7f7f
#define MAXN 100005
#define N 200005
#define P 2
#define MOD 99991
typedef long long ll
;
namespace fastIO
{
inline int read() {
char c
= getchar(); int x
= 0, f
= 1;
while (c
< '0' || c
> '9') { if (c
== '-') f
= -1; c
= getchar(); }
while (c
>= '0' && c
<= '9') x
= x
* 10 + c
- '0', c
= getchar();
return x
* f
;
}
}
using namespace fastIO
;
using namespace std
;
int n
, c
[2 * MAXN
], r
[MAXN
], a
[2 * MAXN
];
void insert(int x
, int val
) {
for (int i
= x
; i
<=2 * n
; i
+= i
& -i
)
c
[i
] += val
;
}
int sum(int x
) {
if (x
<= 0) return 0;
int res
= 0;
for (int i
= x
; i
> 0; i
-= i
& -i
)
res
+= c
[i
];
return res
;
}
int main() {
while (cin
>> n
) {
memset(c
, 0, sizeof(c
));
for (int i
= 1; i
<= 2 * n
; i
++) {
cin
>> a
[i
];
insert(i
, 1);
r
[a
[i
]] = i
;
}
int res
= 0;
for (int i
= 1; i
<= 2 * n
; i
++) {
int t
= r
[a
[i
]];
if (!t
)continue;
res
+= (sum(t
) - sum(i
));
insert(t
, -1); insert(i
, -1);
r
[a
[i
]] = 0;
}
cout
<< res
<< endl
;
}
}
