[STL] Codeforces 69E Subsegments

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 - 1that occur in this subarray exactly 1 time. If there are no such numbers in this subarray, print "Nothing".

Examples

input

Copy

output

Copy

1
3
2

input

Copy

output

Copy

4
Nothing
3

题意：给一个长度为n的数字，输出i从1到n-k-1,i到i+k-1这个区间内若存在只出现一次的区间最大值则输出这个值，否则输出Nothing

思路：先把前k个数排序并找出只出现一次的那些数，就可以的到第一次询问的答案，
然后从k+1开始，每加入一个数就删去上一个区间的第一个数，并看删去的那个数的个数
是否为1，若为1则加入可行集合，否则就看它是否在可行集合中(因为刚才删了一次，若它在可行集合中那么它的数量就为0了，要把它给删了)
若在就删了它。再看新加进来的那个数的个数是否为1，如果是就加入可行集合，否则就看它是否在可行集合中(如果它在可行集合中，那么它现在的数量为1，现在又加了一次它，它的个数就大于1，不符合条件了），若在就把它给删了
每次输出可行集合中最大的那个数

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int amn=1e5+5;
 4 int a[amn];
 5 map<int,int> mp;    ///个数统计，a[i]最大是1e9，故用map统计
 6 set<int> s; ///可行集合
 7 int main(){
 8     int n,k;
 9     ios::sync_with_stdio(0);
10     cin>>n>>k;
11     for(int i=1;i<=n;i++){
12         cin>>a[i];
13         if(i<=k){
14             mp[a[i]]++;
15             if(mp[a[i]]==1){
16                 s.insert(a[i]);
17             }
18             else{
19                 if(s.find(a[i])!=s.end()){
20                     s.erase(a[i]);
21                 }
22             }
23             if(i==k){
24                 if(s.empty())printf("Nothing\n");
25                 else{
26                     printf("%d\n",*(--s.end()));    ///set升序排序，输出最后一个
27                 }
28             }
29         }
30         else{
31             mp[a[i]]++;
32             mp[a[i-k]]--;
33             if(mp[a[i-k]]==1)s.insert(a[i-k]);
34             else{                               ///可能为0了，如果这个数在可行集合中就要把它删掉
35                 if(s.find(a[i-k])!=s.end()){
36                     s.erase(a[i-k]);
37                 }
38             }
39             if(mp[a[i]]==1)s.insert(a[i]);
40             else{
41                 if(s.find(a[i])!=s.end()){
42                     s.erase(a[i]);
43                 }
44             }
45             if(s.empty())printf("Nothing\n");
46             else{
47                  printf("%d\n",*(--s.end()));
48             }
49         }
50     }
51 }
52 /***
53 先把前k个数排序并找出只出现一次的那些数，就可以的到第一次询问的答案，
54 然后从k+1开始，每加入一个数就删去上一个区间的第一个数，并看删去的那个数的个数
55 是否为1，若为1则加入可行集合，否则就看它是否在可行集合中(因为刚才删了一次，若它在可行集合中那么它的数量就为0了，要把它给删了)
56 若在就删了它。再看新加进来的那个数的个数是否为1，如果是就加入可行集合，否则就看它是否在可行集合中(如果它在可行集合中，那么它现在的数量为1，现在又加了一次它，它的个数就大于1，不符合条件了），若在就把它给删了
57 每次输出可行集合中最大的那个数
58 ***/

全部评论

推荐最新楼层

03-23 15:56

已编辑

门头沟学院研发工程师

3-23 腾讯面经 QQ部门（一面挂）

🕐面试时间：45min💻面试岗位：后台开发❓面试问题：拷打实习为什么不继续在那家公司继续干了（全力备战秋招）拷打项目（rag可不可以搞成多标签处理，怎么实现，上传知识库的流程可不可以简化一下，方便非技术人员操作，react是怎么实现的，哪些是循环，循环过程是怎样）你用cursor开发过项目，平常是怎么开发的String s = new String("abc")会创建几个对象java的泛型擦除是什么（这个第一次听说）实习时间安排，如果装正了能实习到多久，如果不考虑秋招能实习到多久（不考虑秋招？？）算法题 将类似aaabbcc的字符串转成a3b2c2，很简单，可以在本地i...

发面经攒人品

点赞评论收藏

03-25 17:41

长春电子科技学院前端工程师

27届大三下, 想去找实习比较迷茫,不知道该怎么准备,求大佬们指点一下~

有很多问题,求大佬们解答,谢谢大佬们:不知道现在该怎么投实习,该怎么准备内心很纠结学校课程和实习到底怎么选择, 自己也不想课程学业这边出问题, 是不是只能投暑期实习,具体时间该怎么安排前端面试也需要准备算法么, 自己的算法能力很薄弱, 面试题需要准备到什么程度?没有ai项目经验的话,我该如何去补充,如何去找好的ai项目

smile丶snow：1.简历尽量一页，比如教育经历那里，全日制，计算机学院这些可以去掉没啥用好浪费空间。熟悉三件套就没必要写了吧。js基本上是这样写 * JavaScript核心:深入理解 JS 运行机制(事件循环 Event Loop、微任务/宏任务),熟练掌握 Promise/Async 异步编程模型。熟悉可以改成熟练掌握。组件库写一个ant感觉就行，多写了浪费空间。旅游项目是不是jonas的natours啊，我之前简历也有这个。我之前是这样写的全栈思维: 熟悉 Node.js/Express 后端架构，掌握 MongoDB 数据库设计与聚合查询工程化我觉得还是少些吧，不写就问的少，如果你真的了解的话可以写。 1.实习的话推荐大厂官网和aoob上面投，我自己有写一个校招网站的小网站可以直达～github主页上面有，顺便求个关注（ 2.大三下一般课程比较少了吧，如果学校比较严的话可以多沉淀一会，如果不太严可以请dai课然后去实习，尽量找个近一些的就行。暑期实习不是暑假才实习哦，基本是上3月底4月初发offer就可以过去了，然后大概暑假的时候走转正流程答辩。 3.大厂算法题+js手写体。hot100+常见的比如数组转树，Promise.all,deepClone,之类 js手写都不难其实。算法看自己能力吧，我其实算法能力也不行。 4.自己平时没有用AI Coding吗？自己想一下怎么让AI帮你更好的写代码～比如Skill的诞生，OpenSpec的诞生，不都是我们想让AI更好帮我们写代码吗。

我的实习日记

点赞评论收藏