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:
n,k = map(int,input().split())
p = tuple(map(int,input().split()))

class Seg_min():
    def __init__(self,x):
        #####単位元######
        self.ide_ele_min = 10**10
        self.func = min

        self.n = len(x)

        #num_max:n以上の最小の2のべき乗
        self.num_max =2**(self.n-1).bit_length()
        self.x = [self.ide_ele_min]*2*self.num_max

        for i,num in enumerate(x, self.num_max):
            self.x[i] = num
        for i in range(self.num_max-1,0,-1):
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def update(self,i,x):
        i += self.num_max
        self.x[i] = x
        while(x>0):
            i = i//2
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def query(self,i,j):
        res = self.ide_ele_min
        if i>=j:
            return res
        i += self.num_max
        j += self.num_max -1
        while(i<=j):
            if(i==j):
                res = self.func(res,self.x[i])
                break
            if(i&1):
                res = self.func(res,self.x[i])
                i += 1
            if(not j&1):
                res = self.func(res,self.x[j])
                j -= 1
            i = i>>1
            j = j>>1
        return res

class Seg_max():
    def __init__(self,x):
        #####単位元######
        self.ide_ele_min = 10**10 * -1
        self.func = max

        self.n = len(x)

        #num_max:n以上の最小の2のべき乗
        self.num_max =2**(self.n-1).bit_length()
        self.x = [self.ide_ele_min]*2*self.num_max

        for i,num in enumerate(x, self.num_max):
            self.x[i] = num
        for i in range(self.num_max-1,0,-1):
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def update(self,i,x):
        i += self.num_max
        self.x[i] = x
        while(x>0):
            i = i//2
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def query(self,i,j):
        res = self.ide_ele_min
        if i>=j:
            return res
        i += self.num_max
        j += self.num_max -1
        while(i<=j):
            if(i==j):
                res = self.func(res,self.x[i])
                break
            if(i&1):
                res = self.func(res,self.x[i])
                i += 1
            if(not j&1):
                res = self.func(res,self.x[j])
                j -= 1
            i = i>>1
            j = j>>1
        return res

seg_min = Seg_min(p)
seg_max = Seg_max(p)

natural = 0
ans = 0

head = 0
for i in range(1,n):
    if(p[i]<p[i-1]):
        head = i

    if(i-head >= k-1):
        natural = 1
        continue

    if(i==k-1):
        ans +=1
    if(i<k):
        continue
    ans += 1

    left = seg_min.query(i-k,i)
    right = seg_max.query(i-k+1,i+1)
    if(left==p[i-k])&(right==p[i]):
        ans -= 1

print(ans+natural)

Submission status: Accepted

Solution code:
from collections import deque

def slide_max(A, K):
    N = len(A)
    max_idx = [0] * N
    d = deque()
    for i in range(N):
        while d and d[0] <= i-K:
            d.popleft()
        while d and A[d[-1]] < A[i]:
            d.pop()
        d.append(i)
        max_idx[i] = d[0]
    return max_idx


def slide_min(A, K):
    N = len(A)
    min_idx = [0] * N
    d = deque()
    for i in range(N):
        while d and d[0] <= i-K:
            d.popleft()
        while d and A[d[-1]] > A[i]:
            d.pop()
        d.append(i)
        min_idx[i] = d[0]
    return min_idx

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

larger_than_left = [1] * N
for i in range(1, N):
  if A[i] < A[i-1]:
    larger_than_left[i] = 0

sorted_idx = set()
num = sum(larger_than_left[1:K])
if num == K-1:
  sorted_idx.add(0)
for i in range(1, N-K+1):
  num += larger_than_left[i+K-1] - larger_than_left[i]
  if num == K-1:
    sorted_idx.add(i)

max_idx = slide_max(A, K-1)
min_idx = slide_min(A, K-1)
ans = [] if 0 in sorted_idx else [0]
for i in range(1, N-K+1):
  if i in sorted_idx:
    continue
  left = A[i-1]
  right = A[i+K-1]
  M = A[max_idx[i+K-2]]
  m = A[min_idx[i+K-2]]
  if m < left or right < M:
    ans.append(i)

print(len(ans) + (len(sorted_idx)>0))

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    inf=10**6
    N,K=MI()
    P=LI()
    inf=10**6
    class SegTree:
        def __init__(self,N,ide,segfunc=min):
            self.ide_ele = ide
            """
            ex)
             最小値のセグ木 → +inf
              和のセグ木 → 0
              積のセグ木 → 1
              gcdのセグ木 → 0
            """
            
            self.segfunc=segfunc
            
            #num:N以上の最小の2のべき乗
            self.num =2**(N-1).bit_length()
            self.seg=[self.ide_ele]*2*self.num




        #リストで初期化する
        def setL(self,init_val):
            #init_valは操作する数列
            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.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 


        #k番目の値をxに更新
        def update(self,k,x):
            k += self.num-1
            self.seg[k] = x
            while k:
                k = (k-1)//2
                self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])


        #[p,q)の区間に対するクエリへの応答
        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



    
    """
    長さKの尺取りぽく見るか．
    最小値が抜けて最大値が入る場合は不変．
    ただし，並び替え後も元の物と変わらない場合を何度かカウントしそう．
    事前に（元から昇順になっている長さKの列）の個数を数えておこうか．
    後からこれを引くのはダメ，事前に計算しておかないと，すでに照準になっているものを数えているのか数えていないのか不明になる．
    
    これは簡単に求まる．次が自分以上なら1をつけて，長さKの尺取りで和がKならおk．
    累積和の方が実装が楽かなあ
    """
    ans=1#最初のK個を並び替えたものは無条件で数える
    mseg=SegTree(N,inf,min)
    Mseg=SegTree(N,-1,max)
    mseg.setL(P)
    Mseg.setL(P)
    
    #累積和パート
    S=[0]*(N+1)
    for i in range(N-1):
        if P[i]<P[i+1]:
            S[i+1]=1
    #print(S)
            
    for i in range(N):
        S[i+1]+=S[i]
    
    m=min(P[:K])
    M=max(P[:K])
    cnt=0#最初と同じ配列のものを何回数えたか
    if S[K]==K:#最初のKこを並び替えたものを1回とすでに数えてしまっているのでチェック
        cnt+=1
        
    for i in range(K,N):
        if m==P[i-K] and P[i]>M:#最小値が抜けて，新しく入るのが最大値を更新するなら
            m=mseg.query(i-K+1,i+1)
            M=P[i]
        else:
            m=mseg.query(i-K+1,i+1)
            M=Mseg.query(i-K+1,i+1)
            #print(i,S[i]-S[i-K+1],S[i],S[i-K+1])
            if cnt==0:
                ans+=1
            elif S[i]-S[i-K+1]!=(K-1):
                ans+=1
            if S[i]-S[i-K+1]==(K-1):
                cnt+=1
                
        #print(i,m,M,ans,cnt)

            
    print(ans)
    #print(S)

main()

Submission status: Accepted

Solution code:
class UnionFind:
    """
    sizeによる実装
    """

    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.size = [1 for _ in range(N)]

    def find(self, x):
        """
        x: child
        ret-> node
        xのグループの代表を見つける
        """
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])

    def union(self, x, y):
        """
        union (x ,y)
        x,y: node
        ret->None
        """
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.size[px] < self.size[py]:
            self.parent[px] = py
            self.size[py] += self.size[px]
        else:
            self.parent[py] = px
            self.size[px] += self.size[py]

    def same(self, x, y):
        """
        return true if x and y are in same group
        """
        return self.find(x) == self.find(y)

    def connectedNum(self, x):
        """
        return size of the group x belong to
        """
        return self.size[self.find(x)]

    def is_connected(self):
        """
        return true is all node is in one group
        """
        return self.connectedNum(0) == len(self.parent)

    def componentNum(self):
        """
        return componentNum
        """
        par_set=set()
        for p in self.parent:
            par_set.add(self.find(p))
        return len(par_set)

class SegmentTree():
    '''
    非再帰
    segment tree
    '''

    def __init__(self, n, func, init=float('inf')):
        '''
        n->配列の長さ
        func:func(a,b)->val,　func=minだとRMQになる
        木の高さhとすると,
        n:h-1までのノード数。h段目のノードにアクセスするために使う。
        data:ノード。
        parent:k->child k*2+1とk*2+2
        '''
        self.n = 2**(n-1).bit_length()
        self.init = init
        self.data = [init]*(2*self.n)
        self.func = func

    def set(self, k, v):
        '''
        あたいの初期化
        '''
        self.data[k+self.n-1] = v

    def build(self):
        '''
        setの後に一斉更新
        '''
        for k in reversed(range(self.n-1)):
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def update(self, k, a):
        '''
        list[k]=aに更新する。
        更新ぶんをrootまで更新
        '''
        k += self.n-1
        self.data[k] = a

        while k > 0:
            k = (k-1)//2
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def query(self, l, r):
        '''
        [l,r)のfuncを求める
        '''
        L = l+self.n
        R = r+self.n
        ret = self.init
        while L < R:
            if R & 1:
                R -= 1
                ret = self.func(ret, self.data[R-1])
            if L & 1:
                ret = self.func(ret, self.data[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return ret


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


Seg_min = SegmentTree(N,min)
Seg_max = SegmentTree(N,max,0)
for i,p in enumerate(P):
    Seg_min.set(i,p)
    Seg_max.set(i,p)
Seg_min.build()
Seg_max.build()

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

for i in range(N):
    if inc[i+1]!=0:
        inc[i+1]+=inc[i]

Un=UnionFind(N-K+1)
sorted_seg_par=None

for i in range(N-K+1):
    #start=iとする
    if inc[i+K-1]>=K-1:#[i,i+K]はsorted
        if sorted_seg_par is None:
            sorted_seg_par=i
        else:
            Un.union(sorted_seg_par,i)
    elif i+1<N-K+1 and P[i]==Seg_min.query(i,i+K+1) and P[i+K]==Seg_max.query(i,i+K+1):#[i,i+K]と[i+1,i+K+1]はequivalent
        Un.union(i,i+1)
print(Un.componentNum())

Submission status: Accepted

Solution code:
# AGC038B
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


from queue import deque
from collections import defaultdict
n, k = map(int, input().split())
p = list(map(int, input().split()))

count = 0
q = deque([])
maxq = deque([])
ren = 0
prev = -1
es = defaultdict(set)
slist = []
for i,num in enumerate(p):
    if i>=k:
        m = p[q[0]]
        M = p[maxq[0]]
        if num>M and m==p[i-k]:
            count += 1
            es[i-k].add(i-k+1)
            es[i-k+1].add(i-k)

    if prev<num:
        ren += 1
        prev = num
        if ren>=k-1:
            slist.append(i-k+1)
    else:
        ren = 0
        prev = num
    
    while q and p[q[-1]]>num:
        q.pop()
    q.append(i)
    if q[0]<=i-k:
        q.popleft()
    while maxq and p[maxq[-1]]<num:
        maxq.pop()
    maxq.append(i)
    if maxq[0]<=i-k:
        maxq.popleft()
if len(slist)>=2:
    for i in range(len(slist)-1):
        es[slist[i]].add(slist[i+1])
        es[slist[i+1]].add(slist[i])
ans = 0   
seen = [False] * n
for i in range(n-k+1):
    if seen[i]:
        continue
    ans += 1
    q = [i]
    seen[i] = True
    while q:
        u = q.pop()
        for v in es[u]:
            if not seen[v]:
                q.append(v)
                seen[v] = True
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from heapq import heappush, heappop
N,K,*P = map(int, open(0).read().split())
i = 0
ans = 1
Cnt = Counter(P[:K])
mls = []
Mls = []
for i in range(K):
  heappush(mls,P[i])
  heappush(Mls,-P[i])
for i in range(N-K):
  Cnt[P[i]] -= 1
  Cnt[P[i+K]] += 1
  if not (P[i]==mls[0] and P[i+K]>=-Mls[0]):
    ans += 1
  heappush(mls,P[i+K])
  heappush(Mls,-P[i+K])
  while Cnt[mls[0]]==0:
    heappop(mls)
  while Cnt[-Mls[0]]==0:
    heappop(Mls)
i = 0
flag = False
for j in range(1,N):
  if P[j]<P[j-1]:
    if j-i>=K:
      ans -= 1
      flag = True
    i = j
if j-i>=K-1:
  flag = True
  ans -= 1
if flag:
  ans += 1
print(ans)

Submission status: Accepted

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

LIS=[1 for i in range(0,N)]
s=0
t=1
while N>t:
    if P[t]>=P[t-1]:
        t+=1
        if t==N:
            ans=N-s
            while t>s:
                LIS[s]=ans
                s+=1
                ans-=1
    else:
        ans=t-s
        while t>s:
            LIS[s]=ans
            s+=1
            ans-=1
        t+=1

nochange=set([])
for i in range(0,N-K+1):
    if LIS[i]>=K:
        nochange.add(i)

n=N
#セグメント木
#####segfunc######
def segfunc(x,y):
    return (min(x[0],y[0]),max(x[1],y[1]))

def init(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]=segfunc(seg[2*i+1],seg[2*i+2])

def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

def query(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 = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
ide_ele =(10**20,0)

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num
PP=[(P[i],P[i]) for i in range(0,N)]
init(PP)
ans=[]
if 0 not in nochange:
    ans.append(0)
for i in range(1,N-K+1):
    if i in nochange:
        continue
    else:
        M=query(i,i+K)[1]
        m=query(i-1,i-1+K)[0]
        if m==P[i-1] and M==P[i+K-1]:
            continue
        else:
            ans.append(i)

if nochange:
    print(len(ans)+1)
else:
    print(len(ans))

Submission status: Accepted

Solution code:
from collections import deque
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = 0
l = [1] * (n - k + 1)
for i in range(k - 1):
    if p[i] > p[i + 1]:
        c += 1
if c == 0:
    l[0] = 0
for i in range(k - 1, n - 1):
    if p[i] > p[i + 1]:
        c += 1
    if p[i - k + 1] > p[i - k + 2]:
        c -= 1
    if c == 0:
        l[i - k + 2] = 0
k -= 1
qa = deque([])
a = [0] * (n - k + 1)
qb = deque([])
b = [0] * (n - k + 1)
for i in range(n):
    while qa and p[qa[-1]] > p[i]:
        qa.pop()
    while qb and p[qb[-1]] < p[i]:
        qb.pop()
    qa.append(i)
    qb.append(i)
    if qa[0] == i - k:
        qa.popleft()
    if qb[0] == i - k:
        qb.popleft()
    if i >= k - 1:
        a[i - k + 1] = p[qa[0]]
        b[i - k + 1] = p[qb[0]]
ans = l[0]
for i in range(n - k - 1):
    if (p[i] > a[i + 1] or b[i + 1] > p[i + k + 1]) and l[i + 1]:
        ans += 1
print(ans + 1 - min(l))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
P = list(map(int, input().split()))
mn = [N] * (N-K)
mx = [-1] * (N-K)
min_heap = []
max_heap = []
for i in range(K):
    heappush(min_heap, P[i])
    heappush(max_heap, -P[i])
used = set()
for i in range(N-K):
    heappush(min_heap, P[i+K])
    heappush(max_heap, -P[i+K])
    while min_heap[0] in used:
        heappop(min_heap)
    while -max_heap[0] in used:
        heappop(max_heap)
    mn[i] = min_heap[0]
    mx[i] = -max_heap[0]
    used.add(P[i])
ans = 1
for i in range(N-K):
    if P[i] != mn[i] or P[i+K] != mx[i]:
        ans += 1
inc = 1
cnt = 0
for i in range(1, N):
    if P[i-1] < P[i]:
        inc += 1
    else:
        inc = 1
    if inc == K:
        cnt += 1
ans -= max(0, cnt-1)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n,k = map(int,input().split())
a = list(map(int,input().split()))
k -= 1
mnlist = []
q = deque([0])
for i in range(1,k):
  while q:
    x = q.pop()
    if a[i]>a[x]:
      q.append(x)
      q.append(i)
      break
  if not q:
    q.append(i)

for i in range(k,n+1):
  t = q.popleft()
  mnlist.append(a[t])
  if t != i-k:
    q.appendleft(t)
  if i == n:
    break
  while q:
    x = q.pop()
    if a[i]>a[x]:
      q.append(x)
      q.append(i)
      break
  if not q:
    q.append(i)
mxlist = []
q = deque([0])
for i in range(1,k):
  while q:
    x = q.pop()
    if a[i]<a[x]:
      q.append(x)
      q.append(i)
      break
  if not q:
    q.append(i)

for i in range(k,n+1):
  t = q.popleft()
  mxlist.append(a[t])
  if t != i-k:
    q.appendleft(t)
  if i == n:
    break
  while q:
    x = q.pop()
    if a[i]<a[x]:
      q.append(x)
      q.append(i)
      break
  if not q:
    q.append(i)
ans = n-k
r = set()
for i in range(1,n-k):
  if a[i-1]<mnlist[i] and mxlist[i]<a[i+k]:
    r.add(i)
flg = 0
flg2 = 0
for i in range(1,n):
  if a[i-1] < a[i]:
    flg += 1
  else:
    flg = 0
  if flg >= k:
    r.add(i-k)
    flg2 = 1
print(ans-len(r)+flg2)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
l=list(map(int,input().split()))
sc=0
ans=n-k+1
INF=n+1
No=2
while No<n:
    No*=2
tree=[[0,0]]*(2*No)
for i in range(No-1,No-1+n):
    tree[i]=[l[i-No+1],l[i-No+1]]
for i in range(No-2,-1,-1):
    a,b=tree[i*2+1]
    c,d=tree[i*2+2]
    tree[i]=[max(a,c),min(b,d)]
def query(l,r):
    L=l+No-1
    R=r+No-1
    s=[-INF,INF]
    while L<=R:
        if R&1:
            a,b=tree[R]
            c,d=s
            s=[max(a,c),min(b,d)]
            R-=2
        else:
            R-=1
        if L&1:
            L-=1
        else:
            a,b=tree[L]
            c,d=s
            s=[max(a,c),min(b,d)]
        L>>=1;R>>=1
    return s
class unionfind:
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
    def find(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def count(self, x):
        return -self.root[self.find(x)]
uf=unionfind(n)
s=set()
t=1
for i in range(n-1):
    if l[i]<l[i+1]:
        t+=1
    else:
        t=1
    if t>=k:
        s.add(i-k+2)
if len(s)>1:
    a=s.pop()
    while s:
        uf.unite(a,s.pop())
for i in range(n-k):
    b,a=query(i,i+k)
    if l[i]==a and l[i+k]==b:
        uf.unite(i,i+1)
s=set()
for i in range(n-k+1):
    s.add(uf.find(i))
print(len(s))

Submission status: Accepted

Solution code:
class BinaryIndexedTree():  #1-indexed
    def __init__(self, n):
        self.n = n
        self.tree = [0 for _ in range(n + 1)]

    def sum(self, index):
        res = 0
        while index:
            res += self.tree[index]
            index -= index & -index
        return res

    def add(self, index, x):
        while index <= self.n:
            self.tree[index] += x
            index += index & -index

    def bisect_left(self, x):
        if x <= 0: return 0
        res, tmp = 0, 2**((self.n).bit_length() - 1)
        while tmp:
            if res + tmp <= self.n and self.tree[res + tmp] < x:
                x -= self.tree[res + tmp]
                res += tmp
            tmp >>= 1
        return res + 1


N, K = map(int, input().split())
P = list(map(lambda x: int(x) + 1, input().split()))

bit = BinaryIndexedTree(N + 1)
count = 1

for i in range(K):
    bit.add(P[i], 1)

for i in range(N - K):
    mi = bit.bisect_left(1)
    ma = bit.bisect_left(K)
    if P[i] != mi or P[K + i] < ma:
        count += 1
    bit.add(P[i], -1)
    bit.add(P[K + i], 1)

inc = 1
incseq = 0

for i in range(N - 1):
    if P[i] < P[i + 1]:
        inc += 1
        if inc == K:
            incseq += 1
    else:
        inc = 1

print(count - max(0, incseq - 1))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
N, K , *P = map(int, open(0).read().split())
mhq = []
Mhq = []
for c in P[:K]:
  heappush(mhq,c)
  heappush(Mhq,-c)

ans = 1
log = set()
for i,c in enumerate(P[K:]):
  while mhq[0] in log:
    heappop(mhq)
  while -Mhq[0] in log:
    heappop(Mhq)
  d = P[i]
  m = mhq[0]
  M = -Mhq[0]
  log.add(d)
  heappush(mhq,c)
  heappush(Mhq,-c)
  if not (m==d and M<c):
    ans += 1
p = P[0]
m = 1
x = 0
for c in P[1:]:
  if p<c:
    m += 1
  else:
    if m>=K:
      x += 1
    m = 1
  p = c
if m>=K:
  x += 1
if x!=0:
  ans -= x-1
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
from itertools import accumulate

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def slide_min(A, K):
    res = []
    Q = deque()
    for i, a in enumerate(A):
        while Q and A[Q[-1]] > a:
            Q.pop()
        Q.append(i)
        if Q[0] == i - K:
            Q.popleft()
        res.append(Q[0])
    return res[K - 1:]

N, K = lr()
P = lr()
mi = slide_min(P, K)
ma = slide_min([-x for x in P], K)
new_pattern = [not (mi == i and ma == i+K) for i, (mi, ma) in enumerate(zip(mi, ma[1:]))]
# Trueの時は新しいパターンが登場
increase = [0] + list(accumulate(x<y for x, y in zip(P, P[1:])))
# K区間で常に上昇
stable_increase = [y-x == K-1  for x, y in zip(increase, increase[K-1:])]
answer = 1 + sum([x for x, y in zip(new_pattern, stable_increase[1:]) if not y])
if not stable_increase[0] and any(stable_increase):
    answer += 1
print(answer)

Submission status: Accepted

Solution code:
from collections import deque


def slide_min(L: int, li: list):
	deq = deque()
	ret = []
	for i, x in enumerate(li):
		while deq and deq[-1][1] > x:
			deq.pop()
		deq.append((i, x))
		if deq[0][0] + L == i:
			deq.popleft()
		ret.append(deq[0][1])
	return ret[L - 1:]


def slide_max(L: int, li: list):
	deq = deque()
	ret = []
	for i, x in enumerate(li):
		while deq and deq[-1][1] < x:
			deq.pop()
		deq.append((i, x))
		if deq[0][0] + L == i:
			deq.popleft()
		ret.append(deq[0][1])
	return ret[L - 1:]


n, k, *a = map(int, open(0).read().split())
m, M = slide_min(k - 1, a), slide_max(k - 1, a)
ans = 1
for i in range(n - k):
	if not (a[i] < m[i + 1] and M[i + 1] < a[i + k]):
		ans += 1
cnt = 1
subt = 0
for x, y in zip(a, a[1:]):
	if x < y:
		cnt += 1
	else:
		cnt = 1
	if cnt == k:
		subt += 1
if subt:
	ans -= subt - 1

print(ans)

Submission status: Accepted

Solution code:
def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    class UnionFind():
        def __init__(self, n):
            self.parent = [-1 for _ in range(n)]
            # 正==子: 根の頂点番号 / 負==根: 連結頂点数

        def find(self, x):
            # 要素xが属するグループの根を返す
            if self.parent[x] < 0:
                return x
            else:
                self.parent[x] = self.find(self.parent[x])
                return self.parent[x]

        def unite(self, x, y):
            # 要素xが属するグループと要素yが属するグループとを併合する
            x, y = self.find(x), self.find(y)
            if x == y:
                return False
            else:
                if self.size(x) < self.size(y):
                    x, y = y, x
                self.parent[x] += self.parent[y]
                self.parent[y] = x

        def same(self, x, y):
            # 要素x, yが同じグループに属するかどうかを返す
            return self.find(x) == self.find(y)

        def size(self, x):
            # 要素xが属するグループのサイズ（要素数）を返す
            x = self.find(x)
            return -self.parent[x]

        def is_root(self, x):
            # 要素の根をリストで返す
            return self.parent[x] < 0

        def roots(self):
            # すべての根の要素をリストで返す
            return [i for i, x in enumerate(self.parent) if x < 0]

        def members(self, x):
            # 要素xが属するグループに属する要素をリストで返す
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]

        def group_count(self):
            # グループの数を返す
            return len(self.roots())

        def all_group_members(self):
            # {ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
            return {r: self.members(r) for r in self.roots()}
    class segment_():
        def __init__(self, A, n, segfunc,ide_ele):
            #####単位元######要設定0or1orinf
            self.ide_ele = ide_ele
            ####################
            self.num = 1 << (n - 1).bit_length()
            self.seg = [self.ide_ele] * 2 * self.num
            self.segfunc = segfunc
            # set_val
            for i in range(n):
                self.seg[i + self.num] = A[i]
                # built
            for i in range(self.num - 1, 0, -1):
                self.seg[i] = self.segfunc(self.seg[2 * i], self.seg[2 * i + 1])

        def update(self, k, r):
            k += self.num
            self.seg[k] = r
            while k:
                k >>= 1
                self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

        # 値xに1加算
        def update1(self, k):
            k += self.num
            self.seg[k] += 1
            while k:
                k >>= 1
                self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

        def updateneg1(self, k):
            k += self.num
            self.seg[k] -= 1
            while k:
                k >>= 1
                self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

        def query(self, p, q):
            if q < p:
                return self.ide_ele
            p += self.num;
            q += self.num
            res = self.ide_ele
            while p < q:
                if p & 1 == 1:
                    res = self.segfunc(res, self.seg[p])
                    p += 1
                if q & 1 == 1:
                    q -= 1
                    res = self.segfunc(res, self.seg[q])
                p >>= 1;
                q >>= 1
            return res
    N, K = LI()
    P = LI()
    Seg_min = segment_(P, N, lambda a, b: min(a,b),inf)
    Seg_max = segment_(P, N, lambda a, b: max(a, b),-inf)
    DL = defaultdict(bool)
    DR = defaultdict(bool)
    for i in range(N-K+1):
        cur = Seg_min.query(i,i+K)
        if cur==P[i]:
            DL[i] = True
        cur = Seg_max.query(i,i+K)
        if cur==P[i+K-1]:
            DR[i+K-1] = True
    #print(DL,DR)
    uf = UnionFind(N)
    bigger = [False]*N
    skip = []
    for i in range(N-1):
        if P[i+1]>P[i]:
            bigger[i] = True
    cur = sum(bigger[:K-1])
    if cur == K - 1:
        skip.append(0)
    for i in range(N-K):
        if bigger[i+K-1]:
            cur += 1
        if bigger[i]:
            cur -= 1
        if cur==K-1:
            skip.append(i+1)
    #print(skip)
    #print(bigger)
    for i in range(len(skip)-1):
        uf.unite(skip[i],skip[i+1])

    for i in range(N-K):
        if DL[i] and DR[i+K]:
            uf.unite(i,i+1)
    ans = set()
    for i in range(N-K+1):
        cur = uf.find(i)
        #print(i,cur)
        ans.add(cur)
    print(len(ans))
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examB()

"""
9 4
8 0 1 2 3 4 5 6 7 

9 2
6 7 8 3 4 5 0 1 2

13 4
9 10 11 12 2 1 0 6 7 8 3 4 5
"""

Submission status: Accepted

Solution code:
from collections import deque


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

smin = deque()
smax = deque()
x = 0
r = 0
r2 = 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 heapq import heappush, heappop

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

h_max = []
h_min = []
for i in range(K):
  heappush(h_min,  A[i])
  heappush(h_max, -A[i])

check = [0] * (N + 1)
tmp = [0] * N
tmp[0] = 1
for i in range(N - K):
  
  a_min =  heappop(h_min)
  a_max = -heappop(h_max)
  while check[a_min]:
    a_min =  heappop(h_min)
  while check[a_max]:
    a_max = -heappop(h_max)
  if A[i] == a_min and A[i + K] > a_max:
    tmp[i + 1] -= 1
  check[A[i]] = 1
  heappush(h_min,  a_min)
  heappush(h_max, -a_max)  
  heappush(h_min,  A[i + K])
  heappush(h_max, -A[i + K])  
  tmp[i + 1] += 1

B = [0]
for i in range(1, N):
  if A[i] > A[i - 1]:
    B.append(1)
  else:
    B.append(0)

sum_B = sum(B[1: K])
flag = 0
for i in range(N - K + 1):
  if sum_B == K - 1:
    if tmp[i]:
      flag = 1
      tmp[i] = 0
  if i == N - K:
    break
  sum_B = sum_B - B[i + 1] + B[i + K]

print(sum(tmp) + flag)