Problem:


Score : 700 points

Problem Statement

Snuke has a permutation (P_0,P_1,\cdots,P_{N-1}) of (0,1,\cdots,N-1).

Now, he will perform the following operation exactly once:

Choose K consecutive elements in P and sort them in ascending order.

Find the number of permutations that can be produced as P after the operation.

Constraints

2 \leq N \leq 200000

2 \leq K \leq N

0 \leq P_i \leq N-1

P_0,P_1,\cdots,P_{N-1} are all different.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
P_0 P_1 \cdots P_{N-1}

Output

Print the number of permutations that can be produced as P after the operation.

Sample Input 1

5 3
0 2 1 4 3

Sample Output 1

2

Two permutations can be produced as P after the operation: (0,1,2,4,3) and (0,2,1,3,4).

Sample Input 2

4 4
0 1 2 3

Sample Output 2

1

Sample Input 3

10 4
2 0 1 3 7 5 4 6 8 9

Sample Output 3

6



Sample input:
5 3
0 2 1 4 3


Sample output:
2

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]

class BIT():#添字は1から始まることに注意
    def __init__(self, max_n):
        self.size = max_n + 1
        self.tree = [0] * self.size
        self.depth = self.size.bit_length()
        
    def initialize(self,seq):
        tree = self.tree
        size = self.size
        for i,x in enumerate(seq,1):
            tree[i] += x
            j = i+(i&(-i))
            if j < size:
                tree[j] += tree[i]
        
    def __repr__(self):
        return self.tree.__repr__()
        
    def get_sum(self,i):
        tree = self.tree
        s = 0
        while i:
            s += tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        tree = self.tree
        size = self.size
        while i < size:
            tree[i] += x
            i += i & -i
    
    def find_kth_element(self,k):#k番目（最小は１）の要素
        tree = self.tree; size = self.size
        x,sx = 0,0
        dx = 1 << (self.depth)
        for i in range(self.depth - 1, -1, -1):
            dx = (1 << i)
            if x + dx >= size:
                continue
            y = x + dx
            sy = sx + tree[y]
            if sy < k:
                x,sx = y,sy
        return x + 1
 
def main():
    mod = 10**9+7
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, K = map(int, input().split())
    Ps = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    bit=BIT(N+1)
    sc=1
    tot=0
    scs=[1]*(N-K+1)
    for p in Ps[:K]:
        bit.add(p+1,1)
    include_sorted=1
    for i in range(N-K):
        if sc==1:
            hantei=1
            for p1, p2 in zip(Ps[i:i+K],sorted(Ps[i:i+K])):
                if p1!=p2:
                    hantei=0
                    break
            if hantei:
                sc=include_sorted
                include_sorted=0
        print(sc)
        tot+=sc
        a=Ps[i]
        b=Ps[i+K]
        if bit.find_kth_element(1)==a+1 and bit.find_kth_element(K)<=b+1:
            sc=0
        else:
            sc=1
        bit.add(a+1,-1)
        bit.add(b+1,1)
    i=N-K
    if sc==1:
        hantei=1
        for p1, p2 in zip(Ps[i:i+K],sorted(Ps[i:i+K])):
            if p1!=p2:
                hantei=0
                break
        if hantei:
            sc=include_sorted
            include_sorted=0
    tot+=sc
    print(tot)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
from bisect import bisect_left
input = sys.stdin.buffer.readline

N, K = map(int, input().split())
Ps = list(map(int, input().split()))

downs = []
for i in range(N-1):
    if Ps[i+1] < Ps[i]:
        downs.append(i)

if not downs:
    print(1)
    exit()

min_wait = deque()
max_wait = deque()
for i in range(K):
    while min_wait and min_wait[-1] > Ps[i]:
        min_wait.pop()
    min_wait.append(Ps[i])
    while max_wait and max_wait[-1] < Ps[i]:
        max_wait.pop()
    max_wait.append(Ps[i])
    
ans = 1
change_nothing = (downs[0] >= K-1)
for i in range(K, N):
    while min_wait and min_wait[-1] > Ps[i]:
        min_wait.pop()
    min_wait.append(Ps[i])
    while max_wait and max_wait[-1] < Ps[i]:
        max_wait.pop()
    max_wait.append(Ps[i])

    if min_wait[0] != Ps[i-K] or max_wait[0] != Ps[i]:
        t = bisect_left(downs, i-K+1)
        if t < len(downs):
            if downs[t] >= i:
                change_nothing = True
            else:
                ans += 1
        else:
            if downs[-1] + K < N:
                change_nothing = True
            break
    
    if min_wait[0] == Ps[i-K]:
        min_wait.popleft()
    if max_wait[0] == Ps[i-K]:
        max_wait.popleft()


if change_nothing:
    ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict, deque

import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def update(self, i, v):
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__op(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def query(self, l, r):
        """[l, r)
        """
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret


@mt
def slv(N, K, P):
    min_st = SegmentTree(P, min, INF)
    max_st = SegmentTree(P, max, -1)


    a = []
    for i in range(N-K):
        min_p = min_st.query(i, i+K+1)
        max_p = max_st.query(i, i+K+1)
        if P[i] == min_p and P[i+K] == max_p:
            a.append((i, i+K))

    j = 0
    ss = []
    for i in range(N-1):
        if P[i] < P[i+1]:
            pass
        else:
            if i - j + 1>= K:
                ss.append((j, i+1))
            j = i + 1
    i += 1
    if i - j +1 >= K:
        ss.append((j, i+1))

    ans = N - K + 1
    if ss:
        ans -= sum(s[1]-s[0] - K + 1 for s in ss) - 1

    ss.reverse()
    for l, r in a:
        while ss and ss[-1][0] > l:
            ss.pop()
        if ss:
            if ss[-1][0] <= l and r < ss[-1][1]:
                pass
            else:
                ans -= 1
        else:
            ans -= 1


    return ans

def ref(N, K, P):
    ans = set()
    for i in range(N-K+1):
        s = tuple(P[:i] + sorted(P[i:i+K]) + P[i+K:])
        ans.add(s)
        print(s, P[:i], sorted(P[i:i+K]), P[i+K:])
    return len(ans)






def main():
    N, K = read_int_n()
    P = read_int_n()
    print(slv(N, K, P))
    # print(ref(N, K, P))



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from collections import defaultdict, deque

import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def update(self, i, v):
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__op(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def query(self, l, r):
        """[l, r)
        """
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret


@mt
def slv(N, K, P):
    min_st = SegmentTree(P, min, INF)
    max_st = SegmentTree(P, max, -1)

    ans = N - K + 1
    a = []
    for i in range(N-K):
        min_p = min_st.query(i, i+K+1)
        max_p = max_st.query(i, i+K+1)
        if P[i] == min_p and P[i+K] == max_p:
            ans -= 1
            # a.append(i, i+K)

    j = 0
    ss = []
    for i in range(N-1):
        if P[i] < P[i+1]:
            pass
        else:
            if i - j + 1>= K:
                ss.append((j, i+1))
            j = i + 1
    i += 1
    if i - j +1 >= K:
        ss.append((j, i+1))
    # ans = N - K + 1
    if ss:
        ans -= sum(s[1]-s[0] - K + 1 for s in ss) - 1

    return ans

def ref(N, K, P):
    ans = set()
    for i in range(N-K+1):
        s = tuple(P[:i] + sorted(P[i:i+K]) + P[i+K:])
        ans.add(s)
        print(s, P[:i], sorted(P[i:i+K]), P[i+K:])
    return len(ans)






def main():
    N, K = read_int_n()
    P = read_int_n()
    print(slv(N, K, P))
    # print(ref(N, K, P))



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
class SegmentTree:
    def __init__(self,l,init):
        nb = bin(len(l))[2:]
        b = sum([int(d) for d in nb])
        if b == 1:
            self.end_leaves = pow(2,len(nb)-1)
        else:
            self.end_leaves = pow(2,len(nb))
        self.tree = [init] * (self.end_leaves*2)
        
        for i in range(len(l)):
            self.tree[self.end_leaves+i] = l[i]
            
    def stmax(self,a):
        if a >= self.end_leaves // 2:
            self.tree[a] = max(self.tree[a*2:a*2+2])
            return self.tree[a]
        else:
            self.tree[a] = max(self.stmax(a*2),self.stmax(a*2+1))
            return self.tree[a]
    def stmin(self,a):
        if a >= self.end_leaves // 2:
            self.tree[a] = min(self.tree[a*2:a*2+2])
            return self.tree[a]
        else:
            self.tree[a] = min(self.stmin(a*2),self.stmin(a*2+1))
            return self.tree[a]
        
    def querymax(self,l,r):
        x = l + self.end_leaves
        y = r + self.end_leaves
        tl = 0
        tr = 0
        while y - x > 1:
            if x % 2 == 1:
                tl = max(tl,self.tree[x])
                x += 1
            if y % 2 == 0:
                tr = max(self.tree[y],tr)
                y -= 1
            x >>= 1
            y >>= 1
        if y - x == 0:
            return max(tl,tr,self.tree[x])
        else:
            return max(tl,tr,self.tree[x],self.tree[y])
    def querymin(self,l,r):
        x = l + self.end_leaves
        y = r + self.end_leaves
        tl = 0
        tr = 0
        while y - x > 1:
            if x % 2 == 1:
                tl = min(tl,self.tree[x])
                x += 1
            if y % 2 == 0:
                tr = min(self.tree[y],tr)
                y -= 1
            x >>= 1
            y >>= 1
        if y - x == 0:
            return min(tl,tr,self.tree[x])
        else:
            return min(tl,tr,self.tree[x],self.tree[y])

from collections import deque

N,K = (int(x) for x in input().split())
P = list(map(int, input().split()))
d = deque(P)
st1 = SegmentTree(P,0)
st1.stmax(1)
st2 = SegmentTree(P,float('inf'))
st2.stmin(1)
combo = 0
mono_increased = False
ans = 0
comp = -1

for i in range(K):
    temp = d.popleft()
    if temp > comp:
        combo += 1
    else:
        combo = 1
    comp = temp

if combo == K:
    mono_increased = True
else:
    ans += 1
d2 = deque(P)

for i in range(2,N-K+2):
    temp = d.popleft()
    if temp > comp:
        if combo < (K-1):
            combo += 1
        elif combo == K-1:
            combo += 1
            mono_increased = True
    else:
        combo = 1
    comp = temp
    t2 = d2.popleft()
    if combo < K:
        if temp < st1.querymax(i,i+K-1):
            ans += 1
        else:
            if t2 > st2.querymin(i,i+K-1):
                ans += 1

if mono_increased == True:
    print(ans+1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

N,K = (int(x) for x in input().split())
P = list(map(int, input().split()))
d = deque(P)
maxd = deque()
maxd_eliminated = 0
mind = deque()
mind_eliminated = 0
combo = 0
mono_increased = False
increased_already = False
ans = 0
comp = -1

for i in range(K):
    temp = d.popleft()
    if temp > comp:
        combo += 1
    else:
        combo = 1
    comp = temp

    if len(maxd) > 0:
        if maxd[0] < temp:
            while True:
                if len(maxd) == 0:
                    break
                elif maxd[0] > temp:
                    break
                else:
                    maxd_eliminated += 1
                    maxd.popleft()
        if mind[0] > temp:
            while True:
                if len(mind) == 0:
                    break
                elif mind[0] < temp:
                    break
                else:
                    mind_eliminated += 1
                    mind.popleft()
        maxd.append(temp)
        mind.append(temp)
        
    else:
        maxd.append(temp)
        mind.append(temp)

if combo == K:
    mono_increased = True
else:
    ans += 1
    increased_already = True

for i in range(N-K):
    temp = d.popleft()
    if temp > comp:
        if combo < (K-1):
            combo += 1
        elif combo == K-1:
            combo += 1
            mono_increased = True
    else:
        combo = 1
        increased_already = False
    comp = temp

    if maxd_eliminated > 0:
        maxd_eliminated -= 1
    else:
        maxd.popleft()
    if mind_eliminated > 0:
        mind_eliminated -= 1
    else:
        mind.popleft()
        m = min(mind)
        while mind[0] > m:
            mind_eliminated += 1
            mind.popleft()
    if maxd[0] < temp:
        while True:
            if len(maxd) == 0:
                break
            elif maxd[0] > temp:
                break
            else:
                maxd_eliminated += 1
                maxd.popleft()
        if mind_eliminated > 0:
            if increased_already == False:
                ans += 1
                increased_already = True
    elif mind[0] > temp:
        while True:
            if len(mind) == 0:
                break
            elif mind[0] < temp:
                break
            else:
                mind_eliminated += 1
                mind.popleft()
        ans += 1
    else:
        ans += 1
    maxd.append(temp)
    mind.append(temp)

if mono_increased == True:
    print(ans+1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

N,K = (int(x) for x in input().split())
P = list(map(int, input().split()))
d = deque(P)
maxd = deque()
eliminated_count = 0
combo = 0
mono_increased = False
increased_already = False
ans = 0
comp = -1

for i in range(K):
    temp = d.popleft()
    if temp > comp:
        combo += 1
    else:
        combo = 1
    comp = temp

    if len(maxd) > 0:
        if maxd[0] < temp:
            while True:
                if len(maxd) == 0:
                    break
                elif maxd[0] > temp:
                    break
                else:
                    eliminated_count += 1
                    maxd.popleft()
        maxd.append(temp)
    else:
        maxd.append(temp)

if combo == K:
    mono_increased = True
else:
    ans += 1
    increased_already = True

for i in range(N-K):
    temp = d.popleft()
    if temp > comp:
        if combo < (K-1):
            combo += 1
        elif combo == K-1:
            combo += 1
            mono_increased = True
    else:
        combo = 1
        increased_already = False
    comp = temp

    if eliminated_count > 0:
        eliminated_count -= 1
    else:
        maxd.popleft()
    if maxd[0] < temp:
        while True:
            if len(maxd) == 0:
                break
            elif maxd[0] > temp:
                break
            else:
                eliminated_count += 1
                maxd.popleft()
        if increased_already == False:
            if combo < K:
                increased_already = True
                ans += 1
    else:
        ans += 1
    maxd.append(temp)

if mono_increased == True:
    print(ans+1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

N,K = (int(x) for x in input().split())
P = list(map(int, input().split()))
d = deque(P)
maxd = deque()
eliminated_count = 0
combo = 0
mono_increased = False
increased_already = False
ans = 0
comp = -1

for i in range(K):
	temp = d.popleft()
	if temp > comp:
		combo += 1
	else:
		combo = 1
	comp = temp
	
	if len(maxd) > 0:
		if maxd[0] < temp:
			while True:
				if len(maxd) == 0:
					break
				elif maxd[0] > temp:
					break
				else:
					eliminated_count += 1
					maxd.popleft()
		maxd.append(temp)
	else:
		maxd.append(temp)
		
if combo == K:
	mono_increased = True
else:
	ans += 1
	increased_already = True

for i in range(N-K):
	temp = d.popleft()
	if temp > comp:
		if combo < (K-1):
			combo += 1
		elif combo == K-1:
			combo += 1
			mono_increased = True
	else:
		combo = 1
		increased_already = False
	comp = temp
	
	if eliminated_count > 0:
		eliminated_count -= 1
	else:
		maxd.popleft()
	if maxd[0] < temp:
		while True:
			if len(maxd) == 0:
				break
			elif maxd[0] > temp:
				break
			else:
				eliminated_count += 1
				maxd.popleft()
		if increased_already == False:
			increased_already = True
			ans += 1
	else:
		ans += 1
	maxd.append(temp)

if mono_increased == True:
	print(ans+1)
else:
	print(ans)

Submission status: Wrong Answer

Solution code:
from operator import add
import sys
input=sys.stdin.readline


class SegTree():
    def __init__(self, N, e, operator_func=add):
        self.e = e # 単位元
        self.size = N
        self.node = [self.e] * (2*N)
        self.operator_func = operator_func # 処理(add or xor max minなど)

    def set_list(self, l):
        for i in range(self.size):
            self.node[i+self.size-1] = l[i]
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.operator_func(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size-1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.operator_func(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        # [l, r) についてqueryを求める
        x = self.e
        l += self.size
        r += self.size

        while l<r:
            if l&1:
                x = self.operator_func(x, self.node[l-1])
                l += 1
            if r&1:
                r -= 1
                x = self.operator_func(x, self.node[r-1])
            l >>= 1
            r >>= 1
        return x


def solve():
    N, K = map(int, input().split())
    *P, = map(int, input().split())
    INF = 10**12

    tree_max = SegTree(N, -INF, operator_func=max)
    tree_max.set_list(P)
    tree_min = SegTree(N, INF, operator_func=min)
    tree_min.set_list(P)
    tree_monoinc = SegTree(N, INF, operator_func=min)
    for i in range(N):
        tree_monoinc.update(i, P[i]-P[i-1] if i else 0)

    def isMonoinc(l, r):
        # [l, r)
        l += 1
        return tree_monoinc.get(l, r)>=0

    ans = N-K+1
    orig = 0

    for i in range(N-K+1):
        if isMonoinc(i, i+K):
            orig = 1
            ans -= 1
        elif i+K<N and tree_max.get(i, i+K+1)==P[i+K] and tree_min.get(i, i+K+1)==P[i]:
            ans -= 1

    ans += orig
    print(ans)

Submission status: Wrong Answer

Solution code:
from operator import add


class SegTree():
    def __init__(self, N, e, operator_func=add):
        self.e = e # 単位元
        self.size = N
        self.node = [self.e] * (2*N)
        self.operator_func = operator_func # 処理(add or xor max minなど)

    def set_list(self, l):
        for i in range(self.size):
            self.node[i+self.size-1] = l[i]
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.operator_func(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size-1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.operator_func(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        # [l, r) についてqueryを求める
        x = self.e
        l += self.size
        r += self.size

        while l<r:
            if l&1:
                x = self.operator_func(x, self.node[l-1])
                l += 1
            if r&1:
                r -= 1
                x = self.operator_func(x, self.node[r-1])
            l >>= 1
            r >>= 1
        return x


class UnionFind(object):
    def __init__(self, n):
        self.parent={i:i for i in range(1,n+1)}
        self.size={i:1 for i in range(1,n+1)}
    def find(self, a):
        if self.parent[a]!=a:
            self.parent[a]=self.find(self.parent[a])
        return self.parent[a]
    def getsize(self, a):
        return self.size[self.find(a)]
    def unite(self, a, b):
        a=self.find(a)
        b=self.find(b)
        if a==b:return
        if self.size[a]>self.size[b]:
            self.size[a]+=self.size[b]
            self.parent[b]=a
        else:
            self.size[b]+=self.size[a]
            self.parent[a]=b
    def isunited(self, a, b):
        return self.find(a)==self.find(b)


N, K = map(int, input().split())
*P, = map(int, input().split())
INF = 10**12

tree_max = SegTree(N, -INF, operator_func=max)
tree_max.set_list(P)
tree_min = SegTree(N, INF, operator_func=min)
tree_min.set_list(P)
tree_monoinc = SegTree(N, INF, operator_func=min)
for i in range(N):
    tree_monoinc.update(i, P[i]-P[i-1] if i else 0)

def isMonoinc(l, r):
    # [l, r)
    l += 1
    return tree_monoinc.get(l, r)>=0

uft = UnionFind(N-K+1)
ans = 0
isOrig = 0

for l in range(N-K+1):
    if isMonoinc(l, l+K):
        ans -= 1
        isOrig = 1
        for r in range(l+1, l+K):
            if not r+K<N: break
            if tree_max.get(l, r) < tree_min.get(r, l+K) < tree_max.get(r, l+K) < tree_min.get(l+K, r+K):
                # print(l, r)
                uft.unite(l+1, r+1)
    else:
        for r in range(l+1, l+2):
            if not r+K<N: break
            # print(l, r, tree_max.get(l, r), tree_min.get(r, l+K), tree_max.get(r, l+K), tree_min.get(l+K, r+K))
            if tree_max.get(l, r) < tree_min.get(r, l+K) < tree_max.get(r, l+K) < tree_min.get(l+K, r+K):
                # print(l, r)
                uft.unite(l+1, r+1)


ans += len({uft.find(i) for i in range(1, N-K+2)}) + isOrig
print(ans)

Submission status: Wrong Answer

Solution code:

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

N, K = map(int,input().split())
P = list(map(int,input().split()))

# 点更新，区間クエリ
class SegTree:
    # n : 元の配列の長さ
    # init_list: 元の配列
    # segfunc : 載せる関数（演算）
    # ide_ele : segfuncの単位元
        
    def __init__(self, n, init_list ,segfunc, ide_ele):
        #　num : 2**num >= n となる最小の整数 （葉の数）
        # seg : segtreeのリスト
        self.num = 2**((n-1).bit_length())
        self.seg = [ide_ele]*(2*self.num)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        # 葉の要素をセット
        for i in range(n):
            self.seg[i+self.num-1] = init_list[i]        
        # segtreeの構築
        for i in range(self.num-2, -1, -1):
            self.seg[i] = segfunc(self.seg[2*i+1],self.seg[2*i+2])
        
        #memo: 要素iの子ノードは要素2*i+1, 2*i+2
        #    : 要素iの親ノードは要素(i-1)//2
        
    # 要素の更新 (init_list[k]=x)
    def update(self,k,x):
        k += self.num-1 #葉のノードのインデックス
        self.seg[k] = x
        #末端から頂点まで更新
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[2*k+1], self.seg[2*k+2])
     
    # 区間クエリ （区間[l,r)に対する演算結果）
    def query(self, l,r):
        if r<=l:
            return self.ide_ele
        
        l += self.num-1 #葉のノードのインデックス
        r += self.num-2 #半開区間から閉区間へ
        ret = self.ide_ele
        
        while r-l>1:
            if l&1 == 0:
                ret = self.segfunc(ret,self.seg[l])
            
            if r&1 == 1:
                ret = self.segfunc(ret,self.seg[r])
                r -= 1
            # 親ノードへ遷移
            l = l//2
            r = (r-1)//2
        if r==l:
            ret = self.segfunc(ret, self.seg[r])
        else:
            ret = self.segfunc(ret, self.seg[l])
            ret = self.segfunc(ret, self.seg[r])
        
        return ret
            
def segfunc(x,y):
    return min(x,y)
INF = 10**9
segtree = SegTree(N, P, segfunc, INF)
from queue import Queue 

zouka = [1]
num = 1
for i in range(N-1):
    if P[i+1]>P[i]:
        num += 1
    else:
        num = 1
    zouka.append(num)


mini = INF
maxi = 0
q = Queue()
for p in P[:K]:
    mini = min(mini, p)
    maxi = max(maxi, p)
    q.put(p)

ans = 1
m = 0
for i in range(1, N-K+1):
    remove = q.get()
    q.put(P[i+K-1])

    if zouka[i+K-1]-zouka[i] == K-1:
        m += 1
        if P[i+K-1]>maxi:
            maxi = P[i+K-1]
        if mini == remove:
            mini = segtree.query(i, i+K-1)
        continue

    if P[i+K-1]>maxi and remove==mini:
        maxi = P[i+K-1]
        mini = segtree.query(i, i+K-1)
    else:
        ans += 1
        if P[i+K-1]>maxi:
            maxi = P[i+K-1]
        if mini == remove:
            mini = segtree.query(i, i+K-1)
if zouka[K-1]-zouka[0] == K-1:
    m += 1


if m<N-K+1 and m>=1:
    ans += 1


print(max(1,ans))