BOJ 2433 - The Sound of Silence

BOJ 2433 - The Sound of Silence

단순히 구간의 최대값과 최소값을 슬라이딩 윈도우로 관리하는 문제이다.

Sparse Table을 이용해도, 덱으로 슬라이딩 윈도우를 해도, 세그먼트 트리를 이용해도 된다.

void solve() {
   int n, m, c;
   cin >> n >> m >> c;
   vi a(n);
   fv(a);
   deque<int> mx, mn;

   vi ans;
   for (int i = 0; i < m; i++) {
      while (sz(mx) && a[mx.back()] < a[i])mx.pop_back();
      while (sz(mn) && a[mn.back()] > a[i])mn.pop_back();

      mx.push_back(i);
      mn.push_back(i);
   }
   if (a[mx[0]] - a[mn[0]] <= c) ans.pb(0);

   for (int i = 1; i + m - 1 < n; i++) {
      while (sz(mx) && mx.front() < i) mx.pop_front();
      while (sz(mn) && mn.front() < i) mn.pop_front();
      while (sz(mx) && a[mx.back()] < a[i + m - 1])mx.pop_back();
      while (sz(mn) && a[mn.back()] > a[i + m - 1])mn.pop_back();
      mx.pb(i + m - 1);
      mn.pb(i + m - 1);
      if (a[mx[0]] - a[mn[0]] <= c) ans.pb(i);
   }

   if (sz(ans) == 0) cout << "NONE";
   else for (int i: ans) cout << i + 1 << endl;
}