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 defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class SegmentTree:
    def __init__(self, init_val, ide_ele, op):
        n = len(init_val)
        self.num = 2 ** (n - 1).bit_length()
        self.seg = [ide_ele] * 2 * self.num
        self.ide_ele = ide_ele
        self.op = op
        for i in range(n):
            self.seg[i + self.num - 1] = init_val[i]
            # built
        for i in range(self.num - 2, -1, -1):
            self.seg[i] = self.op(self.seg[2 * i + 1], self.seg[2 * i + 2])


    def update(self, k, x):
        k += self.num - 1
        self.seg[k] = x
        while k + 1:
            k = (k - 1) // 2
            self.seg[k] = self.op(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.op(res, self.seg[p])
            if q & 1 == 1:
                res = self.op(res, self.seg[q])
            p = p // 2
            q = (q - 2) // 2
        if p == q:
            res = self.op(res, self.seg[p])
        else:
            res = self.op(self.seg[p], self.op(res, self.seg[q]))
        return res


n, k = LI()
L = LI()
min_ST = SegmentTree(L, INF, min)
max_ST = SegmentTree(L, -INF, max)
cnt = 1
for i in range(n - k):
    if min_ST.query(i, i + k) == L[i] and max_ST.query(i + 1, i + k + 1) == L[i + k]:
        continue
    else:
        cnt += 1


ret = -INF
increasing_block_num = 0
max_len = 0
for j in range(n):
    if L[j] >= ret:
        max_len += 1

    else:
        if max_len >= k:
            increasing_block_num += 1
        max_len = 1
    ret = L[j]


if max_len >= k:
    increasing_block_num += 1



if increasing_block_num:
    print(cnt - (increasing_block_num - 1))
else:
    print(cnt)

Submission status: Accepted

Solution code:
from collections import deque

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

minList = deque()
maxList = deque()
ascList = deque()


def add_list(_k, target):
    global p
    global minList
    global maxList
    global ascList
    while len(minList) > 0 and p[minList[-1]] >= p[target]:
        minList.pop()
    minList.append(target)
    if minList[0] == target - _k:
        minList.popleft()
    while len(maxList) > 0 and p[maxList[-1]] <= p[target]:
        maxList.pop()
    maxList.append(target)
    if maxList[0] == target - _k:
        maxList.popleft()
    if target > 0 and p[target] < p[target-1]:
        ascList.append(target-1)
    if len(ascList) > 0 and ascList[0] == target - _k:
        ascList.popleft()


count = 0
ascend = 0
for i in range(k):
    add_list(k, i)

if len(ascList) == 0:
    ascend += 1
else:
    count += 1
for i in range(k, n):
    tail_is_max = False
    if p[i] > p[maxList[0]]:
        tail_is_max = True
    add_list(k, i)
    head_is_min = False
    if p[i-k] < p[minList[0]]:
        head_is_min = True
    if not (tail_is_max and head_is_min):
        if len(ascList) == 0:
            if ascend == 0:
                ascend += 1
        else:
            count += 1

print(count+ascend)

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque

N, K = [int(x) for x in stdin.readline().rstrip().split()]
P = [int(x) for x in stdin.readline().rstrip().split()]

ans = N - K + 1

D = deque([x for x in P[:K]])
oc = 0
ordered_twice = False

for i in range(len(D) - 1):
    if D[i] <= D[i + 1]:
        oc += 1

Q = deque([])
Q_min = []
Q_max = []

for i in range(N):
    while len(Q) > 0 and P[Q[len(Q) - 1]] >= P[i]:
        Q.pop()
    Q.append(i)
    if Q[len(Q) - 1] >= K - 1:
        Q_min.append(P[Q[0]])
        if Q[0] == i + 1 - K:
            Q.popleft()

PP = [-x for x in P]
Q = deque([])

for i in range(N):
    while len(Q) > 0 and PP[Q[len(Q) - 1]] >= PP[i]:
        Q.pop()
    Q.append(i)
    if Q[len(Q) - 1] >= K - 1:
        Q_max.append(-PP[Q[0]])
        if Q[0] == i + 1 - K:
            Q.popleft()

for i in range(N - K + 1):
    if i > 0:
        D.popleft()
        D.append(P[i + K - 1])
        if P[i - 1] <= D[0]:
            oc -= 1
        if D[K - 2] <= D[K - 1]:
            oc += 1

        if (Q_min[i - 1] == P[i - 1] and Q_max[i] == D[-1]) or (oc == K - 1 and ordered_twice):
            ans -= 1

    if oc == K - 1:
        ordered_twice = True

print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
P = list(map(int, input().split()))
INF = float('inf')
num = 2**(N-1).bit_length()
segmin = [INF] * num*2
segmax = [-INF] * num*2
for i in range(N):
    segmin[num + i - 1] = P[i]
    segmax[num + i - 1] = P[i]
for i in range(num-2, -1, -1):
    segmin[i] = min(segmin[2*i+1], segmin[2*i+2])
    segmax[i] = max(segmax[2*i+1], segmax[2*i+2])

def query(seg, f, boundary, p, q):
    p += num-1
    q += num-2
    res=boundary
    while q-p>1:
        if p&1 == 0:
            res = f(res,seg[p])
        if q&1 == 1:
            res = f(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = f(res,seg[p])
    else:
        res = f(f(res,seg[p]),seg[q])
    return res

ans = 1
for i in range(N-K):
    if not (P[i] < query(segmin, min, INF, i+1, i+K) and P[i+K] > query(segmax, max, -INF, i+1, i+K)):
        ans += 1

# 昇順にならんでいるケース
combo = 0
nord = 0
for i in range(1,N):
    if P[i] > P[i-1]:
        combo += 1
    else:
        combo = 0
    if combo == K-1:
        nord += 1

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

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
P = [float('inf')]+list(map(int,input().split()))+[float('inf')]

A = [0]*N
B = [0]*(N+2)
hoge = 1
for i in range(1,N):
    if P[i] < P[i+1]:
        hoge += 1
    else:
        hoge = 1
    if hoge >= K:
        B[i-K+2] = 1
    
for i in range(1,N+1):
    A[P[i]] = i
minL,minR,maxL,maxR = [i-1 for i in range(N+2)],[i+1 for i in range(N+2)],[i-1 for i in range(N+2)],[i+1 for i in range(N+2)]
for i in range(N):
    m = A[i]
    x,y = maxL[m],maxR[m]
    maxL[y] = x
    maxR[x] = y
P[0],P[-1] = -1,-1

for i in range(N-1,-1,-1):
    m = A[i]
    x,y = minL[m],minR[m]
    minL[y] = x
    minR[x] = y
ans = 1
for i in range(1,N-K+1):
    # print(i)
    L,R = i,i+K
    # print(i,P[L],P[R],minR[L],maxL[R],B[i+1])
    if B[i+1] == 0 and (minR[L] <= R or maxL[R] >= L):
        # print(i)
        ans += 1
# print(minR[1:-1])
# print(maxL[1:-1])
if sum(B) and B[1] == 0:
    ans += 1
# print(B)
print(ans)

Submission status: Accepted

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

def init(init_val):
    for i in range(n):
        MI[i+num-1]=init_val[i]
        MA[i+num-1]=init_val[i]    
    for i in range(num-2,-1,-1) :
        MI[i]=min(MI[2*i+1],MI[2*i+2])
        MA[i]=max(MA[2*i+1],MA[2*i+2])
    
def update(k,x):
    k += num-1
    MI[k] = x
    MA[k] = x
    while k+1:
        k = (k-1)//2
        MI[k] = min(MI[k*2+1],MI[k*2+2])
        MA[k] = max(MA[k*2+1],MA[k*2+2])

def rangemin(p,q):
    if q<=p:
        return 1<<100
    p += num-1
    q += num-2
    res= 1<<100
    while q-p>1:
        if p&1 == 0:
            res = min(res,MI[p])
        if q&1 == 1:
            res = min(res,MI[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = min(res,MI[p])
    else:
        res = min(min(res,MI[p]),MI[q])
    return res

def rangemax(p,q):
    if q<=p:
        return -1
    p += num-1
    q += num-2
    res= -1
    while q-p>1:
        if p&1 == 0:
            res = max(res,MA[p])
        if q&1 == 1:
            res = max(res,MA[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,MA[p])
    else:
        res = max(max(res,MA[p]),MA[q])
    return res

#n:リスト長
num =2**(n-1).bit_length()
MI=[1<<100]*2*num
MA=[-1]*2*num

init(p)
a = 0
l = -1
c = 0
for i in range(1,n):
    if p[i-1] > p[i]:
        a = i
    if i >= k-1 and a <= i-k+1:
        if i-l > 1:
            c += 1
        l= i

ans = 1-max(c-1,0)

for i in range(n):
    if i >=k:
        if rangemin(i-k+1,i) < p[i-k] or rangemax(i-k+1,i) > p[i]:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
from operator import lt, gt


def hoge(a, K, op):
    from collections import deque
    dq = deque()
    pop, popleft, append = dq.pop, dq.popleft, dq.append

    for i, v in zip(range(K), a):
        while dq and not op(a[dq[-1]], v):
            pop()
        append(i)

    yield a[dq[0]]

    for i in range(K, len(a)):
        while dq and not op(a[dq[-1]], a[i]):
            pop()
        append(i)
        if dq[0] == i-K:
            popleft()
        yield a[dq[0]]


N, K = map(int, input().split())
a = tuple(map(int, input().split()))

inv_flag = [0]*N

for i, (x, y) in enumerate(zip(a, a[1:]), start=1):
    inv_flag[i] = i if x > y else inv_flag[i-1]

min_coro = hoge(a, K, lt)
max_coro = hoge(a, K, gt)

prev_min, prev_max = next(min_coro), next(max_coro)
ans, flag = inv_flag[K-1] != 0, inv_flag[K-1] == 0

for l, r, x, y in zip(range(1, N), range(K, N), min_coro, max_coro):
    if inv_flag[l] == inv_flag[r]:
        flag = 1
    elif not (prev_min < x and prev_max < y):
        ans += 1

    prev_min, prev_max = x, y

print(ans + flag)

Submission status: Accepted

Solution code:
import sys
from collections import deque

input = sys.stdin.readline

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

def slide_min(P,K):
	q = deque()
	q.append(0)
	slide_minl = []
	for i in range(1,len(P)):
		while P[i]<P[q[-1]]:
			q.pop()
			if len(q)==0: break
		q.append(i)

		if i>=K-1:
			slide_minl.append(P[q[0]])
			if q[0]<=i-K+1:
				q.popleft()

	return slide_minl

def slide_max(P,K):
	q = deque()
	q.append(0)
	slide_maxl = []
	for i in range(1,len(P)):
		while P[i]>P[q[-1]]:
			q.pop()
			if len(q)==0: break
		q.append(i)

		if i>=K-1:
			slide_maxl.append(P[q[0]])
			if q[0]<=i-K+1:
				q.popleft()

	return slide_maxl

minl = slide_min(P,K)
maxl = slide_max(P,K)

if N==K:
	ans = 1
else:
	ans = 1
	for i in range(K,N):
		last = P[i]
		pre = P[i-K]
		if pre!=minl[i-K] or last!=maxl[i-K+1]:
			ans += 1
			# print(i)

	count = 0
	i = 0
	while i<N-1:
		upnum = 0
		while P[i]<P[i+1]:
			upnum += 1
			i += 1
			if i==N-1: break
		if upnum>=K-1:
			count += 1
		i += 1

	ans = ans-max(count-1,0)

print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
P=list(map(int,input().split()))
from collections import deque
smin,smax=deque(),deque()
x,r,r2=0,0,0
for i,p in enumerate(P):
    while len(smin)>0 and P[smin[-1]]>p:
        smin.pop()
    smin.append(i)
    if smin[0]<=i-K:
        smin.popleft()
    while len(smax)>0 and P[smax[-1]]<p:
        smax.pop()
    smax.append(i)
    if smax[0]<=i-K:
        smax.popleft()
    if i>0 and P[i-1]<P[i]:
        x=min(x+1,K-1)
    else:
        x=0
    if i==K-1 or (i>=K and not (P[i-K]<P[smin[0]] and smax[0]==i)):
        if x!=K-1:
            r+=1
        else:
            r2=1
print(r+1 if r2 else r)

Submission status: Accepted

Solution code:
from collections import deque

def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]

n,k=MI()
a=LI()

def slidmin(a,k):
    n=len(a)
    b=[0 for i in range(n-k+1)]
    q=deque()
    for i in range(k):
        while q and a[q[-1]]>=a[i]:
            q.pop()
        q.append(i)
    b[0]=a[q[0]]
    s=len(q)
    for i in range(k,n):
        while q and a[q[-1]]>=a[i]:
            q.pop()
            s-=1
        q.append(i)
        s+=1
        if q[0]<=i-k:
            q.popleft()
            s-=1
        b[i-k+1]=a[q[0]]
    return b

m=slidmin(a,k)
M=[-i for i in slidmin([-i for i in a],k)]
ans=1
p=-1
c=0
for i in range(k):
    if p<a[i]:
        c+=1
    else:
        c=1
    p=a[i]
fl=True if c==k else False

for i in range(n-k):
    if p<a[i+k]:
        c+=1
    else:
        c=1
    p=a[i+k]
    
    inc=1
    if c==k:
        if fl:
            inc=0
        fl=True
    if a[i]==m[i] and a[i+k]==M[i+1]:
        inc=0
    ans+=inc
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
#ts=time.time()
#sys.setrecursionlimit(10**6)
input=sys.stdin.readline
show_flg=False
#show_flg=True

n,k=MI()
a=LI()

def slidmin(a,k):
    n=len(a)
    b=[0 for i in range(n-k+1)]
    q=deque()
    for i in range(k):
        while q and a[q[-1]]>=a[i]:
            q.pop()
        q.append(i)
    b[0]=a[q[0]]
    s=len(q)
    for i in range(k,n):
        while q and a[q[-1]]>=a[i]:
            q.pop()
            s-=1
        q.append(i)
        s+=1
        if q[0]<=i-k:
            q.popleft()
            s-=1
        b[i-k+1]=a[q[0]]
    return b

m=slidmin(a,k)
M=[-i for i in slidmin([-i for i in a],k)]
ans=1
p=-1
c=0
for i in range(k):
    if p<a[i]:
        c+=1
    else:
        c=1
    p=a[i]
fl=True if c==k else False

for i in range(n-k):
    if p<a[i+k]:
        c+=1
    else:
        c=1
    p=a[i+k]
    
    inc=1
    if c==k:
        if fl:
            inc=0
        fl=True
    if a[i]==m[i] and a[i+k]==M[i+1]:
        inc=0
    ans+=inc
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
#ts=time.time()
#sys.setrecursionlimit(10**6)
input=sys.stdin.readline
show_flg=False
#show_flg=True

n,k=MI()
a=LI()
na=[-i for i in a]
qs,ql=[],[]

def slidmin(a,k):
    n=len(a)
    b=[0 for i in range(n-k+1)]
    q=deque()
    for i in range(k):
        #show(q)
        while q and a[q[-1]]>=a[i]:
            q.pop()
        q.append(i)
    b[0]=a[q[0]]
    s=len(q)
    rt=[0 for _ in range(n-k+1)]
    if s==k:
        rt[0]=1
    for i in range(k,n):
        #show(q,i,a[q[0]])
        while q and a[q[-1]]>=a[i]:
            q.pop()
            s-=1
        q.append(i)
        s+=1
        if q[0]<=i-k:
            q.popleft()
            s-=1
        b[i-k+1]=a[q[0]]
    return rt,b

sz,m=slidmin(a,k)
sz,M=slidmin(na,k)
M=[-i for i in M]
ans=1
p=-1
c=0
for i in range(k):
    if p<a[i]:
        c+=1
    else:
        c=1
    p=a[i]
fl=True if c==k else False
show(a)
for i in range(n-k):
    if p<a[i+k]:
        c+=1
    else:
        c=1
    p=a[i+k]
    inc=1
    if c==k:
        if fl:
            inc=0
            show('c==k')
        fl=True
    if a[i]==m[i] and a[i+k]==M[i+1]:
        inc=0
        show('min=m,Max=M')
    show(i,inc)
    ans+=inc
print(ans)

Submission status: Accepted

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

minp=[0]*(n-k+1)
maxp=[0]*(n-k+1)
q1=deque([0])
q2=deque([0])
for i in range(1,k):
    while p[q1[-1]]>p[i]:
        q1.pop()
        if len(q1)==0:
            break
    while p[q2[-1]]<p[i]:
        q2.pop()
        if len(q2)==0:
            break
    q1.append(i)
    q2.append(i)
for i in range(n-k+1):
    minp[i]=p[q1[0]]
    maxp[i]=p[q2[0]]
    if i==n-k:
        break
    if q1[0]==i:
        q1.popleft()
    if q2[0]==i:
        q2.popleft()
    while p[q1[-1]]>p[i+k]:
        q1.pop()
        if len(q1)==0:
            break
    while p[q2[-1]]<p[i+k]:
        q2.pop()
        if len(q2)==0:
            break
    q1.append(i+k)
    q2.append(i+k)

d=[0]*n
d[0]=1
for i in range(1,n):
    if p[i]>p[i-1]:
        d[i]=d[i-1]+1
    else:
        d[i]=1

ans=int(k in d)
if d[k-1]!=k:
    ans+=1
for i in range(n-k):
    if d[i+k]>=k:
        continue
    if not (p[i]==minp[i] and p[i+k]==maxp[i+1]):
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from operator import itemgetter
from fractions import gcd
from math import ceil, floor, sqrt
from copy import deepcopy
from collections import Counter, deque
import heapq
import random
from functools import reduce
sys.setrecursionlimit(200000)
# local only
# if not __debug__:
#     fin = open('in_1.txt', 'r')
#     sys.stdin = fin
# local only
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()
# template

class SparseTable():
    """SparseTable:2の冪乗ごとにテーブルを作成しておいて，min,maxなどを高速に行う。セグ木から更新を除いたもの。"""
    def __init__(self, n, func, default_value):
        self._size = n
        self.func = func
        self.default_value = default_value
        self.log2 = [0 for i in range(n + 1)]
        for i in range(2, n + 1):
            self.log2[i] = self.log2[i >> 1] + 1
        self.table = [[default_value for i in range(n)] for j in range(self.log2[n] + 1)]

    @property
    def size(self):
        return self._size

    def __getitem__(self, i):
        assert(i < self._size)
        return self.table[0][i]

    def __str__(self):
        return str(self.table[0])

    def set(self, i, val):
        assert(i < self._size)
        self.table[0][i] = (val, val)

    def build(self):
        for j in range(self.log2[self._size]):
            w = 1 << j
            for i in range(self._size - (w << 1) + 1):
                self.table[j + 1][i] = self.func(self.table[j][i], self.table[j][i + w])

    def fold(self, l, r):
        if r - l < 1:
            return self.default_value
        assert(l < self._size and r <= self._size)
        j = self.log2[r - l]
        return self.func(self.table[j][l], self.table[j][r - (1 << j)])

    def max(self, l, r):
        return self.fold(l, r)[0]

    def min(self, l, r):
        return self.fold(l, r)[1]

# BEGIN CUT HERE
class UnionFind():
    '''
    UnionFind木

    Parameters
    --------
        n (int): UnionFind木のサイズ

    Methods
    --------
        unite(x: int, y: int) -> None
            ノード x とノード y を結合する
        same(x: int, y: int) -> bool
            ノード x とノード y が同じ集合に属するか判定する
        size(x: int) -> int
            ノード x を含む集合の要素数を返す

    '''

    def __init__(self, n):
        self._data = [-1] * n

    def unite(self, x: int, y: int) -> bool:
        '''x と y を結合'''
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False  # 元々結合されている場合はFalseを返し終了する
        elif self._data[x] > self._data[y]:
            x, y = y, x  # swap
        self._data[x] += self._data[y]
        self._data[y] = x
        return True

    def root(self, x: int) -> int:
        '''ノード x の親を返す'''
        while self._data[x] >= 0:
            x = self._data[x]
        return x

    def same(self, x: int, y: int) -> bool:
        '''x と y が同じグループに属するか判定'''
        return self.root(x) == self.root(y)

    def size(self, x: int) -> int:
        '''x を含むグループのノード数を返す'''
        return -self._data[self.root(x)]
# END CUT HERE


def generate_testcase():
    N = 200000
    K = 10000
    with open('in_1.txt', 'w') as f:
        print(N, K, file=f)
        a = [i for i in range(N)]
        random.shuffle(a)
        print(*a, file=f)

def bruteforce(N, K, P):
    s = set()
    for i in range(N - K + 1):
        d = deepcopy(P)
        d[i:i + K] = sorted(d[i:i + K])
        s.add(''.join(list(map(str, d))))
    return len(s)

def main():
    N, K = mi()
    P = lmi()
    # ba = bruteforce(N, K, P)
    def func(x: tuple, y: tuple):
        return (max(x[0], y[0]), min(x[1], y[1]))
    spt = SparseTable(N, func, (int(-1e9), int(1e9)))
    for i, val in enumerate(P):
        spt.set(i, val)
    spt.build()
    uf = UnionFind(N - K + 1)
    # しゃくとり法
    right = 1  # [0, 1) は確実に条件を満たす
    left = 0
    ans = 0
    s = []
    while left < N - K + 1:
        # right を 1 個進めたものが条件を満たすかどうか
        while (right < N and (right <= left or P[right - 1] < P[right])):
            right += 1
        if right - left >= K:
            s.append(left)
        if left == right:
            right += 1
        left += 1
    if len(s) >= 2:
        for i in range(1, len(s)):
            uf.unite(s[0], s[i])
    for i in range(N - K):
        if P[i] == spt.min(i, i + K + 1) and spt.max(i, i + K + 1) == P[i + K]:
            uf.unite(i, i + 1)
    for i in range(N - K + 1):
        if uf.root(i) == i:
            ans += 1
    print(ans)
    return


if __name__ == '__main__':
    # generate_testcase()
    # import cProfile
    # cProfile.run('main()')
    main()

Submission status: Accepted

Solution code:
from collections import deque

n,k=map(int,input().split())
p=list(map(int,input().split()))+[1000000]

p1=[0]*(n)
pmin=[0]*(n+1)
pmax=[0]*(n+1)

cnt=0

for i in range(n-1):
  if p[i]<p[i+1]:
    cnt+=1
  else:
    cnt=0
  p1[i+1]=cnt

d=deque()
d.append(0)

for i in range(1,k+1):
  if p[d[-1]]<p[i]:
    d.append(i)
  else:
    try:
      while p[d[-1]]>p[i]:
        d.pop()
    except:
      pass
    d.append(i)
pmin[k]=p[d[0]]

for i in range(k+1,n):
  if d[0]==i-(k+1):
    d.popleft()
  if p[d[-1]]<p[i]:
    d.append(i)
  else:
    try:
      while p[d[-1]]>p[i]:
        d.pop()
    except:
      pass
    d.append(i)
  pmin[i]=p[d[0]]


dd=deque()
dd.append(0)

for i in range(1,k+1):
  if p[dd[-1]]>p[i]:
    dd.append(i)
  else:
    try:
      while p[dd[-1]]<p[i]:
        dd.pop()
    except:
      pass
    dd.append(i)
pmax[k]=p[dd[0]]

for i in range(k+1,n):
  if dd[0]==i-(k+1):
    dd.popleft()
  if p[dd[-1]]>p[i]:
    dd.append(i)
  else:
    try:
      while p[dd[-1]]<p[i]:
        dd.pop()
    except:
      pass
    dd.append(i)
  pmax[i]=p[dd[0]]

ans=n-k+1
f=1
ff=[0]*n
for i in range(n):
  if p1[i]>=k-1:
    ff[i]=1
    if f==0:
      ans-=1
    else:
      f=0

for i in range(n-k):
  if p[i]==pmin[i+k] and p[i+k]==pmax[i+k] and ff[i+k]==0:
    ans-=1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import heapq

(n,k),p = [list(map(int, s.split())) for s in open(0)]

p_np = np.array(p)
p_cumsum = (p_np[1:]>p_np[:-1]).cumsum()

_min = [(x,i) for i,x in enumerate(p[:k])]
_max = [(-x,i) for i,x in enumerate(p[:k])]
heapq.heapify(_min)
heapq.heapify(_max)

ans = n - k + 1
no_change = False
if p_cumsum[k-2]==k-1:
    no_change = True

for i in range(n-k):
    decrease = False
    
    heapq.heappush(_min, (p[i+k], i+k))
    heapq.heappush(_max, (-p[i+k], i+k))
    
    while _min[0][1] < i:
        heapq.heappop(_min)
    while _max[0][1] < i:
        heapq.heappop(_max)
    
    if (_min[0][0]==p[i] and -_max[0][0]==p[i+k]):
        ans -= 1
        decrease = True
    
    if p_cumsum[i]+k-1 == p_cumsum[i+k-1]:
        if no_change and not decrease:
            ans -= 1
        no_change = True

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import heapq

(n,k),p = [list(map(int, s.split())) for s in open(0)]

p_np = np.array(p)
p_cumsum = (p_np[1:]>p_np[:-1]).cumsum()

c = [False] * n

_min = p[:k].copy()
_max = [-x for x in p[:k]]
heapq.heapify(_min)
heapq.heapify(_max)

ans = n - k + 1
no_change = False
if p_cumsum[k-2]==k-1:
    no_change = True

for i in range(n-k):
    decrease = False
    
    heapq.heappush(_min, p[i+k])
    heapq.heappush(_max, -p[i+k])
    
    while c[_min[0]]:
        heapq.heappop(_min)
    while c[-_max[0]]:
        heapq.heappop(_max)
    
    if (_min[0]==p[i] and -_max[0]==p[i+k]):
        ans -= 1
        decrease = True
    
    c[p[i]] = True
    
    if p_cumsum[i]+k-1 == p_cumsum[i+k-1]:
        if no_change and not decrease:
            ans -= 1
        no_change = True

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

class SlideMin:
    def __init__(self, leng):
        self.que = deque([])
        self.leng = leng

    def top(self):
        return self.que[0]

    def getQue(self):
        return self.que

    def update(self, index, value=0):
        while self.que:
            if self.que[-1][1] >= value:
                self.que.pop()
            else:
                break

        self.que.append((index, value))

        if self.que[0][0] == index - self.leng:
            self.que.popleft()

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

maxQ = SlideMin(K)
minQ = SlideMin(K)

for i in range(K):
    maxQ.update(i, -P[i])
    minQ.update(i, P[i])

ans = 1
hasSame = False
seq = 1
for i in range(1, K):
    if P[i - 1] < P[i]:
        seq += 1
    else:
        seq = 1
if seq >= K:
    hasSame = True

for left in range(N - K):
    right = left + K

    if P[right - 1] < P[right]:
        seq += 1
    else:
        seq = 1

    maxQ.update(right, -P[right])

    if left == minQ.top()[0] and right == maxQ.top()[0]:
        pass
    else:
        if seq < K:
            ans += 1
        else:
            if not hasSame:
                hasSame = True
                ans += 1

    minQ.update(right, P[right])

print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def ff(n,k,p):
    s = set()
    for i in range(n-k+1):
        t = tuple(p[:i] + sorted(p[i:i+k]) + p[i+k:])
        s.add(t)

    return len(s)

def main():
    n,k = LI()
    p = LI()
    qc = [None] * n
    for i in range(n-1):
        if p[i] > p[i+1]:
            qc[i+1] = True

    ec = -1
    iq = []
    aq = []
    for i in range(k):
        if qc[i]:
            ec = i
        heapq.heappush(iq,p[i])
        heapq.heappush(aq,-p[i])


    r = 0
    if ec > 0:
        r += 1
    s = set()
    for i in range(k,n):
        if qc[i]:
            ec = i
        t = p[i]
        u = p[i-k]
        heapq.heappush(iq,t)
        while iq[0] in s:
            heapq.heappop(iq)
        while -aq[0] in s:
            heapq.heappop(aq)
        heapq.heappush(aq,-t)
        if iq[0] != u or aq[0] != -t:
            if ec > i - k + 1:
                r += 1
        s.add(u)

    rr = 0
    c = 1
    for i in range(1,n):
        if p[i] > p[i-1]:
            c += 1
            if c >= k:
                rr = 1
                break
        else:
            c = 1

    return r + rr


print(main())