题目描述

blablabla

(暴力) $O(n^2)$

首先考虑朴素做法
由于需要得到某个数是否出现过，并记录第一次出现的位置
故可以用哈希表记录某个元素第一次出现的位置
1. 若元素是第一次出现，直接取反即可.
2. 若元素已经出现过了，则哈希表中的位置是该元素最后一次出现的位置.
记录上一次出现的位置为$l$, 当前位置为$r$，则变换需要的就是区间$[l + 1, r - 1]$之内有多少个不同的元素
这个子问题最朴素的做法就是在遍历一遍区间$[l + 1, r - 1]$, 通过哈希表记录不同的元素的个数

时间复杂度

整个数组需要遍历一遍，时间复杂度$O(n)$, 而每次遍历子区间的时间复杂度也为$O(n)$,
故总的时间复杂度为$O(n^2)$

C++ 代码, (TLE, 只过了三个点)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
using namespace std;

const int N = 1e5 + 10;
unordered_map<int, int> pos;
int a[N];
int b[N];
int n;


int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for(int i = 1; i <= n; ++i) {
        if(pos.count(a[i]) == 0) {
            pos[a[i]] = i;
            b[i] = -a[i];
        }
        else {
            int t = pos[a[i]];
            unordered_set<int> s;
            for(int j = t + 1; j < i; ++j) s.insert(a[j]); 
            pos[a[i]] = i;
            b[i] = s.size();
        }
    }


    for(int i = 1; i <= n; ++i) printf("%d ", b[i]);
    puts("");

    return 0;
}

进行优化

1. 考虑朴素做法的瓶颈： 在求解子区间$[l + 1, r - 1]$之内有多少个不同的元素的时间复杂度为$O(n)$
   而$n$的数据范围为$10^5$, 故需要将求解子区间内元素的时间复杂度降到$O(1)$ 或者 $O(logn)$
2. 对于区间问题，时间复杂度$O(logn)$算法首先想到线段树和树状数组
   线段树维护的一般要求满足区间可加性，树状数组一般维护的是动态前缀和
   而本子问题要求解的是一个区间内不重复的元素组成的集合的大小
   不好直接用线段树或树状数组进行求解，故应该将问题进行转化
3. 既然是统计一个区间内不重复的元素的个数，那么我们可以对于相同的元素可以只统计最后一次出现那个
4. 构造辅助数组$st[]$, 若$a[i]$之前未出现过，直接令$st[i] = 1$；
   若之前出现过，且位置为$t$, 则$st[t] = 0, st[i] = 1$
5. 这样问题就转化成了求解区间$[l + 1, r - 1]$上$st[]$的和了，用线段树或者树状数组均可求解。

线段树 $O(nlogn)$

C++ 代码(AC)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
using namespace std;

const int N = 1e5 + 10;
unordered_map<int, int> pos;
int a[N];
bool st[N];//st[i] = true表示元素a[i]在[1 - 当前位置] 中最后一次出现
//故只需要维护区间内1的个数即可
int b[N];
int n;

struct Node {
    int l, r;
    int sum;
}tr[N * 4];

//用子节点信息更新父节点
void pushup(int u) {
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void build(int u, int l, int r) {
    tr[u] = {l, r, 0};
    if(l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
}

void modify(int u, int pos, int x) {
    if(tr[u].l == tr[u].r) {
        tr[u].sum = x;
        return;
    }
    int mid = tr[u].l + tr[u].r >> 1;
    if(pos <= mid) modify(u << 1, pos, x);
    else modify(u << 1 | 1, pos, x);
    pushup(u);
}

int query(int u, int l, int r) {
    if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
    int mid = tr[u].l + tr[u].r >> 1;
    int ans = 0;
    if(mid >= l) ans += query(u << 1, l, r);
    if(mid < r) ans += query(u << 1 | 1, l, r);
    return ans;
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    build(1, 1, n);
    for(int i = 1; i <= n; ++i) {
        if(pos.count(a[i]) == 0) {
            pos[a[i]] = i;
            b[i] = -a[i];
            st[i] = true;
            modify(1, i, 1);
        }
        else {
            int t = pos[a[i]];
            st[t] = false;
            st[i] = true;
            modify(1, t, 0);
            modify(1, i, 1);

            // unordered_set<int> s;
            // for(int j = t + 1; j < i; ++j) s.insert(a[j]); 
            pos[a[i]] = i;
            //b[i] = s.size();
            b[i] = query(1, t + 1, i - 1);
        }
    }


    for(int i = 1; i <= n; ++i) printf("%d ", b[i]);
    puts("");

    return 0;
}

树状数组 $O(nlogn)$

C++ 代码(AC)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <unordered_map>

using namespace std;

const int N = 1e5 + 10;
int tr[N];
int n;
int a[N];
unordered_map<int, int> pos;
int lowbit(int x) {
    return x & -x;
}
void add(int pos, int x) {
    for(int i = pos; i <= n; i += lowbit(i)) tr[i] += x;
}

int query(int pos) {
    int ans = 0;
    for(int i = pos; i > 0; i -= lowbit(i)) ans += tr[i];
    return ans;
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);

        if(pos.count(a[i]) == 0) {
            pos[a[i]] = i;
            add(i, 1);
            a[i] = -a[i];
        }
        else {
            int t = pos[a[i]];
            pos[a[i]] = i;
            add(t, -1);
            add(i, 1);
            a[i] = query(i - 1) - query(t);

        }
    }
    for(int i = 1; i <= n; ++i) printf("%d ", a[i]);

    return 0;
}