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 collections import deque



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

disordered_count = [0]

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

ordered = 0

def interval_min(a, K):
    q = deque()
    min_array = []
    for i, v in enumerate(a):
        while len(q) != 0 and a[q[len(q)-1]] > v:
            q.pop()

        q.append(i)

        if i >= K-1:
            min_array.append(q[0])
            if q[0] == len(min_array)-1:
                q.popleft()
    return min_array

def interval_max(a, K):
    return interval_min([-i for i in a], K)

res = 0
min_array = interval_min(P, K)
max_array = interval_max(P, K)

# print(N,K)
# print(P)
# print(max_array)

for i in range(N-K+1):
    if disordered_count[i] == disordered_count[i+K-1]:
        ordered = 1
    else:
        if i == 0:
            res += 1
        else:
            if not (P[i-1] == P[min_array[i-1]] and P[i+K-1] == P[max_array[i]]):
                res += 1
    # print(P[i:i+K], res)


print(res+ordered)

Submission status: Accepted

Solution code:
import heapq
from collections import deque, Counter
N, K = map(int, input().split())
P = list(map(int, input().split()))
#ans = []
q = deque()
q_idx = []
L = []
for i, p in enumerate(P):
    while q and p <= q[-1][1]:
        idx, _ = q.pop()
        heapq.heappush(q_idx, idx)
    q.append((i, p))
    #print(q, q_idx)
    L.append(q_idx[0] if q_idx else -1)
    #ans.append(q[0][1])
    if q and q[0][0] <= i+1-K:
        idx, _ = q.popleft()
    if q_idx and q_idx[0] <= i+1-K:
        heapq.heappop(q_idx)
L = L[K-1:]

P = [-p for p in P]
P.reverse()
q = deque()
q_idx = []
R = []
for i, p in enumerate(P):
    while q and p <= q[-1][1]:
        idx, _ = q.pop()
        heapq.heappush(q_idx, idx)
    q.append((i, p))
    #print(q, q_idx)
    R.append(N - 1 - q_idx[0] if q_idx else -1)
    #ans.append(q[0][1])
    if q and q[0][0] <= i+1-K:
        idx, _ = q.popleft()
    if q_idx and q_idx[0] <= i+1-K:
        heapq.heappop(q_idx)
R = R[K-1:]
R.reverse()

#for l, r in zip(L, R):
print(len(Counter(zip(L, R))))

Submission status: Accepted

Solution code:
from collections import deque

def sliding_minima(a, k):
    dq = deque()
    l = r = 0
    ret = []
    for i, item in enumerate(a):
        while(dq and a[dq[-1]] >= a[i]):
            dq.pop()
        dq.append(i)
        if i < k - 1:
            continue
        if dq[0] == i - k:
            dq.popleft()
        ret.append(a[dq[0]])
    return ret

def sliding_maxima(a, k):
    dq = deque()
    l = r = 0
    ret = []
    for i, item in enumerate(a):
        while(dq and a[dq[-1]] <= a[i]):
            dq.pop()
        dq.append(i)
        if i < k - 1:
            continue
        if dq[0] == i - k:
            dq.popleft()
        ret.append(a[dq[0]])
    return ret

def is_increasing(a, k):
    increasing = [0] * len(a)
    for i, (a1, a2) in enumerate(zip(a, a[1:])):
        if a1 < a2:
            increasing[i+1] = 1
    ret = [0] * (len(a) - k + 1)
    val = sum(increasing[1:k])
    if val == k-1:
        ret[0] = 1
    for i in range(len(a) - k):
        val += increasing[i + k]
        val -= increasing[i + 1]
        if val == k-1:
            ret[i+1] = 1
        else:
            ret[i+1] = 0
    return ret

n, k = [int(item) for item in input().split()]
a = [int(item) for item in input().split()]

minima = sliding_minima(a, k)
maxima = sliding_maxima(a, k)
increasing = is_increasing(a, k)

ans = n - k + 1
if increasing[0]:
    ans -= 1
for l, r, minima, maxima, inc in zip(a, a[k:], minima[1:], maxima, increasing[1:]):
    if (l < minima and r > maxima) or inc:
        ans -= 1
if sum(increasing) > 0:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


class Segtree:
    # https://atcoder.jp/contests/agc038/submissions/7637556
    # の実装を借用しました
    
    # Segment tree
    # 1-indexed
    # 再帰を使わないもの
    # 最小値を求める
    def __init__(self, n, v, func, initial):
        self.initial = initial
        self.func = func
        self.size = 1 << n.bit_length()
        # Segment treeの台の要素数
        self.tree = [self.initial] * (2 * self.size)
        # 1-indexedなので、要素数2*self.size
        # Segment treeの初期値で初期化

        for i in range(n):  # Aを対応する箇所へupdate
            self.tree[i + self.size] = v[i]

        for i in range(self.size - 1, 0, -1):  # 親の部分もupdate
            self.tree[i] = self.func(self.tree[i * 2], self.tree[i * 2 + 1])

    def update(self, n, x):  # v[n]をxへ更新（反映）
        i = n + self.size
        self.tree[i] = x
        i >>= 1  # 子ノードへ

        while i != 0:
            self.tree[i] = self.func(self.tree[i * 2], self.tree[i * 2 + 1])
            i >>= 1

    def getvalues(self, l, r):  # 区間[l,r)に関するfuncを調べる
        L = l + self.size
        R = r + self.size
        ANS = self.initial

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

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

        return ANS


class UnionFind:
    def __init__(self, n):
        self.v = [-1 for _ in range(n)]

    def find(self, x):
        if self.v[x] < 0:  # (負)は根
            return x
        else:
            self.v[x] = self.find(self.v[x])
            return self.v[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if -self.v[x] < -self.v[y]:
            x, y = y, x
        self.v[x] += self.v[y]
        self.v[y] = x

    def root(self, x):
        return self.v[x] < 0


def main():
    n, k = map(int, input().split())
    p = tuple(int(x) for x in input().split())

    tr1 = Segtree(n, p, min, 1 << 30)
    tr2 = Segtree(n, p, max, -1)

    uf = UnionFind(n)

    cont = 1
    v = None
    for i in range(1, n):
        if p[i - 1] < p[i]:
            cont += 1
        else:
            cont = 1
        if cont >= k:
            # print(i - k + 1)
            if v is None:
                v = i - k + 1
            else:
                uf.unite(v, i - k + 1)
                # print(v, i - k + 1)

    for i in range(n - k):
        # print(f'i:{i} {p[i]} < {tr1.getvalues(i + 1, i + k)} < {tr2.getvalues(i + 1, i + k)} < {p[i + k]}')
        if p[i] < tr1.getvalues(i + 1, i + k) < tr2.getvalues(i + 1, i + k) < p[i + k]:
            uf.unite(i, i + 1)
            # print(i, i + 1)

    ans = sum(uf.root(x) for x in range(n - k + 1))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000)


class SegmentTree():
    def __init__(self, array, f, ti):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        ti : 
            identity element of the monoid
        """
        self.f = f
        self.ti = ti
        self.n = n = 2**(len(array).bit_length())
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def update(self, p, v):  # set value at position p (0-indexed)
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def query(self, l, r):  # result on interval [l, r) (0-indexed)
        f, ti, n, dat = self.f, self.ti, self.n, self.dat
        res = ti
        l += n
        r += n
        while l < r:
            if l & 1:
                res = f(res, dat[l])
                l += 1
            if r & 1:
                r -= 1
                res = f(dat[r], res)
            l >>= 1
            r >>= 1
        return res


class UnionFind():
    def __init__(self, size):
        self.dat = list(range(size))
        self.SIZE = [1] * size  # 0-indexed

    def find(self, x):
        dat = self.dat
        stack = [x]
        while True:
            y = stack[-1]
            if dat[y] != y:
                stack += [dat[y]]
            else:
                break
        for s in stack:
            dat[s] = y
        return y

    def unite(self, x, y):
        is_same = self.is_same
        find = self.find
        SIZE = self.SIZE
        dat = self.dat
        if not is_same(x, y):
            X, Y = find(x), find(y)
            SX, SY = SIZE[X], SIZE[Y]
            if SX > SY:
                m = dat[X] = Y
            else:
                m = dat[Y] = X
            SIZE[m] = SX + SY
            SIZE[X + Y - m] = 0

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

    def scan_uf(self):
        find = self.find
        length = len(self.dat)
        for i in range(length):
            find(i)

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


N, K = [int(_) for _ in input().split()]
P = [int(_) for _ in input().split()]
STmax = SegmentTree(array=P, f=max, ti=-float('inf'))
STmin = SegmentTree(array=P, f=min, ti=float('inf'))
UF = UnionFind(N - K + 1)
for i in range(N - K):
    if P[i] == STmin.query(i, i + K) and P[i + K] == STmax.query(
            i + 1, i + K + 1):
        UF.unite(i, i + 1)
inc = 0
incK = []
for i in range(N - 2, -1, -1):
    if P[i] <= P[i + 1]:
        inc += 1
        if inc >= K - 1:
            incK += [i]
    else:
        inc = 0
for i in incK:
    UF.unite(incK[0], i)
UF.scan_uf()
print(len(set(UF.dat)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000)


class SegmentTree():
    def __init__(self, array, f, ti):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        ti : 
            identity element of the monoid
        """
        self.f = f
        self.ti = ti
        self.n = n = 2**(len(array).bit_length())
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def update(self, p, v):  # set value at position p (0-indexed)
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def query(self, l, r):  # result on interval [l, r) (0-indexed)
        f, ti, n, dat = self.f, self.ti, self.n, self.dat
        res = ti
        l += n
        r += n
        while l < r:
            if l & 1:
                res = f(res, dat[l])
                l += 1
            if r & 1:
                r -= 1
                res = f(dat[r], res)
            l >>= 1
            r >>= 1
        return res


class UnionFind:
    def __init__(self, size):
        self.dat = list(range(size))
        self.SIZE = [1] * size  # 0-indexed

    def find(self, x):
        dat = self.dat
        stack = [x]
        while True:
            y = stack[-1]
            if dat[y] != y:
                stack += [dat[y]]
            else:
                break
        for s in stack:
            dat[s] = y
        return y

    def unite(self, x, y):
        is_same = self.is_same
        find = self.find
        SIZE = self.SIZE
        dat = self.dat
        if not is_same(x, y):
            X, Y = find(x), find(y)
            SX, SY = SIZE[X], SIZE[Y]
            if SX > SY:
                m = dat[X] = Y
            else:
                m = dat[Y] = X
            SIZE[m] = SX + SY
            SIZE[X + Y - m] = 0

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

    def scan_uf(self):
        find = self.find
        length = len(self.dat)
        for i in range(length):
            find(i)

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


N, K = [int(_) for _ in input().split()]
P = [int(_) for _ in input().split()]
STmax = SegmentTree(array=P, f=max, ti=-float('inf'))
STmin = SegmentTree(array=P, f=min, ti=float('inf'))
UF = UnionFind(N - K + 1)
for i in range(N - K):
    if P[i] == STmin.query(i, i + K) and P[i + K] == STmax.query(
            i + 1, i + K + 1):
        UF.unite(i, i + 1)
inc = 0
incK = []
for i in range(N - 2, -1, -1):
    if P[i] <= P[i + 1]:
        inc += 1
        if inc >= K - 1:
            incK += [i]
    else:
        inc = 0
for i in incK:
    UF.unite(incK[0], i)
UF.scan_uf()
print(len(set(UF.dat)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000)


class SegmentTree():
    def __init__(self, array, f, ti):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        ti : 
            identity element of the monoid
        """
        self.f = f
        self.ti = ti
        self.n = n = 2**(len(array).bit_length())
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def update(self, p, v):  # set value at position p (0-indexed)
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def query(self, l, r):  # result on interval [l, r) (0-indexed)
        f, ti, n, dat = self.f, self.ti, self.n, self.dat
        res = ti
        l += n
        r += n
        while l < r:
            if l & 1:
                res = f(res, dat[l])
                l += 1
            if r & 1:
                r -= 1
                res = f(dat[r], res)
            l >>= 1
            r >>= 1
        return res



class UnionFind:
    def __init__(self, size):
        self.UF = list(range(size))
        self.SIZE = [1] * size  # 0-indexed

    def find(self, x):
        UF = self.UF
        stack = [x]
        while True:
            y = stack[-1]
            if UF[y] != y:
                stack += [UF[y]]
            else:
                break
        for s in stack:
            UF[s] = y
        return y

    def unite(self, x, y):
        is_same = self.is_same
        find = self.find
        SIZE = self.SIZE
        UF = self.UF
        if not is_same(x, y):
            X, Y = find(x), find(y)
            SX, SY = SIZE[X], SIZE[Y]
            if SX > SY:
                m = UF[X] = Y
            else:
                m = UF[Y] = X
            SIZE[m] = SX + SY
            SIZE[X + Y - m] = 0

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

    def scan_uf(self):
        find = self.find
        length = len(self.UF)
        for i in range(length):
            find(i)

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


N, K = [int(_) for _ in input().split()]
P = [int(_) for _ in input().split()]
STmax = SegmentTree(array=P, f=max, ti=-float('inf'))
STmin = SegmentTree(array=P, f=min, ti=float('inf'))
UF = UnionFind(N - K + 1)
for i in range(N - K):
    if P[i] == STmin.query(i, i + K) and P[i + K] == STmax.query(
            i + 1, i + K + 1):
        UF.unite(i, i + 1)
inc = 0
incK = []
for i in range(N - 2, -1, -1):
    if P[i] <= P[i + 1]:
        inc += 1
        if inc >= K - 1:
            incK += [i]
    else:
        inc = 0
for i in incK:
    UF.unite(incK[0], i)
UF.scan_uf()
print(len(set(UF.UF)))

Submission status: Accepted

Solution code:
class SegmentTree():
    def __init__(self,param,default,func):
        if isinstance(param,list):
            n=len(param)
        else:
            n=param
        self.d=default
        self.leaf=1<<(n-1).bit_length()
        if isinstance(param,list):
            self.tree=[default]*(self.leaf-1)+param+[default]*(self.leaf-n)
            for i in range(self.leaf-2,-1,-1):
                self.tree[i]=func(self.tree[i*2+1],self.tree[i*2+2])
        else:
            self.tree=[default]*(self.leaf*2-1)
        self.f=func
    def find(self,i):
        return self.tree[i+self.leaf-1]
    def merge(self,a,b):
        return self.f(a,b)
    def get_top(self):
        return self.tree[0]
    def query(self,a,b):
        T=self.tree
        l,r=a+self.leaf-1,b+self.leaf-1
        res=self.d
        while l<r:
            if not l%2:
                res=self.merge(res,T[l])
                l+=1
            if not r%2:
                r-=1
                res=self.merge(res,T[r])
            l>>=1; r>>=1
        return res

def main():
    inf=10**7
    n,k=map(int,input().split())
    P=list(map(int,input().split()))
    segmax=SegmentTree(P,0,max)
    segmin=SegmentTree(P,inf,min)
    ans=n-k+1
    for i in range(n-k):
        if segmin.query(i,i+k)==P[i] and segmax.query(i,i+k)<P[i+k]:
            ans-=1
    tmp=1
    cnt=0
    for i in range(n-1):
        if P[i]>P[i+1]:
            if tmp>=k:
                cnt+=1
            tmp=1
        else:
            tmp+=1
    if tmp>=k:
        cnt+=1
    ans-=max(0,cnt-1)
    print(ans)
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
class SparseTableMAX():
    def __init__(self, array, n):
        '''テーブルを構築する'''
        self.row_size = n.bit_length()
        
        # log_tableを構築する
        # log_table = [0, 0, 1, 1, 2, 2, 2, 2, ...]
        self.log_table = [0] * (n + 1)
        for i in range(2, n + 1):
            self.log_table[i] = self.log_table[i//2] + 1
        
        # sparse_tableを構築する
        self.sparse_table = [[0] * n for _ in range(self.row_size)]
        for i in range(n):
            self.sparse_table[0][i] = array[i]
        for row in range(1, self.row_size):
            for i in range(n - (1 << row) + 1):
               self.sparse_table[row][i] = self._merge(self.sparse_table[row - 1][i], \
                                                       self.sparse_table[row - 1][i + (1 << row - 1)])

    def _merge(self, num1, num2):
        '''クエリの内容'''
        return max(num1, num2)

    def query(self, l, r):
        '''区間[l, r)に対するクエリに答える'''
        if r == l:
            return None
        row = self.log_table[r - l]
        return self._merge(self.sparse_table[row][l], self.sparse_table[row][r - (1 << row)])


class SparseTableMIN():
    def __init__(self, array, n):
        '''テーブルを構築する'''
        self.row_size = n.bit_length()
        
        # log_tableを構築する
        # log_table = [0, 0, 1, 1, 2, 2, 2, 2, ...]
        self.log_table = [0] * (n + 1)
        for i in range(2, n + 1):
            self.log_table[i] = self.log_table[i//2] + 1
        
        # sparse_tableを構築する
        self.sparse_table = [[0] * n for _ in range(self.row_size)]
        for i in range(n):
            self.sparse_table[0][i] = array[i]
        for row in range(1, self.row_size):
            for i in range(n - (1 << row) + 1):
               self.sparse_table[row][i] = self._merge(self.sparse_table[row - 1][i], \
                                                       self.sparse_table[row - 1][i + (1 << row - 1)])

    def _merge(self, num1, num2):
        '''クエリの内容'''
        return min(num1, num2)

    def query(self, l, r):
        '''区間[l, r)に対するクエリに答える'''
        if r == l:
            return None
        row = self.log_table[r - l]
        return self._merge(self.sparse_table[row][l], self.sparse_table[row][r - (1 << row)])
      
n, k = map(int, input().split())
a = list(map(int, input().split()))
max_st = SparseTableMAX(a, n)
min_st = SparseTableMIN(a, n)

ans = 0
for i in range(1,n-k+1):
    l = a[i-1]
    r = a[i+k-1]
    min_ = min_st.query(i-1, i-1+k)    
    max_ = max_st.query(i, i+k)
    if l != min_ or r != max_:
        ans += 1

tmp = 0
cnt = 0
tmp_ans = 0
l = -1
for i in range(1, n):
    if a[i-1] > a[i]:
        tmp = i
    if i >= k-1 and tmp <= i - k + 1:
        if i - l > 1:
            cnt += 1
        l = i
ans += 1 - max(cnt - 1, 0)

print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
P=[int(i) for i in input().split()]
import collections
from collections import deque
M1,M2=deque(),deque()
A1,A2=[],[]
M1.append(0)
for i in range(1,n):
  while M1:
    if P[M1[-1]]>P[i]:
      M1.pop()
    else:
      M1.append(i)
      break
  if not M1:
    M1.append(i)
  if M1[0]==i-k-1:
    M1.popleft()
  if i<k:
    continue
  else:
    A1.append(P[M1[0]])
M2.append(0)
for i in range(1,n):
  while M2:
    if P[M2[-1]]<P[i]:
      M2.pop()
    else:
      M2.append(i)
      break
  if not M2:
    M2.append(i)
  if M2[0]==i-k-1:
    M2.popleft()
  if i<k:
    continue
  else:
    A2.append(P[M2[0]])
ans=1
for i in range(n-k):
  if A1[i]==P[i] and A2[i]==P[i+k]:
    continue
  else:
    ans+=1
Q=[0]*n
for i in range(1,n):
  if P[i]>P[i-1]:
    Q[i]=Q[i-1]+1
  else:
    continue
count=0
for i in range(n):
  if Q[i]==k-1:
    count+=1
print(ans-max(0,count-1))

Submission status: Accepted

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    n,k=map(int,input().split())
    x=list(map(int,input().split()))
    
    min_list=[]
    max_list=[]
    m=262143+n
    segtree=[-1]*m
    
    for i in range(262143,m):
        segtree[i]=x[i-262143]
    	
    for i in range(262142,-1,-1):
        j=2*i+1
        if j>=m:
            segtree[i]=-1
        elif j+1>=m:
            segtree[i]=segtree[j]
        else:
            segtree[i]=min(segtree[j],segtree[j+1])
    
    for i in range(n-k+2):
        qq=[(i,i+k-2,0,1)]
        s=set()
        while qq:
            ii,jj,now,kubun=qq.pop()
            now2=now-kubun+1
            width=262144//kubun
            left=width*now2
            right=width*(now2+1)-1
            if ii<=left and right<=jj:
                s.add(segtree[now])
            elif jj<left or right<ii:
                continue
            else:
                qq.append((ii,jj,2*now+1,2*kubun))
                qq.append((ii,jj,2*now+2,2*kubun))
        min_list.append(min(s))
       
    for i in range(262142,-1,-1):
        j=2*i+1
        if j>=m:
            segtree[i]=n+1
        elif j+1>=m:
            segtree[i]=segtree[j]
        else:
            segtree[i]=max(segtree[j],segtree[j+1])
    
    for i in range(n-k+2):
        qq=[(i,i+k-2,0,1)]
        s=set()
        while qq:
            ii,jj,now,kubun=qq.pop()
            now2=now-kubun+1
            width=262144//kubun
            left=width*now2
            right=width*(now2+1)-1
            if ii<=left and right<=jj:
                s.add(segtree[now])
            elif jj<left or right<ii:
                continue
            else:
                qq.append((ii,jj,2*now+1,2*kubun))
                qq.append((ii,jj,2*now+2,2*kubun))
        max_list.append(max(s))
        
    cnt=0
    flag=[True]*(n-k+1)
    first=False
    for i in range(n-1):
        if x[i]<x[i+1]:
            cnt+=1
        else:
            cnt=0
        if cnt>=k-1:
            if first==False:
                first=True
            else:
                flag[i-k+2]=False
    
    for i in range(1,n-k+1):
        if x[i-1]<min_list[i] and max_list[i]<x[i+k-1]:
            flag[i]=False
            
    print(sum(flag))

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:



class SegmentTree:
    def __init__(self, L, op, ide):
        self.op = op
        self.ide = ide
        self.sz = len(L)
        self.n = 1
        self.s = 1
        for i in range(1000):
            self.n *= 2
            self.s += 1
            if self.n >= self.sz:
                break
        self.node = [self.ide]*(2*self.n-1)

        for i in range(self.sz):
            self.node[i+self.n-1] = L[i]

        for i in range(self.n-2,-1,-1):
            self.node[i] = self.op(self.node[i*2+1],self.node[i*2+2])
    
    def add(self, a, x):
        k = a+self.n-1
        self.node[k] += x
        for i in range(1000):
            k = (k-1)//2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])
            if k <= 0:
                break
    
    def substitute(self, a, x):
        k = a+self.n-1
        self.node[k] = x
        for i in range(1000):
            k = (k-1)//2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])
            if k <= 0:
                break

    def get_one(self, a):
        k = a+self.n-1
        return self.node[k]
    
    def get(self, l, r):
        res = self.ide
        n = self.n
        if self.sz <= r or 0 > l:
            print("ERROR: the indice are wrong.")
            return False

        for i in range(self.s):
            count = 2**i-1
            a = (r+1)//n
            b = (l-1)//n
            if a-b == 3:
                res = self.op(self.node[count+b+1],res)
                res = self.op(self.node[count+b+2],res)
                right = a*n
                left = (b+1)*n-1
                break
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n
                left = (b+1)*n-1
                break
            n = n//2

        #left
        n1 = n//2        
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (left+1)//n1
            b = (l-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                left = (b+1)*n1-1                
            n1 = n1//2

        #right
        n1 = n//2        
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (r+1)//n1
            b = (right-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n1                
            n1 = n1//2
        return res

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

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

count = 0
Tag = [0]*N

for i in range(1,N):
    if P[i]<P[i-1]:
        count+=1
    Tag[i]=count


ST1 = SegmentTree(P,max,-10**27)
ST2 = SegmentTree(P,min,10**27)
ans = 0
same_flag = False

for i in range(N-K+1):
    if Tag[i+K-1]==Tag[i]:
        if not same_flag:
            same_flag=True
            ans+=1
    else:
        if i>0:
            M = ST1.get(i,i+K-2)
            m = ST2.get(i,i+K-2)
            if not (P[i-1]<m and P[i+K-1]>M):
                ans+=1
        else:
            ans+=1

print(ans)

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop

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

    ans = N - K + 1

    numAsc = 0
    num = 0
    P0 = -1
    for P in (Ps+[-1]):
        if P0 < P:
            num += 1
        else:
            if num >= K:
                numAsc += num-K+1
            num = 1
        P0 = P
    if numAsc > 0:
        ans -= numAsc - 1

    if K > 2:
        mins = [N] * N
        P = min(Ps[:K+1])
        mins[0] = P
        PQ = [(P, i) for i, P in enumerate(Ps[:K+1])]
        heapify(PQ)
        for i in range(K+1, N):
            heappush(PQ, (Ps[i], i))
            while True:
                P, pos = heappop(PQ)
                if i-K <= pos:
                    mins[i-K] = P
                    heappush(PQ, (P, pos))
                    break

        maxs = [-1] * N
        P = max(Ps[:K+1])
        maxs[0] = P
        PQ = [(-P, i) for i, P in enumerate(Ps[:K+1])]
        heapify(PQ)
        for i in range(K+1, N):
            heappush(PQ, (-Ps[i], i))
            while True:
                P, pos = heappop(PQ)
                if i-K <= pos:
                    maxs[i-K] = -P
                    heappush(PQ, (P, pos))
                    break

        isSorteds = [False] * N
        num = 0
        P0 = -1
        for i, P in enumerate(Ps+[-1]):
            if P0 < P:
                num += 1
                if num >= K-1:
                    isSorteds[i-K+1] = True  ###
            else:
                if num >= K:
                    numAsc += num-K+1
                num = 1
            P0 = P

        for i in range(N-K):
            L, R = Ps[i], Ps[i+K]
            minK, maxK = mins[i], maxs[i]
            if L == minK and R == maxK and not isSorteds[i]:
                ans -= 1

    print(ans)


solve()