Language: C++

#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#include <iomanip>
#include <complex>
#include <bitset>
#include <stack>
using namespace std;
 
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define repl(i,s,n) for(int i=s; i<=n; ++i)
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define ktya(x) sort(all(x))
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 1e18
#define INFLL 1000000000000000007LL
#define SIZE 200105
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define mind(a,b) (a>b?b:a)
#define maxd(a,b) (a>b?a:b)
#define PI (acos(-1))
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
typedef pair<int,ll> pill; typedef pair<ll,int> plli; 
typedef pair<double, int> pdi;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
typedef complex<double> P;
//ll MOD = 1000000007;
ll MOD=998244353;
typedef ll Weight;
struct Edge {
	int src, dst;
	Weight weight;
};
bool operator < (const Edge &e, const Edge &f) {
	return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
	e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
int N,K;
vi hoge;
const int BT = 1 << 17 ;
struct segtree {//BT = size,2べき, 初期化忘れずに
	vector<int> seg;
	
	void init() {
		seg.resize(BT * 2);
		rep(i, BT * 2 - 1) seg[i] = INT_MIN;
	}
	
	void add(int pos, int x) {//posにxを追加,0-index nodeも0-index
		pos += BT - 1;
		seg[pos] = x;
	
		while (pos > 0) {
			pos = (pos - 1) / 2;
			seg[pos] = max(seg[pos * 2 + 1], seg[pos * 2 + 2]);
		}
	}

	int maxQ(int a, int b, int k = 0, int l = 0, int r = BT) {//[a,b)に対するクエリ
		if (b <= l || r <= a) return INT_MIN;//交差しない
		if (a <= l && r <= b) return seg[k];//被覆する
		return max(maxQ(a, b, k * 2 + 1, l, (l + r) / 2), maxQ(a, b, k * 2 + 2, (l + r) / 2, r));
	}

}segm; 

int pre[214514]={0},suf[214514]={0};//pre = prefix-i suf=suffix
int main(){
	cin>>N>>K;
	vi fuga;
	rep(i,N){
		int x;
		cin>>x;
		hoge.pb(x);
		if(i<K)fuga.pb(x);
	}
	segm.init();
	sort(all(fuga));
	bool incflag=false;
	int memo1=0,memo2=0;
	rep(i,K){
		if(fuga[i]==hoge[i])memo1=i+1;
		else break;
	}
	rep(i,K){
		if(fuga[K-1-i]==hoge[K-1-i])memo2=i+1;
		else break;
	}
	pre[0]=memo1;
	suf[0]=memo2;
	int ans=1;
	
	for(int i=0;i<=N-K;i++){
		if(i==0||pre[i-1]<=1){
			vi piyo;
			rep(j,K){
				piyo.pb(hoge[i+j]);
			}
			sort(all(piyo));
			int memo=0;
			rep(j,K){
				if(piyo[j]==hoge[i+j])memo=j+1;
				else break;
			}
			pre[i]=memo;
		}else{
			int nex=hoge[i+K-1];
			if(nex>hoge[i-1+pre[i-1]-1])pre[i]=pre[i-1]-1;
			else if(nex<hoge[i]){
				i=i+K-2;
				pre[i]=0;
			}else{
				int lef=i,rig=i+pre[i-1]-2;
				while(rig-lef>1){
					int mid=(rig+lef)/2;
					if(hoge[mid]>nex) rig=mid;
					else lef=mid;
				}
				pre[i]=lef-i+1;
			}
			
		}
	}
	reverse(all(hoge));
	for(int i=0;i<=N-K;i++){
		if(i==0||suf[i-1]<=1){
			vi piyo;
			rep(j,K){
				piyo.pb(hoge[i+j]);
			}
			sort(all(piyo));
			reverse(all(piyo));
			int memo=0;
			rep(j,K){
				if(piyo[j]==hoge[i+j])memo=j+1;
				else break;
			}
			suf[i]=memo;
		}else{
			int nex=hoge[i+K-1];
			if(nex<hoge[i-1+suf[i-1]-1])suf[i]=suf[i-1]-1;
			else if(nex>hoge[i]){
				i=i+K-2;
				suf[i]=0;
			}else{
				int lef=i,rig=i+suf[i-1]-2;
				while(rig-lef>1){
					int mid=(rig+lef)/2;
					if(hoge[mid]<nex) rig=mid;
					else lef=mid;
				}
				suf[i]=lef-i+1;
			}
			
		}
	}
	int suf2[214514];
	rep(i,N-K+1){
		pre[i]=pre[i]+i;
		suf2[i]=suf[N-K-i];
		//cout<<pre[i]<<" "<<suf2[i]<<endl;
	}
	rep(i,N-K+1){
		if(i>0){
			int b=suf2[i];
			int ma=segm.maxQ(max(0,i-b),i);
			if(ma<i){
				if(pre[i]!=K+i||!incflag){
					ans++;
				}
			}
			
		}
		segm.add(i,pre[i]);
		if(pre[i]==K+i)incflag=true;
		//cout<<ans<<endl;
	}
	cout<<ans<<endl;
}


Compiler output:
a.cc: In member function 'void segtree::init()':
a.cc:76:45: error: 'INT_MIN' was not declared in this scope
   76 |                 rep(i, BT * 2 - 1) seg[i] = INT_MIN;
      |                                             ^~~~~~~
a.cc:22:1: note: 'INT_MIN' is defined in header '<climits>'; this is probably fixable by adding '#include <climits>'
   21 | #include <stack>
  +++ |+#include <climits>
   22 | using namespace std;
a.cc: In member function 'int segtree::maxQ(int, int, int, int, int)':
a.cc:90:46: error: 'INT_MIN' was not declared in this scope
   90 |                 if (b <= l || r <= a) return INT_MIN;//交差しない
      |                                              ^~~~~~~
a.cc:90:46: note: 'INT_MIN' is defined in header '<climits>'; this is probably fixable by adding '#include <climits>'