Language: C++

#include <bits/stdc++.h>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define INF 999999999
#define M_PI 3.14159265358979323846
#define ALL(X) (X).begin(),(X).end()

#ifdef __LOCAL
    #define DBG(X) cout << #X << " = " << (X) << endl;
    #define SAY(X) cout << (X) << endl;
#else
    #define DBG(X)
    #define SAY(X)
#endif

#ifdef __LOCAL
    #include <filesystem>
    namespace fs = std::filesystem;
#endif

using namespace std;

using ll = long long int;
using ull = unsigned long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

int dx[]={1, 0, -1, 0, 0};
int dy[]={0, 1, 0, -1, 0};
const int INT_INF = (int)(2e9);
const ll  LL_INF = (ll)(2e18);
const int NIL = -1;
static mt19937 _g(time(nullptr));
 
std::string pad(int num){ char buffer[4]; std::snprintf(buffer, sizeof(buffer), "%03d", num); return buffer;}
inline ll randint(ll a, ll b) { ll w = (_g() << 31LL) ^ _g(); return a + w % (b - a + 1); }
inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); };
template<typename T> inline T sign(T x) { return T(x > 0) - T(x < 0); }
template<typename T, typename S> inline ostream& operator<<(ostream& os, const pair<T, S> p) { cout << "[" << p.first << ";" << p.second << "]"; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) { for (auto el : v) cout << el << " "; return os; }
template<typename T> inline T fetch() { T ret; cin >> ret; return ret; }
template<typename T> inline vector<T> fetch_vec(int sz) { vector<T> ret(sz); for (auto& elem : ret) cin >> elem; return ret; }

template< typename Monoid >
struct SegmentTree {
  using F = function< Monoid(Monoid, Monoid) >;

  int sz;
  vector< Monoid > seg;

  const F f;
  const Monoid M1;

  SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) {
    sz = 1;
    while(sz < n) sz <<= 1;
    seg.assign(2 * sz, M1);
  }

  void set(int k, const Monoid &x) {
    seg[k + sz] = x;
  }

  void build() {
    for(int k = sz - 1; k > 0; k--) {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }

  void update(int k, const Monoid &x) {
    k += sz;
    seg[k] = x;
    while(k >>= 1) {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }

  Monoid query(int a, int b) {
    Monoid L = M1, R = M1;
    for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
      if(a & 1) L = f(L, seg[a++]);
      if(b & 1) R = f(seg[--b], R);
    }
    return f(L, R);
  }

  Monoid operator[](const int &k) const {
    return seg[k + sz];
  }

  template< typename C >
  int find_subtree(int a, const C &check, Monoid &M, bool type) {
    while(a < sz) {
      Monoid nxt = type ? f(seg[2 * a + type], M) : f(M, seg[2 * a + type]);
      if(check(nxt)) a = 2 * a + type;
      else M = nxt, a = 2 * a + 1 - type;
    }
    return a - sz;
  }


  template< typename C >
  int find_first(int a, const C &check) {
    Monoid L = M1;
    if(a <= 0) {
      if(check(f(L, seg[1]))) return find_subtree(1, check, L, false);
      return -1;
    }
    int b = sz;
    for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
      if(a & 1) {
        Monoid nxt = f(L, seg[a]);
        if(check(nxt)) return find_subtree(a, check, L, false);
        L = nxt;
        ++a;
      }
    }
    return -1;
  }

  template< typename C >
  int find_last(int b, const C &check) {
    Monoid R = M1;
    if(b >= sz) {
      if(check(f(seg[1], R))) return find_subtree(1, check, R, true);
      return -1;
    }
    int a = sz;
    for(b += sz; a < b; a >>= 1, b >>= 1) {
      if(b & 1) {
        Monoid nxt = f(seg[--b], R);
        if(check(nxt)) return find_subtree(b, check, R, true);
        R = nxt;
      }
    }
    return -1;
  }
};


int N,K;
vector<int> P;
void input(){
    fast_io();
    #ifdef __LOCAL
        fs::path p = __FILE__;
        fs::path input,output;
        input = output = p.parent_path();
        input += string("/input/") + string(p.stem()) + string(".txt");
        output += string("/output/") + string(p.stem()) + string(".txt");
        freopen(input.c_str(), "r", stdin);
        freopen(output.c_str(), "w", stdout);
    #endif
    cin >> N >> K;
    P = fetch_vec<int>(N);
}

int TLEsolve(){
    if(K==1) {cout << 1 << endl; return 0;}
    if(K==N) {cout << 1 << endl; return 0;}
    // 計算量を考慮せずに愚直にやる場合・・・
    map<vector<int>,int> cnt;
    vector<int> A;
    for (int i = 0; i <= N-K; i++)
    {
        A = P;
        sort(A.begin()+i,A.begin()+i+K);
        DBG(i)
        DBG(A);
        cnt[A]++;
        A.clear();
    }
    for(auto a:cnt) DBG(a.first)
    
    cout << cnt.size() << endl;
    // cout << N-K+1 << endl;
    return 0;
}

int solve(){
    if(K==1) {cout << 1 << endl; return 0;}
    if(K==N) {cout << 1 << endl; return 0;}
    // deque<int> A;
    int ans=1;
    // しゃくとり法的にやる。
    // a1...a'i...a'i+k-1...an-1
    // a1...a'i+1...a'i+k...an-1
    // が同じ列 <==>
    // ai = min(ai,...,ai+k-1) and 
    // ai+k > max(ai,...,ai+k-1)

    // セグ木使えばdequeは要らない。
    // for (int i = 0; i < K; i++)
    // {
    //     A.push_back(P[i]);
    // }
    SegmentTree< int > segMin(N, [](int a, int b) { return min(a, b); }, N+10);
    SegmentTree< int > segMax(N, [](int a, int b) { return max(a, b); }, 0);

    vector<int> ZL;
    int r=0;
    for (int i = 0; i < N-1; i++)
    {
        if(P[i]<P[i+1]) r++;
        // else if(i==N-1) {r++;ZL.push_back(r);r=0;}
        else {r++;ZL.push_back(r);r=0;}
    }
    ZL.push_back(r);
    
    for (int i = 0; i < N; i++)
    {
        segMin.update(i,P[i]);
        segMax.update(i,P[i]);
    }
    
    // max,minのクエリはセグ木を構築して高速化する。
    int mi = segMin.query(0,K-1);
    int ma = segMax.query(0,K-1);
    for (int i = 0; i < N-K; i++)
    {
        // int out = A.front();
        int out = P[i];
        int in = P[i+K];
        // A.pop_front();
        // A.push_back(in);
        if(mi==out && ma<in){ma=in; mi=segMin.query(i+1,i+K);}
        else {ans++; ma=segMax.query(i+1,i+K); mi=segMin.query(i+1,i+K);DBG(i)}
        // else if(mi!=out && ma<in) {ans++;ma=in;}
        // else if(mi==out && ma>=in){ans++;mi=segMin.query(i+1,i+1+K)}
        // else if(mi!=out && ma>=in){ans++;}
    }
    DBG(ZL)
    ans -= max(0,count_if(ZL.begin(),ZL.end(),[](int x){return x>=K;})-1);
    cout << ans << endl;
    return 0;
}

int main()
{
    input();
    // TLEsolve();
    solve();
    return 0;
}


Compiler output:
a.cc: In function 'int solve()':
a.cc:239:15: error: no matching function for call to 'max(int, std::__iterator_traits<__gnu_cxx::__normal_iterator<int*, std::vector<int> >, void>::difference_type)'
  239 |     ans -= max(0,count_if(ZL.begin(),ZL.end(),[](int x){return x>=K;})-1);
      |            ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_algobase.h:257:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  257 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:257:5: note:   template argument deduction/substitution failed:
a.cc:239:15: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'std::__iterator_traits<__gnu_cxx::__normal_iterator<int*, std::vector<int> >, void>::difference_type' {aka 'long int'})
  239 |     ans -= max(0,count_if(ZL.begin(),ZL.end(),[](int x){return x>=K;})-1);
      |            ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:303:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  303 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:303:5: note:   candidate expects 3 arguments, 2 provided
In file included from /usr/include/c++/14/algorithm:61:
/usr/include/c++/14/bits/stl_algo.h:5706:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)'
 5706 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5706:5: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5716:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)'
 5716 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5716:5: note:   template argument deduction/substitution failed:
a.cc:239:15: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  239 |     ans -= max(0,count_if(ZL.begin(),ZL.end(),[](int x){return x>=K;})-1);
      |            ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~