跳转至

union 去重

Bug

unique是algorithm中的一个函数，可以对数组进行去重（离散化的时候会用到）。如下：

1
int newN = unique(num + 1, num + 1 + n) - num - 1;

但是后面的“-num-1”经常容易丢掉“-1”。unique函数返回的是去重完毕的数组尾地址的后一个。所以有如下标准写法：

1
int newN = unique(Begin, End) - Begin;

因为我们知道“数组尾地址的后一个”减去数组首地址就是数组的长度。将num+1代入Begin，就可得到正确写法。

注意区分

函数lower_bound返回的也是数组地址（迭代器）。但是由于lower_bound函数返回的地址不是目标地址的下一个，因此不需要“-1”，直接减去数组名即可。

错题

P1908 逆序对

  • 离散化去重时，unique地址应减“数组地址 + 1”而不是 “数组地址”
  • 因为union函数返回的是数组尾地址的后一个
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int main(){

    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        num[i] = a[i];
    }

    sort(num + 1, num + 1 + n);
    // 这里
    int newN = unique(num + 1, num + 1 + n) - num - 1;
    for(int i = 1; i <= newN; i++){
        mp[num[i]] = i;
    }

    newN += 5;

    long long ans = 0;
    for(int i = 1; i <= n; i++){
        ans += query(1, 1, newN, mp[a[i]] + 1, newN);
        update(1, 1, newN, mp[a[i]], 1);
    }
    cout << ans << endl;

    return 0;
}