Beta Round #63-E: Subsegments

keyword

尺取り法　C++

問題概要

長さN(<10^5)の数列a(abs(a[i])<10^9)が与えられる。長さK(

解法

尺取り法で部分列における出現回数を記録しておき、ちょうど1回だけ表れている数はsetに突っ込んでおけば最大の数が対数時間で取り出せる。計算量O(N*log N)。
追記：よく考えたら部分列の長さが一定だし尺取り法とはいえないような。

#include <cstdio>
#include <map>
#include <set>
using namespace std;

int N, K;
int as[100009];
set<int> bigs;

void print(){
    if(bigs.empty()) puts("Nothing");
    else printf("%d\n", *bigs.rbegin());
}

void solve(){
    map<int, int> counts;
    for(int i=0; i<K; i++){
        counts[as[i]]++;
        if(counts[as[i]]==1) bigs.insert(as[i]);
        else bigs.erase(as[i]);
    }
    print();
    for(int i=0; i<N-K; i++){
        counts[as[i]]--;
        if(counts[as[i]]==1) bigs.insert(as[i]);
        else bigs.erase(as[i]);
        counts[as[i+K]]++;
        if(counts[as[i+K]]==1) bigs.insert(as[i+K]);
        else bigs.erase(as[i+K]);
        print();
    }
}

int main(){
    scanf("%d%d",&N,&K);
    for(int i=0; i<N; i++){
        scanf("%d",as+i);
    }
    solve();
    return 0;
}