题目描述

难度分:$1800$

输入$n$，$k(1 \leq k \leq n \leq 10^5)$和长为$n$的数组$a(-10^9 \leq a[i] \leq 10^9)$。

对于每个长为$k$的连续子数组，输出子数组内的恰好出现一次的最大元素。如果不存在这样的元素，输出Nothing。

输入样例$1$

5 3
1
2
2
3
3

输出样例$1$

1
3
2

输入样例$2$

6 4
3
3
3
4
4
2

输出样例$2$

4
Nothing
3

算法

滑动窗口+平衡树

数据结构爽题！

平衡树

整体就是滑动窗口，构建一个按照“频数降序，数值升序”排序的平衡树（有序集合）$st$，其中存储二元组（数值$x$在子数组中的频数，数值$x$），用于维护窗口中每个数值的频数信息。按照这样的排序规则，只要遍历到某个窗口时，就能保证$st$的头部始终都是频数最小数的二元组，只要这个数的频数是$1$，那么它对应的数值就应该是当前窗口的解，输出这个数值；如果频数不是$1$，当前窗口就无解，输出Nothing。

哈希表

还需要一个哈希表$val2freq$来存储窗口内每个数值的频数，为的就是在窗口滑动的时候快速获得之前窗口端点数值的“老”频数。

滑动窗口

接下来就是滑动窗口来维护$st$，每次加入一个新的元素$a[i]$，都会出去一个老的元素$a[i-k]$。通过$val2freq$获得它们在上一个窗口的频数，然后更新在$st$和$val2freq$中的频数信息即可。这样进行一番操作后，$st$的头部又变成了当前窗口中频数最小且数值最大的元素所组成的二元组，还是按照频数是否为$1$来输出答案即可。

复杂度分析

时间复杂度

只遍历了一次数组，每次遍历的瓶颈在于有限几次对平衡树的删除和插入操作，时间复杂度都是$O(log_2n)$的，因此算法整体的时间复杂度为$O(nlog_2n)$。

空间复杂度

空间消耗在于平衡树$st$和哈希表$val2freq$，在最差情况下，平衡树需要存储$O(n)$个二元组，哈希表需要存储$O(n)$个键值对，因此额外空间复杂度为$O(n)$、

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <chrono>
#include <set>
#include <unordered_map>

using namespace std;
typedef pair<int, int> PII;

const int N = 200010;
int n, k, a[N];

struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
      x += 0x9e3779b97f4a7c15;
      x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
      x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
      return x ^ (x >> 31);
  }

  size_t operator()(uint64_t x) const {
      static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
      return splitmix64(x + FIXED_RANDOM);
  }
};

int main() {
    scanf("%d%d", &n, &k);
    set<PII> st;
    unordered_map<int, int, custom_hash> val2freq;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        if(i <= k) {
            val2freq[a[i]]++;
        }
    }
    for(auto&[num, cnt]: val2freq) {
        st.insert({cnt, -num});
    }
    auto& t = *st.begin();
    if(t.first == 1) {
        printf("%d\n", -t.second);
    }else {
        puts("Nothing");
    }
    for(int i = k + 1; i <= n; i++) {
        int left = a[i - k], right = a[i];
        if(left != right) {
            int lfreq = val2freq[left], rfreq = val2freq.find(right) != val2freq.end()? val2freq[right]: 0;
            st.erase({lfreq, -left});
            --lfreq;
            if(lfreq) {
                st.insert({lfreq, -left});
                val2freq[left] = lfreq;
            }else {
                val2freq.erase(left);
            }
            st.erase({rfreq, -right});
            ++rfreq;
            st.insert({rfreq, -right});
            val2freq[right] = rfreq;
        }
        auto& t = *st.begin();
        if(t.first == 1) {
            printf("%d\n", -t.second);
        }else {
            puts("Nothing");
        }
    }
    return 0;
}