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:
inpl = lambda: list(map(int,input().split()))

INF = 2**31-1
class SegmentTree:
    def __init__(self, value, N=0, comp=lambda x,y: x<=y, reverse=False):
        M = max(len(value),N)
        N = 2**(len(bin(M))-3)
        if N < M: N *= 2
        self.N = N
        self.node = [0] * (2*N-1)
        self.reverse = reverse
        for i in range(N):
            self.node[N-1+i] = i
        self.value = [None] * N
        for i, v in enumerate(value):
            self.value[i] = v
        self.comp = lambda x, y: True if y is None else False if x is None else comp(x,y)^reverse
        for i in range(N-2,-1,-1):
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            if self.comp(left_v, right_v):
                self.node[i] = left_i
            else:
                self.node[i] = right_i

    def set_input(self, n, v):
        self.value[n] = v
        i = (self.N-1) + n
        while i > 0:
            i = (i-1)//2
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            if self.comp(left_v, right_v):
                new_i = left_i
            else:
                new_i = right_i
            if new_i == self.node[i] and new_i != n:
                break
            else:
                self.node[i] = new_i

    def get_input(self, n):
        if n is None:
            return None
        else:
            return self.value[n]

#    def get_output(self, a=0, b=-1):
#        return self.get_input(self.get_output_index(a,b))

    def get_output(self, l, r):
        L = l + self.N; R = r + self.N
        if self.reverse:
            s = -INF
        else:
            s = INF
        while L < R:
            if R & 1:
                R -= 1
                if self.reverse:
                    s = max(s, self.value[self.node[R-1]]) 
                else:
                    s = min(s, self.value[self.node[R-1]])

            if L & 1:                    
                if self.reverse:
                    s = max(s, self.value[self.node[L-1]])
                else:
                    s = min(s, self.value[self.node[L-1]])
                L += 1
            L >>= 1; R >>= 1
        return s

    def get_output_index(self,
                         a=0, b=-1,
                         k=0, l=0, r=-1):
        if b < 0:
            b = self.N
        if r < 0:
            r = self.N
        if a <= l and r <= b:
            return self.node[k]
        elif r <= a or b <= l:
            return None
        else:
            left_i = self.get_output_index(a,b,2*k+1,l,(l+r)//2)
            right_i = self.get_output_index(a,b,2*k+2,(l+r)//2,r)
            left_v, right_v = self.get_input(left_i), self.get_input(right_i)
            if left_v is None and right_v is None:
                return None
            elif self.comp(left_v, right_v):
                return left_i
            else:
                return right_i

def get_sequence(arr):
    if len(arr) == 0:
        return [], []
    elements = []
    nums = []
    n = 1
    prev = arr[0]
    for c in arr[1:]:
        if c == prev:
            n += 1
        else:
            elements.append(prev)
            nums.append(n)
            prev = c
            n = 1
    elements.append(prev)
    nums.append(n)
    return elements, nums

N, K = inpl()
P = inpl()
minseg = SegmentTree(P)
maxseg = SegmentTree(P, reverse=True)

ans = 1
for i in range(N-K):
    if P[i] < minseg.get_output(i+1,i+K) and P[i+K] > maxseg.get_output(i+1,i+K):
        pass
    else:
        ans += 1

ordered = [ P[i] < P[i+1] for i in range(N-1)]
elements, nums = get_sequence(ordered)
nums = nums[(elements[0]+1)%2::2]

unchanged = len(list(filter(lambda x: x>=K-1, nums)))
if unchanged > 1:
    ans -= unchanged-1

print(ans)

Submission status: Accepted

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import product, permutations,combinations
import fractions

import sys
def input():
	return sys.stdin.readline().strip()

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

next_small = [N]*N
G = []
heapq.heapify(G)
heapq.heappush(G, (-P[0], 0))
for i in range(1, N):
	judge = 0
	while judge == 0 and len(G) > 0:
		num = heapq.heappop(G)
		if -num[0] < P[i]:
			heapq.heappush(G, num)
			judge = 1
		else:
			next_small[num[1]] = i
	heapq.heappush(G, (-P[i], i))

before_large = [-1]*N
G = []
heapq.heapify(G)
heapq.heappush(G, (P[N - 1], N - 1))
for i in range(N - 2, -1, -1):
	judge = 0
	while judge == 0 and len(G) > 0:
		num = heapq.heappop(G)
		if num[0] > P[i]:
			heapq.heappush(G, num)
			judge = 1
		else:
			before_large[num[1]] = i
	heapq.heappush(G, (P[i], i))

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

num = 0
zero = 0
if inc[K - 1] >= K:
	zero += 1

for i in range(1, N - K + 1):
	#print(i + K - 1)
	if inc[i + K - 1] >= K:
		zero += 1
	elif next_small[i - 1] >= i - 1 + K and before_large[i + K - 1] <= i - 1:
		num += 1

#print(inc, next_small, before_large)
print(N - K + 1 - num - max(0, (zero - 1)))

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
raw = list(map(int,input().split()))
num = 2**(n-1).bit_length()
seg1 = [0]*2*num
seg2 = [n]*2*num

def build(raw):
    for i in range(n):
        seg1[i+num-1] = raw[i]
        seg2[i+num-1] = raw[i]
    for i in range(num-2,-1,-1):
        seg1[i] = max(seg1[2*i+1],seg1[2*i+2])
        seg2[i] = min(seg2[2*i+1],seg2[2*i+2])
    return True

build(raw)
cnt = n-k+1

def query(seg,ele,segf,p,q):
    if q <= p:
        return False
    p += num - 1
    q += num - 2
    res = ele
    while q-p > 1:
        if not p%2:
            res = segf(res,seg[p])
        if q%2:
            res = segf(res,seg[q])
            q -= 1
        p //= 2
        q = (q-1)//2
    if p == q:
        res = segf(res,seg[p])
    else:
        res = segf(res,seg[p],seg[q])
    return res

def check(i):
    #print(i,query(seg1,0,max,i,i+k+1),query(seg2,n+1,min,i,i+k+1))
    return query(seg1,0,max,i,i+k+1) == raw[i+k] and query(seg2,n+1,min,i,i+k+1) == raw[i]

t = [0]*n
f = -1
c = -1
for i in range(n):
    if raw[i] > c:
        f += 1
    else:
        f = 0
    c = raw[i]
    t[i] = f

c2 = -1
for i in range(n-k):
    if t[i+k-1] - t[i] == k-1:
        c2 += 1
    elif check(i):
        cnt -= 1
if t[n-1] - t[n-k] == k-1:
    c2 += 1
if c2 >= 0:
    cnt -= c2
print(cnt)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        for _ in range(num): return []
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(map(int, input().split())) for _ in range(N)]
        return map(list,zip(*read_all))

#################

class SegmentTree:
    def __init__(self,N,default):
        #演算の定義
        self.op = min
        #初期化の値
        self.default = default
        self.N0 = 2**(N-1).bit_length()
        self.tree = [self.default]*(2*self.N0)
        
    #a_kの値をxに更新
    def update(self,k,x):
        k += self.N0-1
        self.tree[k] = x
        while k >= 0:
            k = (k-1)//2
            self.tree[k] = self.op(self.tree[2*k+1], self.tree[2*k+2])

    #区間[l,r]へのクエリ
    def query(self,l,r):
        L = l + self.N0; R = r + self.N0 + 1 
        s = self.default
        while L < R:
            if R & 1:
                R -= 1
                s = self.op(s,self.tree[R-1])
            if L & 1:
                s = self.op(s,self.tree[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

    #k番目の値を取得
    def get(self,k):
        return self.tree[k+self.N0-1]

class Max_SegmentTree:
    def __init__(self,N,default):
        #演算の定義
        self.op = max
        #初期化の値
        self.default = default
        self.N0 = 2**(N-1).bit_length()
        self.tree = [self.default]*(2*self.N0)
        
    #a_kの値をxに更新
    def update(self,k,x):
        k += self.N0-1
        self.tree[k] = x
        while k >= 0:
            k = (k-1)//2
            self.tree[k] = self.op(self.tree[2*k+1], self.tree[2*k+2])

    #区間[l,r]へのクエリ
    def query(self,l,r):
        L = l + self.N0; R = r + self.N0 + 1 
        s = self.default
        while L < R:
            if R & 1:
                R -= 1
                s = self.op(s,self.tree[R-1])
            if L & 1:
                s = self.op(s,self.tree[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

    #k番目の値を取得
    def get(self,k):
        return self.tree[k+self.N0-1]

from bisect import bisect_left

N,K = II()
P = III()

seg = SegmentTree(N,N+1)
for i in range(N):
    seg.update(i,P[i])

kmin = [False]*N
for i in range(N-K+1):
    a = seg.query(i,i+K-1)
    if a==P[i]:
        kmin[i] = True

seg2 = Max_SegmentTree(N,-1)
for i in range(N):
    seg2.update(i,P[i])

kmax = [False]*N
for i in range(K-1,N):
    a = seg2.query(i-K+1,i)
    if a==P[i]:
        kmax[i] = True

dp = [0]*N
dp[K-1] = 1
flag = True
bad_p = []
for i in range(K-1):
    if P[i]>P[i+1]:
        flag = False
for i in range(N-1):
    if P[i]>P[i+1]:
        bad_p.append(i)

for i in range(K,N):
    now_flag = False
    if kmax[i]:
        if kmin[i-K]:
            dp[i] = dp[i-1]
        else:
            l = bisect_left(bad_p,i-K+1)
            r = bisect_left(bad_p,i)
            if l==r:
                now_flag = True
            if flag and now_flag:
                dp[i] = dp[i-1]
            else:
                dp[i] = dp[i-1]+1
    else:
        dp[i] = dp[i-1]+1

    if now_flag:
        flag = True

print(dp[N-1])

Submission status: Accepted

Solution code:

import heapq

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

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

minlis = []
maxlis = []
endflag = [False] * N

ans = 1

for i in range(K):

    heapq.heappush(minlis,P[i])
    heapq.heappush(maxlis,-1 * P[i])

for i in range(N - K):

    flag = False

    endflag[P[i]] = True
    if minlis[0] != P[i]:
        flag = True

    while endflag[minlis[0]]:
        heapq.heappop(minlis)

    if P[i+K] <= -1 * maxlis[0]:
        flag = True

    while endflag[-1 * maxlis[0]]:
        heapq.heappop(maxlis)

    

    heapq.heappush(minlis,P[i+K])
    heapq.heappush(maxlis,-1 * P[i+K])



    if flag:
        ans += 1

kaburi = 0
P.append(-2)
now = 0
nmax = -1
for i in range(N+1):
    if nmax < P[i]:
        now += 1
        nmax = P[i]
    else:
        if now >= K:
            kaburi += 1 #max(0 , now - K + 1)
        now = 1
        nmax = P[i]
        
#print (ans,kaburi)
if kaburi >= 2:
    print (ans - kaburi + 1)
else:
    print (ans)

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush

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

increases = [int(p1 < p2) for p1, p2 in zip(ppp, ppp[1:])]
h = k - 1
tmp = sum(increases[:h])
duplicated = [0] * n
first_ascending = True
for i, q in enumerate(increases[h:], start=h):
    tmp += q - increases[i - h]
    if tmp == h:
        if first_ascending:
            first_ascending = False
        else:
            duplicated[i + 1] = 1

state = [1] * k + [0] * (n - k)
ans = 1
minq = ppp[:k]
maxq = [-p for p in ppp[:k]]
heapify(minq)
heapify(maxq)

# print(duplicated)

for i, p in enumerate(ppp[k:], start=k):
    l = ppp[i - k]

    if l == minq[0] and p > -maxq[0]:
        pass
    elif duplicated[i] == 1:
        pass
    else:
        ans += 1
    state[l] = 2
    state[p] = 1
    while state[minq[0]] == 2:
        heappop(minq)
    while state[-maxq[0]] == 2:
        heappop(maxq)
    heappush(minq, p)
    heappush(maxq, -p)
    # print(i, p, ans)
    # print(state)
    # print(minq)
    # print(maxq)

print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    h,w,a,b = LI()
    ans = [1]*a+[0]*(w-a)
    ans_ = [0]*a+[1]*(w-a)
    for i in range(h):
        if i < b:
            print(*ans,sep = "")
        else:
            print(*ans_,sep = "")
    return

#B
def B():
    class SegmentTree:
        def __init__(self, size, default, op = min):
            self.size = 2**size.bit_length()
            self.dat = [default]*(self.size*2)
            self.op = op

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

        def add(self, i, x):
            i += self.size
            self.dat[i] = self.op(self.dat[i], x)
            while i > 0:
                i >>= 1
                self.dat[i] = self.op(self.dat[i], x)

        def get(self, a, b = None):
            if b is None:
                b = a + 1
            l, r = a + self.size, b + self.size
            res = None
            while l < r:
                if l & 1:
                    if res is None:
                        res = self.dat[l]
                    else:
                        res = self.op(res, self.dat[l])
                    l += 1

                if r & 1:
                    r -= 1
                    if res is None:
                        res = self.dat[r]
                    else:
                        res = self.op(res, self.dat[r])
                l >>= 1
                r >>= 1
            return res
    n,k = LI()
    p = LI()
    for i in range(n):
        p[i] += 1
    mi = SegmentTree(n,n,min)
    ma = SegmentTree(n,0,max)
    for i in range(n):
        mi.update(i,p[i])
        ma.update(i,p[i])
    min_p = [mi.get(i,i+k) for i in range(n-k+1)]
    max_p = [ma.get(i,i+k) for i in range(n-k+1)]
    s = 1
    for i in range(k-1):
        if p[i] < p[i+1]:
            s += 1
        else:
            s = 1
    ans = 1
    a = s >= k
    f = 0
    for i in range(1,n-k+1):
        if p[i+k-2] < p[i+k-1]:
            s += 1
        else:
            s = 1
        if s >= k:
            f |= 1
            continue
        elif min_p[i-1] != p[i-1] or max_p[i] != p[i+k-1]:
            ans += 1
    if not a and f:
        ans += 1
    print(ans)
    return
def B_():
    n,k = LI()
    p = LI()
    for i in range(n-k+1):
        print(i)
        s = p[i:i+k]
        s.sort()
        print(p[:i]+s+p[i+k:])
#C
def C():

    return

#D
def D():

    return

#E
def E():

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    B()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)


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


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'))

size = N - K + 1
UF = list(range(size))
SIZE = [1] * size  # 0-indexed


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


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


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):
        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:
    unite(incK[0], i)

scan_uf()
print(len(set(UF)))

Submission status: Accepted

Solution code:
def init(seg,init_val,n,num):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=min(seg[2*i+1],seg[2*i+2]) 
    return seg
    
def query(seg,p,q,n,num):
    if q<=p:
        return float("inf")
    p += num-1
    q += num-2
    res=float("inf")
    while q-p>1:
        if p&1 == 0:
            res = min(res,seg[p])
        if q&1 == 1:
            res = min(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = min(res,seg[p])
    else:
        res = min(min(res,seg[p]),seg[q])
    return res

def init2(seg,init_val,n,num):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i] = max(seg[2*i+1],seg[2*i+2]) 
    return seg
    
def query2(seg,p,q,n,num):
    ide_ele = -float("inf")
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = max(res,seg[p])
        if q&1 == 1:
            res = max(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,seg[p])
    else:
        res = max(max(res,seg[p]),seg[q])
    return res


def main():
    import sys
    input = sys.stdin.readline
    N,K = map(int,input().split())
    P = list(map(int,input().split()))
    
    num =2**(N-1).bit_length()
    seg1=[float("inf")]*2*num
    seg1 = init(seg1,P,N,num)
    seg2=[-float("inf")]*2*num
    seg2 = init2(seg2,P,N,num)
    
    ans = 1
    c = 0
    tmp = 0
    for i in range(N-1):
        if P[i]<P[i+1]:
            tmp += 1
        else:
            if tmp >= K-1:
                c += 1
            tmp = 0
    if tmp >= K-1:
        c += 1
        tmp = 0
        
        
    for i in range(N-K):
        m = query(seg1, i, i+K+1,N,num)
        M = query2(seg2, i, i+K+1,N,num)
        if P[i]!=m or P[i+K]!=M:
            ans += 1
    
    print(ans- max(0,c-1))
        
    
    
main()

Submission status: Accepted

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

# N:  処理する区間の長さ
N0 = 2**(N-1).bit_length()
INF = 10**6
seg_min = [INF]*(2*N0)
seg_max = [-INF]*(2*N0)


def update(index, value):
    index += N0 - 1
    seg_min[index] = value
    seg_max[index] = value
    while index > 0:
        index = (index - 1) // 2
        seg_min[index] = min(seg_min[index * 2 + 1], seg_min[index * 2 + 2])
        seg_max[index] = max(seg_max[index * 2 + 1], seg_max[index * 2 + 2])


def query(first, last):
    first += N0 - 1
    last += N0 - 1
    ret_min = INF
    ret_max = -INF
    while first <= last:
        if not first & 1:
            ret_min = min(ret_min, seg_min[first])
            ret_max = max(ret_max, seg_max[first])
        if last & 1:
            ret_min = min(ret_min, seg_min[last])
            ret_max = max(ret_max, seg_max[last])
        first = first // 2
        last = last // 2 - 1
    return ret_min, ret_max


for i in range(N):
    update(i, P[i])

ans = 1
for i in range(1, N - K + 1):
    s, b = query(i-1, K+i-1)
    # print(s, b, P[i - 1], P[K + i - 1])
    if s != P[i-1] or b != P[K+i-1]:
        ans += 1

kaburi = 0
cnt = 0
for i in range(1, N):
    if P[i-1] < P[i]:
        cnt += 1
    else:
        cnt = 0
    if cnt == K-1:
        kaburi += 1
kaburi = max(0, kaburi - 1)

print(ans - kaburi)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

from collections import deque

N,K,*P=map(int,sys.stdin.read().split())

Kmin = []
deq = deque()
for i in range(K):
    while deq and P[deq[-1]] > P[i]:
        deq.pop()
    deq.append(i)
Kmin.append(deq[0])
for i in range(K,N):
    if deq[0] == i-K:
        deq.popleft()
    while deq and P[deq[-1]] > P[i]:
        deq.pop()
    deq.append(i)
    Kmin.append(deq[0])

Kmax = []
deq = deque()
for i in range(K):
    while deq and P[deq[-1]] < P[i]:
        deq.pop()
    deq.append(i)
Kmax.append(deq[0])
for i in range(K,N):
    if deq[0] == i-K:
        deq.popleft()
    while deq and P[deq[-1]] < P[i]:
        deq.pop()
    deq.append(i)
    Kmax.append(deq[0])

is_new_seq = [Kmin[i] != i or Kmax[i+1] != i+K for i in range(N-K)]

is_new_seq

import itertools
incr = [1 if x<y else 0 for x,y in zip(P,P[1:])]
incr_cum = [0] + list(itertools.accumulate(incr))
is_stable = [y-x==K-1 for x,y in zip(incr_cum,incr_cum[K-1:])]

is_new_seq = [x&(not y) for x,y in zip(is_new_seq,is_stable[1:])]

answer = sum(is_new_seq)
if not is_stable[0]:
    answer += 1
    if any(is_stable):
        answer += 1
else:
    answer += 1
print(answer)

Submission status: Accepted

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

def init_max(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=max(seg[2*i+1],seg[2*i+2]) 
    
def update_max(k,x):
    k += num-1
    seg[k] = x
    while k+1:
        k = (k-1)//2
        seg[k] = max(seg[k*2+1],seg[k*2+2])
    
def query_max(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = max(res,seg[p])
        if q&1 == 1:
            res = max(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,seg[p])
    else:
        res = max(max(res,seg[p]),seg[q])
    return res

def init_min(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=min(seg[2*i+1],seg[2*i+2]) 
    
def update_min(k,x):
    k += num-1
    seg[k] = x
    while k+1:
        k = (k-1)//2
        seg[k] = min(seg[k*2+1],seg[k*2+2])
    
def query_min(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = min(res,seg[p])
        if q&1 == 1:
            res = min(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = min(res,seg[p])
    else:
        res = min(min(res,seg[p]),seg[q])
    return res


#####単位元######
ide_ele = -1

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

init_max(p)

a = [-1]*(n-k+1)
for i in range(n-k+1):
    a[i] = query_max(i,i+k)

#####単位元######
ide_ele = n

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

init_min(p)

b = [-1]*(n-k+1)
for i in range(n-k+1):
    b[i] = query_min(i,i+k)

c = [1]*n
d = [True]*n
for i in range(n-2,-1,-1):
    if p[i] < p[i+1]:
        c[i] = c[i+1]+1
        if c[i] >= k:
            d[i] = False



res = 0
res2 = 0


for i in range(n-k):
    if not d[i]:
        res2 = 1
        continue
    if b[i] == p[i] and a[i+1] == p[i+k]:
        continue
    res += 1
if d[n-k]:
    res += 1

if n==k:
    print(1)
else:
    print(res+res2)

Submission status: Accepted

Solution code:
import sys
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

class Searchable_BIT():
    def __init__(self,N):
        self.N = N
        self.node = [0]*(self.N+1)
        self.cnt = 0

    def add(self,a): # 要素 x を追加
        x = a
        self.cnt += 1
        while x <= self.N:
            self.node[x] += 1
            x += x & -x

    def delete(self,x): # 要素 x を削除
        self.cnt -= 1
        while x <= self.N:
            self.node[x] -= 1
            x += x & -x

    def count(self,x): # x以下の要素数
        tmp = 0
        while x > 0:
            tmp += self.node[x]
            x -= x & -x
        return tmp

    def get_maxval(self):
        return self.get_lower_i(self.cnt)

    def get_lower_i(self,i): # i 番目に小さい要素を取得
        NG = -1
        OK = self.N
        while OK-NG > 1:
            mid = (OK+NG)//2
            #print(OK,NG,self.count(mid))
            if self.count(mid) >= i:
                OK = mid
            else:
                NG = mid
        return OK

N,K = inpl()
PP = inpl()

BIT = Searchable_BIT(N+1)
for i in range(1,K):
    BIT.add(PP[i]+1)

ans = [i for i in range(N-K+1)]

cnt = 1
for i in range(N-1):
    if PP[i] < PP[i+1]:
        cnt += 1
    else:
        cnt = 1
    if cnt >= K:
        ans[i-K+2] = -1

for i in range(N-K):
    L,R = PP[i]+1,PP[i+K]+1
    MIN,MAX = BIT.get_lower_i(1), BIT.get_maxval()
    if L <= MIN and MAX <= R:
        ans[i+1] = ans[i]
    BIT.delete(PP[i+1]+1)
    BIT.add(PP[i+K]+1)

print(len(set(ans)))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

# Segment tree(1-indexed,再帰を使わないもの,最小値を求める)

seg_el=1<<(N.bit_length())# Segment treeの台の要素数
SEG=[1<<30]*(2*seg_el)# 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化

for i in range(N):# Aを対応する箇所へupdate
    SEG[i+seg_el]=A[i]

for i in range(seg_el-1,0,-1):# 親の部分もupdate
    SEG[i]=min(SEG[i*2],SEG[i*2+1])

def update(n,x,seg_el):# A[n]をxへ更新（反映）
    i=n+seg_el
    SEG[i]=x
    i>>=1# 子ノードへ
    
    while i!=0:
        SEG[i]=min(SEG[i*2],SEG[i*2+1])
        i>>=1
        
def getvalues(l,r):# 区間[l,r)に関するminを調べる
    L=l+seg_el
    R=r+seg_el
    ANS=1<<30

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

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

    return ANS

SEG2=[1<<30]*(2*seg_el)# 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化

for i in range(N):# Aを対応する箇所へupdate
    SEG2[i+seg_el]=A[i]

for i in range(seg_el-1,0,-1):# 親の部分もupdate
    SEG2[i]=max(SEG2[i*2],SEG2[i*2+1])

def update2(n,x,seg_el):# A[n]をxへ更新（反映）
    i=n+seg_el
    SEG2[i]=x
    i>>=1# 子ノードへ
    
    while i!=0:
        SEG2[i]=max(SEG2[i*2],SEG2[i*2+1])
        i>>=1
        
def getvalues2(l,r):# 区間[l,r)に関するmaxを調べる
    L=l+seg_el
    R=r+seg_el
    ANS=-1

    while L<R:
        if L & 1:
            ANS=max(ANS , SEG2[L])
            L+=1

        if R & 1:
            R-=1
            ANS=max(ANS , SEG2[R])
        L>>=1
        R>>=1

    return ANS

# UnionFind

Group=[i for i in range(N-K+1)]# グループ分け.Group[i]=jのときiとjは同じグループ

def find(x):# find(a)=find(b)のとき同じグループ
    if Group[x]==-1:
        return -1
    
    while Group[x] != x:
        x=Group[x]
    return x

def Union(x,y):  # xとyが同じグループになるよう更新
    if find(x) != find(y):
        Group[find(y)]=Group[find(x)]=min(find(y),find(x))

count=0
for i in range(1,N):
    if A[i]>A[i-1]:
        count+=1
    else:
        count=0
    if count>=K-1:
        Group[i-K+1]=-1
    

for i in range(N-K):
    if A[i]<getvalues(i+1,i+K)<getvalues2(i+1,i+K)<A[i+K]:
        Union(i,i+1)

B=[find(x) for x in range(N-K+1)]
#print(B)
print(len(set(B)))

Submission status: Accepted

Solution code:
NN = 18
MA = [-1] * ((1<<NN+1)-1)
MI = [1<<100] * ((1<<NN+1)-1)
 
def update(a, x):
    i = (1<<NN) - 1 + a
    MI[i] = x
    MA[i] = x
    while True:
        i = (i-1) // 2
        MI[i] = min(MI[2*i+1], MI[2*i+2])
        MA[i] = max(MA[2*i+1], MA[2*i+2])
        if i == 0:
            break
def rangemin(a, b):
    l = a + (1<<NN)
    r = b + (1<<NN)
    mi = 1<<100
    while l < r:
        if l%2:
            mi = min(mi, MI[l-1])
            l += 1
        if r%2:
            r -= 1
            mi = min(mi, MI[r-1])
        l >>= 1
        r >>= 1
    return mi
def rangemax(a, b):
    l = a + (1<<NN)
    r = b + (1<<NN)
    ma = -1
    while l < r:
        if l%2:
            ma = max(ma, MA[l-1])
            l += 1
        if r%2:
            r -= 1
            ma = max(ma, MA[r-1])
        l >>= 1
        r >>= 1
    return ma

N, K = map(int, input().split())
A = [int(a) for a in input().split()]
a = 0
l = -1
cnt = 0
for i in range(1, N):
    if A[i-1] > A[i]:
        a = i
    if i >= K-1 and a <= i - K + 1:
        if i - l > 1:
            cnt += 1
        l = i
ans = 1 - max(cnt-1, 0)
for i in range(N):
    update(i, A[i])
    if i >= K:
        mi = rangemin(i-K, i)
        ma = rangemax(i-K+1, i+1)
        if mi != A[i-K] or ma != A[i]:
            ans += 1

print(ans)