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:
import heapq


def main():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))
    ans = 1
    inside_que = [0] * N
    min_que, max_que = [], []
    for i in range(K):
        heapq.heappush(min_que, P[i])
        heapq.heappush(max_que, - P[i])
        inside_que[P[i]] = 1
    for i in range(N - K):
        old_p, new_p = P[i], P[i + K]
        if not(old_p == min_que[0] and new_p >= - max_que[0]):
            ans += 1
        inside_que[old_p] = 0
        inside_que[new_p] = 1
        heapq.heappush(min_que, new_p)
        heapq.heappush(max_que, - new_p)
        while inside_que[min_que[0]] == 0:
            heapq.heappop(min_que)
        while inside_que[-max_que[0]] == 0:
            heapq.heappop(max_que)
    desc_index = 0
    exists_asc_section = False
    for i in range(1, N):
        if P[i - 1] > P[i]:
            if i - desc_index >= K:
                ans -= 1
                exists_asc_section = True
            desc_index = i
    if N - desc_index >= K:
        exists_asc_section = True
        ans -= 1
    if exists_asc_section:
        ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(N)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """

    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, left, right):
        """
        [left, right)のsegfuncしたものを得る
        left: index(0-index)
        right: index(0-index)
        """
        res = self.ide_ele
        left += self.num
        right += self.num
        while left < right:
            if left & 1:
                res = self.segfunc(res, self.tree[left])
                left += 1
            if right & 1:
                res = self.segfunc(res, self.tree[right - 1])
            left >>= 1
            right >>= 1
        return res


def resolve():
    n, k = map(int, input().split())
    P = list(map(int, input().split()))

    seg_min = SegTree(P, lambda x, y: min(x, y), f_inf)
    seg_max = SegTree(P, lambda x, y: max(x, y), -f_inf)
    mi = seg_min.query(0, k)
    ma = seg_max.query(0, k)
    res = {(0, k - 1)}
    for i in range(1, n - k + 1):
        prev = P[i - 1]
        new = P[i + k - 1]
        if prev != mi or new < ma:
            res.add((i, i + k - 1))
        mi = seg_min.query(i, i + k)
        ma = seg_max.query(i, i + k)

    ascending = []
    head = 0
    foot = 1
    cnt = 1
    for i in range(1, n):
        if P[i - 1] < P[i]:
            cnt += 1
            foot = i
        else:
            cnt = 1
            head = i
        if cnt == k:
            ascending.append((head, foot))
            head = i
            cnt -= 1

    ans = len(res)
    flg = False
    for section in ascending:
        if section in res:
            if not flg:
                flg = True
            else:
                ans -= 1
    print(ans)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
class SegmentTree:

    def __init__(self, n, op, e):
        """
        :param n: 要素数
        :param op: 二項演算
        :param e: 単位減
        """
        self.n = n
        self.op = op
        self.e = e
        self.size = 1 << (self.n - 1).bit_length()      # st[self.size + i] = array[i]
        self.tree = [self.e] * (self.size << 1)

    def built(self, array):
        """arrayを初期値とするセグメント木を構築"""
        for i in range(self.n):
            self.tree[self.size + i] = array[i]
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.op(self.tree[i<<1], self.tree[(i<<1)|1])

    def update(self, i, x):
        """i 番目の要素を x に更新　(0-indexed) """
        i += self.size
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.op(self.tree[i<<1], self.tree[(i<<1)|1])

    def get(self, l, r):
        """ [l, r)の区間取得の結果を返す　(0-indexed) """
        l += self.size
        r += self.size
        res_l = self.e
        res_r = self.e
        while l < r:
            if l & 1:
                res_l = self.op(res_l, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                res_r = self.op(self.tree[r], res_r)
            l >>= 1
            r >>= 1
        return self.op(res_l, res_r)

    def __iter__(self):
        for a in self.tree[self.size:self.size+self.n]:
            yield a

    def __str__(self):
        return str(self.tree[self.size:self.size+self.n])

##################################################################################################################
import sys
input = sys.stdin.readline


N, K = map(int, input().split())
P = list(map(int, input().split()))
e = float("inf")
op = lambda x, y : x if x < y else y
st1 = SegmentTree(N, op, e)
st1.built(P)
e = 0
op = lambda x, y : x if x > y else y
st2 = SegmentTree(N, op, e)
st2.built(P)

Q = [1]
for i in range(N-1):
    if P[i] < P[i+1]:
        Q.append(Q[-1]+1)
    else:
        Q.append(1)

res, flg = 1, 0
if Q[K-1]>=K:
    flg = 1
for i in range(1,N-K+1):
    mi, ma = st1.get(i,i+K-1), st2.get(i,i+K-1)
    if (P[i+K-1] < ma or P[i-1] > mi):
        if Q[i+K-1]<K:
            res += 1
        elif not flg:
            res += 1
            flg = 1
print(res)

Submission status: Accepted

Solution code:
class SegmentTree:
    """
    演算子は要素とセットでモノイドを形成するようなものでなければならない。
    すなわち、結合律が成り立ち単位元が存在する必要がある。(ただし単位元は添加可能)
    """
    @classmethod
    def all_identity(cls, operator, identity, size):
        return cls(operator, identity, [identity]*(2 << (size-1).bit_length()))

    @classmethod
    def from_initial_data(cls, operator, identity, data):
        size = 1 << (len(data)-1).bit_length()
        temp = [identity]*(2*size)
        temp[size:size+len(data)] = data
        data = temp

        for i in reversed(range(size)):
            data[i] = operator(data[2*i],data[2*i+1])
        return cls(operator, identity, data)

    # これ使わずファクトリーメソッド使いましょうね
    def __init__(self, operator, identity, data):
        self.op = operator
        self.id = identity
        self.data = data
        self.size = len(data)//2

    def _interval(self, a, b):
        a += self.size
        b += self.size
        ra = self.id
        rb = self.id

        data = self.data
        op = self.op
        while a < b:
            if a & 1:
                ra = op(ra,data[a])
                a += 1
            if b & 1:
                b -= 1
                rb = op(data[b],rb)
            a >>= 1
            b >>= 1
        return op(ra,rb)

    def __getitem__(self, i):
        if isinstance(i, slice):
            return self._interval(
                                    0 if i.start is None else i.start,
                                    self.size if i.stop is None else i.stop)
        elif isinstance(i, int):
            return self.data[i+self.size]

    def __setitem__(self, i, v):
        i += self.size
        data = self.data
        op = self.op
        while i:
            data[i] = v
            v = op(data[i^1],v) if i & 1 else op(v,data[i^1])
            i >>= 1

    def __iter__(self):
        return iter(self.data[self.size:])

max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

def solve(K,P):
    N = len(P)
    maxseg = SegmentTree.from_initial_data(max2, -1, P)
    minseg = SegmentTree.from_initial_data(min2, N, P)

    delta = [b-a for a,b in zip(P,P[1:])]
    deltaseg = SegmentTree.from_initial_data(min2, N, delta)

    c = 1
    sorted_ever_counted = deltaseg[:K-1] > 0
    for i in range(N-K):
        a = maxseg[i+1:i+K]
        b = minseg[i+1:i+K]
        is_sorted = deltaseg[i+1:i+K] > 0

        if b < P[i] or a > P[i+K]:
            if is_sorted:
                c += int(not sorted_ever_counted)
                sorted_ever_counted = True
            else:
                c += 1

    return c

if __name__ == '__main__':
    N,K = map(int,input().split())
    P = list(map(int,input().split()))
    print(solve(K,P))

Submission status: Accepted

Solution code:
import math
import numpy as np
import decimal
import collections
import itertools
import sys
#Union-Find
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
def unite(x, y):
    p = find(x)
    q = find(y)
    if p == q:
        return None
    if p > q:
        p,q = q,p
    par[p] += par[q]
    par[q] = p
def same(x, y):
    return find(x) == find(y)
def size(x):
    return -par[find(x)]
n = 0
par = [-1 for i in range(n)]

#素数関連
def prime_numbers(x):
    if x < 2:
        return []
    prime_numbers = [i for i in range(x)]
    prime_numbers[1] = 0
    for prime_number in prime_numbers:
        if prime_number > math.sqrt(x):
            break
        if prime_number == 0:
            continue
        for composite_number in range(2 * prime_number, x, prime_number):
            prime_numbers[composite_number] = 0
    return [prime_number for prime_number in prime_numbers if prime_number != 0]
def is_prime(x):
    if x < 2:
        return False
    if x == 2 or x == 3 or x == 5:
        return True
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0:
        return False
    prime_number = 7
    difference = 4
    while prime_number <= math.sqrt(x):
        if x % prime_number == 0:
            return False
        prime_number += difference
        difference = 6 - difference
    return True
#nCr
mod = 10 ** 9 + 7
def comb(n, r):
    if n < r:return 0
    if n < 0 or r < 0:return 0
    return fa[n] * fi[r] % mod * fi[n - r] % mod
fa = [1] * (n + 1)
fi = [1] * (n + 1)
for i in range(1, n + 1):
    fa[i] = fa[i - 1] * i % mod
    fi[i] = pow(fa[i], mod - 2, mod)
#BIT
BIT = [0] * (n + 1)
def add(i, x):
    while i <= n:
        BIT[i] += x
        i += i & -i
def query(i):
    s = 0
    while i > 0:
        s += BIT[i]
        i -= i & -i
from collections import deque
n, k = map(int, input().split())
p = list(map(int, input().split()))
cnt = 0
li = [1 for i in range(n - k + 1)]
for i in range(1, k):
    if p[i - 1] > p[i]:
        cnt += 1
if cnt == 0:
    li[0] = 0
for i in range(k, n):
    if p[i - 1] > p[i]:
        cnt += 1
    if p[i - k] > p[i - k + 1]:
        cnt -= 1
    if cnt == 0:
        li[i - k + 1] = 0
Q1 = deque([])
Q2 = deque([])
L1 = [0 for i in range(n - k + 2)]
L2 = [0 for i in range(n - k + 2)]
for i in range(n):
    while Q1 and p[Q1[-1]] > p[i]:
        Q1.pop()
    while Q2 and p[Q2[-1]] < p[i]:
        Q2.pop()
    Q1.append(i)
    Q2.append(i)
    if Q1[0] == i - k + 1:
        Q1.popleft()
    if Q2[0] == i - k + 1:
        Q2.popleft()
    if i >= k - 2:
        L1[i - k + 2] = p[Q1[0]]
        L2[i - k + 2] = p[Q2[0]]
ans = 0
for i in range(1, n - k + 1):
    if p[i - 1] > L1[i] or p[i + k - 1] < L2[i]:
        if li[i] > 0:
            ans += 1
print(ans - min(li) + li[0] + 1)

Submission status: Accepted

Solution code:
import sys
from heapq import *
input = sys.stdin.readline


def solve(n, k, p):
    res = n-k+1
    count = 0
    length = 1
    
    judge_max = [-x for x in p[:k]]
    judge_min = p[:k]
    heapify(judge_max)
    heapify(judge_min)
    already = [False]*n
    
    for i in range(k-1):
        if p[i] < p[i+1]:
            length += 1
        else:
            length = 1
            
    if length == k:
        count += 1
    
    for i in range(k-1, n-1):
        if p[i] < p[i+1]:
            length += 1
        else:
            length = 1
        
        already[p[i-k+1]] = True
        while True:
            vmax = -judge_max[0]
            if already[vmax]:
                heappop(judge_max)
                continue
            else:
                break
        while True:
            vmin = judge_min[0]
            if already[vmin]:
                heappop(judge_min)
                continue
            else:
                break
        if p[i-k+1] < vmin and vmax < p[i+1]:
            res -= 1
        
        elif length >= k:
            if count:
                res -= 1
            count += 1
        heappush(judge_max, -p[i+1])
        heappush(judge_min, p[i+1])
    
    return res

    
def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    
    ans = solve(n, k, p)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    from collections import deque
    N, K = map(int, readline().split())
    P = list(map(int, readline().split()))

    if N == K:
        return print(1)

    p_min = [0] * (N - K)
    p_max = [0] * (N - K)
    p_asc = [0] * (N - K + 1)

    def calc_min():
        que = deque()
        que.append(P[0])

        for i in range(1, K + 1):
            cur = P[i]
            while que and cur < que[-1]:
                que.pop()
            que.append(cur)
        p_min[0] = que[0]

        for i in range(N - K - 1):
            prev = P[i]
            cur = P[i + K + 1]
            if que[0] == prev:
                que.popleft()
            while que and cur < que[-1]:
                que.pop()
            que.append(cur)
            p_min[i + 1] = que[0]

    def calc_max():
        que = deque()
        que.append(P[0])

        for i in range(1, K + 1):
            cur = P[i]
            while que and cur > que[-1]:
                que.pop()
            que.append(cur)
        p_max[0] = que[0]

        for i in range(N - K - 1):
            prev = P[i]
            cur = P[i + K + 1]
            if que[0] == prev:
                que.popleft()
            while que and cur > que[-1]:
                que.pop()
            que.append(cur)
            p_max[i + 1] = que[0]

    def calc_asc():
        prev = -1
        cnt = 0
        for i in range(K):
            cur = P[i]
            if prev < cur:
                cnt += 1
            else:
                cnt = 1
            prev = cur
        p_asc[0] = cnt

        for i in range(N - K):
            cur = P[i + K]
            if prev < cur:
                p_asc[i + 1] = min(p_asc[i] + 1, K)
            else:
                p_asc[i + 1] = 1
            prev = cur

    calc_min()
    calc_max()
    calc_asc()

    uf = UnionFind(N - K + 1)

    asc_list = []
    for i in range(N - K + 1):
        if p_asc[i] == K:
            asc_list.append(i)
    if len(asc_list) > 1:
        for i in range(1, len(asc_list)):
            uf.union(asc_list[0], asc_list[i])

    for i in range(N - K):
        if p_min[i] == P[i] and p_max[i] == P[i + K]:
            uf.union(i, i + 1)

    print(uf.group_count())


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class SegTree:  # 0-index !!!
    def __init__(self, seq, fx, ex):
        self.n = len(seq)
        self.fx = fx
        self.ex = ex
        self.size = 1<<(self.n - 1).bit_length()
        self.tree = [ex] * (self.size * 2)
        # build
        for i, x in enumerate(seq, start=self.size):
            self.tree[i] = x
        for i in reversed(range(1, self.size)):
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, i, x):
        i += self.size
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def query(self, l, r):
        tmp_l = self.ex
        tmp_r = self.ex
        l += self.size
        r += self.size
        while l < r:
            if l & 1:
                tmp_l = self.fx(tmp_l, self.tree[l])
                l += 1
            if r & 1:
                tmp_r = self.fx(self.tree[r - 1], tmp_r)  # 交換法則を仮定しない(順序大事に)
            l >>= 1
            r >>= 1
        return self.fx(tmp_l, tmp_r)

# ---------------------- #

n, k = (int(x) for x in input().split())
P = list(int(x) for x in input().split())

min_seg = SegTree(P, fx=min, ex=10**18)
max_seg = SegTree(P, fx=max, ex=0)

asc_count = [1] * n
for i in range(1, n):
    if P[i] > P[i - 1]:
        asc_count[i] = asc_count[i - 1] + 1

ans = 1
no_count = 0
if asc_count[k - 1] >= k:
    no_count += 1
for i in range(1, n - k + 1):
    if P[i - 1] != min_seg.query(i - 1, i + k - 1) or P[i + k - 1] != max_seg.query(i, i + k):
        ans += 1
        if asc_count[i + k - 1] >= k:
            no_count += 1

print(ans - max(no_count - 1, 0))

Submission status: Accepted

Solution code:
class SegTree:  # 0-index !!!
    """
    fx: モノイドXでの二項演算
    ex: モノイドXでの単位元
    init(seq, fx, ex): 配列seqで初期化 O(N)
    update(i, x): i番目の値をxに更新 O(logN)
    query(l, r): 区間[l,r)をfxしたものを返す O(logN)
    get(i): i番目の値を返す
    show(): 配列を返す
    """

    def __init__(self, seq, fx, ex):
        self.n = len(seq)
        self.fx = fx
        self.ex = ex
        self.size = 1<<(self.n - 1).bit_length()
        self.tree = [ex] * (self.size * 2)
        # build
        for i, x in enumerate(seq, start=self.size):
            self.tree[i] = x
        for i in reversed(range(1, self.size)):
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def set(self, i, x):  # O(log(n))
        i += self.size
        self.tree[i] = x
        while i:
            i >>= 1
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, i, x):
        i += self.size
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def query(self, l, r):  # l = r の場合はたぶんバグるので注意
        tmp_l = self.ex
        tmp_r = self.ex
        l += self.size
        r += self.size
        while l < r:
            if l & 1:
                tmp_l = self.fx(tmp_l, self.tree[l])
                l += 1
            if r & 1:
                tmp_r = self.fx(self.tree[r - 1], tmp_r)  # 交換法則を仮定しない(順序大事に)
            l >>= 1
            r >>= 1
        return self.fx(tmp_l, tmp_r)

    def get(self, i):
        return self.tree[self.size + i]

    def show(self):
        return self.tree[self.size: self.size + self.n]

# ---------------------- #

n, k = (int(x) for x in input().split())
P = list(int(x) for x in input().split())

min_seg = SegTree(P, fx=min, ex=10**18)
max_seg = SegTree(P, fx=max, ex=0)

asc_count = [1] * n
for i in range(1, n):
    if P[i] > P[i - 1]:
        asc_count[i] = asc_count[i - 1] + 1

ans = 0
no_count = 0
min_out_flag = False
for i in range(n - k + 1):
    if not min_out_flag or P[i + k - 1] != max_seg.query(i, i + k):
        ans += 1
        if asc_count[i + k - 1] >= k:
            no_count += 1
    if P[i] == min_seg.query(i, i + k):
        min_out_flag = True
    else:
        min_out_flag = False
print(ans - max(no_count - 1, 0))

Submission status: Accepted

Solution code:
from collections import Counter, deque
N, K = map(int, input().split())
P = list(map(int, input().split()))
ans = N - K + 1


# 変化しないものを数える
LIS = [-1] * N
LIS[-1] = 1
LIS_MIN_NOW = P[-1]
for i in reversed(range(N - 1)):
    p = P[i]
    if p < LIS_MIN_NOW:
        LIS_MIN_NOW = p
        LIS[i] = LIS[i + 1] + 1
    else:
        LIS_MIN_NOW = p
        LIS[i] = 1
LIS = LIS[:N - K + 1]


def slide_min(A, K):
    deq, ret = deque([]), []
    for k in range(len(A)):
        while deq and A[deq[-1]] >= A[k]:
            deq.pop()
        deq.append(k)

        if k < K - 1:
            continue

        if deq[0] + K <= k:
            deq.popleft()
        ret.append(A[deq[0]])

    return ret


# スライド最小値・最大値を計算
MIN = slide_min(P, K)
MAX = list(map(lambda x: -x, slide_min(list(map(lambda x: -x, P)), K)))


for i in range(N - K + 1):
    flg = False
    if LIS[i] >= K:
        flg = True

    if (i + 1 < N - K + 1) and (P[i] == MIN[i]) and (P[i + K] == MAX[i + 1]):
        flg = True

    ans -= flg

if len([l for l in LIS if l >= K]):
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter, deque
N, K = map(int, input().split())
P = list(map(int, input().split()))
ans = N - K + 1


# 変化しないものを数える
LIS = [-1] * N
LIS[-1] = 1
LIS_MIN_NOW = P[-1]
for i in reversed(range(N - 1)):
    p = P[i]
    if p < LIS_MIN_NOW:
        LIS_MIN_NOW = p
        LIS[i] = LIS[i + 1] + 1
    else:
        LIS_MIN_NOW = p
        LIS[i] = 1
LIS = LIS[:N - K + 1]


# スライド最小値を計算
slide_min = deque([])
MIN = []
for k in range(N):
    while slide_min and P[slide_min[-1]] >= P[k]:
        slide_min.pop()
    slide_min.append(k)

    if k < K - 1:
        continue

    if slide_min[0] + K <= k:
        slide_min.popleft()
    MIN.append(P[slide_min[0]])


# スライド最大値を計算
slide_max = deque([])
MAX = []
for k in range(N):
    while slide_max and P[slide_max[-1]] <= P[k]:
        slide_max.pop()
    slide_max.append(k)

    if k < K - 1:
        continue

    if slide_max[0] + K <= k:
        slide_max.popleft()
    MAX.append(P[slide_max[0]])


for i in range(N - K + 1):
    flg = False
    if LIS[i] >= K:
        flg = True

    if (i + 1 < N - K + 1) and (P[i] == MIN[i]) and (P[i + K] == MAX[i + 1]):
        flg = True

    ans -= flg

if len([l for l in LIS if l >= K]):
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


class SegmentTreeRMQ(object):  # 1-indexed [l,r)
    def __init__(self, size, value):
        self.len = 1 << size.bit_length()
        # print(self.len)
        self.array = [value] * (2 * self.len)

    def update(self, i, x):  # 0-indexed
        i += self.len
        while i > 0:
            self.array[i] = min(self.array[i], x)
            i >>= 1
        # print(self.array)

    def get(self, i):  # 0-indexed
        return self.array[i + self.len]

    def get_minimum(self, l, r):  # 0-indexed
        L = l+self.len
        R = r+self.len
        ANS = 1 << 30

        while L < R:
            if L & 1:
                ANS = min(ANS, self.array[L])
                L += 1

            if R & 1:
                R -= 1
                ANS = min(ANS, self.array[R])
            L >>= 1
            R >>= 1

        return ANS


N, K = na()
P = na()

if N == K or N == 2:
    print(1)
    exit()


min_tree = SegmentTreeRMQ(N, N)
max_tree = SegmentTreeRMQ(N, 1)

for i, p in enumerate(P):
    min_tree.update(i, p)
    max_tree.update(i, -p)

no_change = [0] * (N-K+1)

last = -1

for i in range(N):
    if i - last >= K:
        no_change[i-K+1] = 1
    if i == N-1:
        break
    if P[i] > P[i+1]:
        last = i

# print(no_change)


ans = 1
no_count = 0

for i in range(N-K):
    if P[i] > min_tree.get_minimum(i+1, i+K+1) or -P[i+K] > max_tree.get_minimum(i+1, i+K+1):
        ans += 1
        if no_change[i] == 1:
            no_count += 1
    if i == (N-K-1) and no_change[N-K] == 1:
        no_count += 1

print(ans - max(0, no_count-1))

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

class SegminTree:
    # init_valはseg木にしたいlist、ide_eleは単位元
    # """
    # 単位元の説明
    # 最小値のセグ木 → 10**9　(最小値の更新に影響しないため)
    # 　　和のセグ木 → 0　(上の単位元の説明を参照)
    # 　　積のセグ木 → 1　(上の単位元の説明を参照)
    # 　　gcdのセグ木 → 0　(gcdを更新しない値は0)
    # """
    def __init__(self, init_val, ide_ele):
        self.ide_ele=ide_ele
        self.num=2**(len(init_val)-1).bit_length()
        self.seg=[self.ide_ele]*2*self.num

        #set_val
        for i in range(len(init_val)):
            self.seg[i+self.num-1]=init_val[i]
        #built
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2])

    # 書け
    def segfunc(self, x, y):
        return min(x,y)
    
    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[k*2+1],self.seg[k*2+2])

    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

class SegmaxTree:
    # init_valはseg木にしたいlist、ide_eleは単位元
    # """
    # 単位元の説明
    # 最小値のセグ木 → 10**9　(最小値の更新に影響しないため)
    # 　　和のセグ木 → 0　(上の単位元の説明を参照)
    # 　　積のセグ木 → 1　(上の単位元の説明を参照)
    # 　　gcdのセグ木 → 0　(gcdを更新しない値は0)
    # """
    def __init__(self, init_val, ide_ele, func):
        self.ide_ele=ide_ele
        self.num=2**(len(init_val)-1).bit_length()
        self.seg=[self.ide_ele]*2*self.num
        self.func=func

        #set_val
        for i in range(len(init_val)):
            self.seg[i+self.num-1]=init_val[i]
        #built
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2])

    # 書け
    def segfunc(self, x, y):
        return self.func(x,y)
    
    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[k*2+1],self.seg[k*2+2])

    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

segmin=SegminTree(p,10**9)
segmax=SegmaxTree(p,0,max)

lst=[]
for i in range(n-k+1):
    tmp1=segmin.query(i,k+i)
    tmp2=segmax.query(i,k+i)
    lst.append((tmp1,tmp2))
# print(lst)

ans=1
for i in range(n-k):
    # print(lst[i][0],p[i])
    # print(lst[i+1][1],p[i+k])
    if lst[i][0]==p[i] and lst[i+1][1]==p[i+k]:
        continue
    else:
        ans+=1
# print(ans)

cnt=1
cnt2=0
flag=0
for i in range(n-1):
    if p[i]<p[i+1]:
        if flag==1:
            continue
        else:
            cnt+=1
    else:
        cnt=1
        flag=0
    if cnt>=k:
        cnt2+=1
        flag=1
# print(cnt2)
if cnt2>=2:
    print(ans-cnt2+1)
else:
    print(ans)