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: Accepted

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 = list(map(int, input().split()))
    tree = SegTree(N, 10**12, min)
    tree_min = SegTree(N, 10**12, min)
    tree_max = SegTree(N, -10**12, max)
    tree_min.set_list(P)
    tree_max.set_list(P)
    tree.set_list([P[i]-P[i-1] if i else P[i] for i in range(N)])

    f = lambda l,r:tree.get(l+1, r)>=0

    ans = N-K+1
    isOrig = 0
    for i in range(N-K):
        if f(i, i+K):
            ans -= 1
            isOrig = 1
        elif tree_min.get(i, i+1+K)==P[i] and tree_max.get(i, i+1+K)==P[i+K]:
            ans -= 1
    if f(N-K, N):
        ans -= 1
        isOrig = 1
    ans += isOrig
    print(ans)


solve()

Submission status: Accepted

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


N, K = map(int, input().split())
P = list(map(int, input().split()))
tree = SegTree(N, 10**12, min)
tree_min = SegTree(N, 10**12, min)
tree_max = SegTree(N, -10**12, max)
tree_min.set_list(P)
tree_max.set_list(P)

for i in range(N):
    tree.update(i, P[i]-P[i-1] if i else P[i])

f = lambda l,r:tree.get(l+1, r)>=0

ans = N-K+1
isOrig = 0
for i in range(N-K):
    if f(i, i+K):
        ans -= 1
        isOrig = 1
    elif tree_min.get(i, i+1+K)==P[i] and tree_max.get(i, i+1+K)==P[i+K]:
        ans -= 1
if f(N-K, N):
    ans -= 1
    isOrig = 1
ans += isOrig
print(ans)

Submission status: Accepted

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
    j=0
    cur=Ps[0]
    flag=1
    cur=Ps[0]
    it=0
    for i,p in enumerate(Ps[:K]):
        if cur>p:
            it=i
        bit.add(p+1,1)
        cur=p
    
    count=0
    if it ==0:
        count=1

    for i in range(N-K+1):
        j=i+K-1

        tot+=sc
        if i==N-K:
            break
        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)

        j=i+K
        if Ps[j-1]>Ps[j]:
            it=j
        elif j-it+1>=K:
            #print(it,j)
            if count>0:
                sc=0
            else:
                count=1
        cur=Ps[j]
    print(tot)


if __name__ == "__main__":
    main()

Submission status: Accepted

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])
    
change_nothing = (downs[0] >= K-1)
if change_nothing:
    ans = 0
else:
    ans = 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: Accepted

Solution code:
# -*- coding: utf-8 -*-
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][1] <= 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 main():
    N, K = read_int_n()
    P = read_int_n()
    print(slv(N, K, P))


if __name__ == '__main__':
    main()

Submission status: Accepted

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][1] <= 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))


    # from random import randint, shuffle
    # while True:
    #     N = 100
    #     K = randint(1, N-1)
    #     P = list(range(1, N+1))
    #     shuffle(P)
    #     a = slv(N, K, P[:])
    #     b = ref(N, K, P[:])
    #     if a != b:
    #         print(N, K)
    #         print(P)
    #         print(a, b)
    #         break



if __name__ == '__main__':
    main()

Submission status: Accepted

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 = float('inf')
        tr = float('inf')
        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(1,N-K+1):
    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: Accepted

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)


if __name__ == "__main__":
    solve()

Submission status: Accepted

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


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: Accepted

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)
def segfunc2(x,y):
    return max(x,y)

INF = 10**9
segtree = SegTree(N, P, segfunc, INF)
segtree_max = SegTree(N, P, segfunc2, 0)
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

if zouka[K-1]-zouka[0] == K-1:
    m += 1
    ans = 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
    elif P[i+K-1]>maxi and remove==mini:
        None
    else:
        ans += 1
    maxi = segtree_max.query(i, i+K)
    mini = segtree.query(i, i+K)


if m>=1:
    ans += 1

print(max(1,ans))

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
p=list(map(int,input().split()))

#スライド最小値、スライド最大値
from collections import deque
def slide_max_index(a, K):
    # max_idx[i]: 区間 [i - K + 1, i] (両側閉区間)における a の最大値を与えるインデックス
    N = len(a)
    max_idx = [0] * N # (長さKに満たない左側領域もついでに計算する)
    deq = deque() # デック．番長順番待ちキューをシミュレートする．インデックスを格納しておく
    for i in range(0,N):
        while len(deq) > 0 and deq[0] <= i - K : deq.popleft() # 卒業する
        while len(deq) > 0 and a[deq[-1]] < a[i] : deq.pop()   # a[i] の入学で 望みがなくなった先輩達が脱落する
        deq.append(i)                                          # 新入生i は常に番長になる望みがある
        max_idx[i] = deq[0]                                    # 番長順番待ちキューの最左が番長
    return max_idx
def slide_min_index(a, K):
    # max_idx[i]: 区間 [i - K + 1, i] (両側閉区間)における a の最大値を与えるインデックス
    N = len(a)
    min_idx = [0] * N # (長さKに満たない左側領域もついでに計算する)
    deq = deque() # デック．番長順番待ちキューをシミュレートする．インデックスを格納しておく
    for i in range(0,N):
        while len(deq) > 0 and deq[0] <= i - K : deq.popleft() # 卒業する
        while len(deq) > 0 and a[deq[-1]] > a[i] : deq.pop()   # a[i] の入学で 望みがなくなった先輩達が脱落する
        deq.append(i)                                          # 新入生i は常に番長になる望みがある
        min_idx[i] = deq[0]                                    # 番長順番待ちキューの最左が番長
    return min_idx

min_idx=slide_min_index(p,k+1)
max_idx=slide_max_index(p,k+1)
eq=list(range(n-k+1))
for i in range(n-(k+1)+1):
  if i==min_idx[i+k] and i+k==max_idx[i+k]:
    eq[i+1]=eq[i]

pre=p[0]
a=[0]
c=0
for pi in p[1:]:
  if pre<pi:
    c+=1
  else:
    c=0
  pre=pi
  a.append(c)
eqi=-1
for i in range(n-k+1):
  if a[i+k-1]>=k-1:
    if eqi==-1:
      eqi=i
    else:
      eq[i]=eqi

print(len(set(eq)))
#print(eq)
#print(a)

Submission status: Accepted

Solution code:
def make_tree(n):
    i = 2
    while True:
        if i >= n * 2:
            tree1 = [inf] * i
            tree2 = [0] * i
            break
        else:
            i *= 2
    return tree1, tree2

def update(i, x):
    j = len(tree1) // 2 + i
    tree1[j] = x
    j //= 2
    while True:
        if j == 0:
            break
        tree1[j] = min(tree1[2 * j], tree1[2 * j + 1])
        j //= 2
    j = len(tree2) // 2 + i
    tree2[j] = x
    j //= 2
    while True:
        if j == 0:
            break
        tree2[j] = max(tree2[2 * j], tree2[2 * j + 1])
        j //= 2
    return

def find(x, y):
    s = len(tree1) // 2 + x
    t = len(tree1) // 2 + y
    ans1 = inf
    while True:
        if s > t:
            break
        if s % 2 == 0:
            s //= 2
        else:
            ans1 = min(ans1, tree1[s])
            s = (s + 1) // 2
        if t % 2 == 1:
            t //= 2
        else:
            ans1 = min(ans1, tree1[t])
            t = (t - 1) // 2
    s = len(tree2) // 2 + x
    t = len(tree2) // 2 + y
    ans2 = 0
    while True:
        if s > t:
            break
        if s % 2 == 0:
            s //= 2
        else:
            ans2 = max(ans2, tree2[s])
            s = (s + 1) // 2
        if t % 2 == 1:
            t //= 2
        else:
            ans2 = max(ans2, tree2[t])
            t = (t - 1) // 2
    return ans1, ans2

n, k = map(int, input().split())
p = list(map(int, input().split()))
ans = n - k + 1
s = [1] * n
for i in range(1, n):
    if p[i] > p[i - 1]:
        s[i] = s[i - 1] + 1
ans -= max(s.count(k) - 1, 0)
inf = pow(10, 7)
tree1, tree2 = make_tree(n)
for i in range(n):
    update(i, p[i])
for i in range(n - k):
    a, b = find(i, i + k)
    if a == p[i] and b == p[i + k]:
        ans -= 1
print(ans)