Codeforces Beta Round #63 (Div. 2) E. Subsegments（map + set）

红太狼 2023-07-04 08:38 7阅读 0赞

> 原题链接：[https://codeforces.com/contest/69/problem/E][https_codeforces.com_contest_69_problem_E]

Programmer Sasha has recently begun to study data structures. His coach Stas told him to solve the problem of finding a minimum on the segment of the array in , which Sasha coped with. For Sasha not to think that he had learned all, Stas gave him a new task. For each segment of the fixed length Sasha must find the maximum element of those that occur on the given segment exactly once. Help Sasha solve this problem.

**Input**  
The first line contains two positive integers n and k (1 ≤ n ≤ 105, 1 ≤ k ≤ n) — the number of array elements and the length of the segment.

Then follow n lines: the i-th one contains a single number ai ( - 109 ≤ ai ≤ 109).

**Output**  
Print n–k + 1 numbers, one per line: on the i-th line print of the maximum number of those numbers from the subarray ai ai + 1 … ai + k - 1 that occur in this subarray exactly 1 time. If there are no such numbers in this subarray, print “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

**题意：** 给一个长度为 n 的数组，输出 n-k-1 个数，分别为下标为 i 到 i+k-1 这个区间内存在且只出现一次的数的最大值，不存在则输出 “Nothing”。

**思路：**

1.  该题可以用线段树来做也可以用STL来做，这里用STL解答。
2.  先把前 k 个数只出现一次的数存入 set 集合里，自动从小到大排序，如果不为空则输出最后一个数，否则输出 “Nothing”。
3.  然后从 k+1 开始，每加入一个数就删去上一个区间的第一个数，并判断删去的数剩下的个数是否为 1，若是，则加入可行集合 set 里，否则就看它是否在可行集合里，在的话就删掉。
4.  然后再判断新加入的数的个数是否为 1，是的话加入可行集合里，否则就看它是否在可行集合里，在的话就删掉。
5.  最后再判断该区间的可行集合里是否为空，为空的话就输出 “Nothing”，否则输出最后一个数。

> [【总结】C++ 基础数据结构 —— STL之集合（set）用法详解][C_ _ _ STL_set]  
> [【总结】C++ 基础数据结构 —— STL之关联容器（map）用法详解][C_ _ _ STL_map]

**Code：**

#include <iostream>
    #include <map>
    #include <set>
    using namespace std;
    const int N=1e5+100;
    map<int,int> mp;
    set<int> s;
    int a[N];
    int main()
    { 
        int n,k;    cin>>n>>k;
        for(int i=1;i<=n;i++)   cin>>a[i];
        for(int i=1;i<=n;i++){ 
            if(i<=k){ 
                mp[a[i]]++;
                if(mp[a[i]]==1) s.insert(a[i]);
                else{ 
                    if(s.find(a[i])!=s.end())
                        s.erase(a[i]);
                }
                if(i==k){ 
                    if(s.empty())   cout<<"Nothing"<<endl;
                    else    cout<<*(--s.end())<<endl;
                }
            }
            else{ 
                mp[a[i]]++;
                mp[a[i-k]]--;
                if(mp[a[i]]==1) s.insert(a[i]);
                else{ 
                    if(s.find(a[i])!=s.end())
                        s.erase(a[i]);
                }
                if(mp[a[i-k]]==1)   s.insert(a[i-k]);
                else{ 
                    if(s.find(a[i-k])!=s.end())
                        s.erase(a[i-k]);
                }
                if(s.empty())   cout<<"Nothing"<<endl;
                else    cout<<*(--s.end())<<endl;
            }
        }
        return 0;
    }

[https_codeforces.com_contest_69_problem_E]: https://codeforces.com/contest/69/problem/E
[C_ _ _ STL_set]: https://blog.csdn.net/weixin_44668898/article/details/102089892
[C_ _ _ STL_map]: https://blog.csdn.net/weixin_44668898/article/details/102167527