Two Permutations (Codeforces 213E)
Tags: Others, hashing

Rubik is very keen on number permutations. A permutation a with length n is a sequence, consisting of n different numbers from 1 to n. Element number i (1 ≤ i ≤ n) of this permutation will be denoted as ai.Furik decided to make a present to Rubik and came up with a new problem on permutations. Furik tells Rubik two number permutations: permutation a with length n and permutation b with length m. Rubik must give an answer to the problem: how many distinct integers d exist, such that sequence c (c1 = a1 + d, c2 = a2 + d, ..., cn = an + d) of length n is a subsequence of b.Sequence a is a subsequence of sequence b, if there are such indices i1, i2, ..., in (1 ≤ i1 < i2 < ... < in ≤ m), that a1 = bi1, a2 = bi2, ..., an = bin, where n is the length of sequence a, and m is the length of sequence b. You are given permutations a and b, help Rubik solve the given problem.

Input: The first line contains two integers n and m (1 ≤ n ≤ m ≤ 200000) — the sizes of the given permutations. The second line contains n distinct integers — permutation a, the third line contains m distinct integers — permutation b. Numbers on the lines are separated by spaces.

Output: On a single line print the answer to the problem. 


Sample Inputs:
1 1
1
1

1 2
1
2 1

3 3
2 3 1
1 2 3

Sample Outputs:
1

2

0

Solution (Python):
import sys
readline = sys.stdin.readline

class Segment_Tree:

    def __init__(self, N, f, e, lst=None):
        self.f = f
        self.e = e
        self.N = N
        if lst == None:
            self.segment_tree = [self.e] * 2 * self.N
        else:
            assert len(lst) <= self.N
            self.segment_tree = [self.e] * self.N + [x for x in lst] + [self.e] * (N - len(lst))
            for i in range(self.N - 1, 0, -1):
                self.segment_tree[i] = self.f(self.segment_tree[i << 1], self.segment_tree[i << 1 | 1])

    def __getitem__(self, i):
        if type(i) == int:
            if -self.N <= i < 0:
                return self.segment_tree[i + self.N * 2]
            elif 0 <= i < self.N:
                return self.segment_tree[i + self.N]
            else:
                raise IndexError('list index out of range')
        else:
            (a, b, c) = (i.start, i.stop, i.step)
            if a == None:
                a = self.N
            else:
                a += self.N
            if b == None:
                b = self.N * 2
            else:
                b += self.N
            return self.segment_tree[slice(a, b, c)]

    def __setitem__(self, i, x):
        if -self.N <= i < 0:
            i += self.N * 2
        elif 0 <= i < self.N:
            i += self.N
        else:
            raise IndexError('list index out of range')
        self.segment_tree[i] = x
        while i > 1:
            i >>= 1
            self.segment_tree[i] = self.f(self.segment_tree[i << 1], self.segment_tree[i << 1 | 1])

    def Build(self, lst):
        for (i, x) in enumerate(lst, self.N):
            self.segment_tree[i] = x
        for i in range(self.N - 1, 0, -1):
            self.segment_tree[i] = self.f(self.segment_tree[i << 1], self.segment_tree[i << 1 | 1])

    def Fold(self, L=None, R=None):
        if L == None:
            L = self.N
        else:
            L += self.N
        if R == None:
            R = self.N * 2
        else:
            R += self.N
        vL = self.e
        vR = self.e
        while L < R:
            if L & 1:
                vL = self.f(vL, self.segment_tree[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.f(self.segment_tree[R], vR)
            L >>= 1
            R >>= 1
        return self.f(vL, vR)

    def Fold_Index(self, L=None, R=None):
        if L == None:
            L = self.N
        else:
            L += self.N
        if R == None:
            R = self.N * 2
        else:
            R += self.N
        if L == R:
            return None
        x = self.Fold(L - self.N, R - self.N)
        while L < R:
            if L & 1:
                if self.segment_tree[L] == x:
                    i = L
                    break
                L += 1
            if R & 1:
                R -= 1
                if self.segment_tree[R] == x:
                    i = R
                    break
            L >>= 1
            R >>= 1
        while i < self.N:
            if self.segment_tree[i] == self.segment_tree[i << 1]:
                i <<= 1
            else:
                i <<= 1
                i |= 1
        i -= self.N
        return i

    def Bisect_Right(self, L=None, f=None):
        if L == self.N:
            return self.N
        if L == None:
            L = 0
        L += self.N
        vl = self.e
        vr = self.e
        (l, r) = (L, self.N * 2)
        while l < r:
            if l & 1:
                vl = self.f(vl, self.segment_tree[l])
                l += 1
            if r & 1:
                r -= 1
                vr = self.f(self.segment_tree[r], vr)
            l >>= 1
            r >>= 1
        if f(self.f(vl, vr)):
            return self.N
        v = self.e
        while True:
            while L % 2 == 0:
                L >>= 1
            vv = self.f(v, self.segment_tree[L])
            if f(vv):
                v = vv
                L += 1
            else:
                while L < self.N:
                    L <<= 1
                    vv = self.f(v, self.segment_tree[L])
                    if f(vv):
                        v = vv
                        L += 1
                return L - self.N

    def Bisect_Left(self, R=None, f=None):
        if R == 0:
            return 0
        if R == None:
            R = self.N
        R += self.N
        vl = self.e
        vr = self.e
        (l, r) = (self.N, R)
        while l < r:
            if l & 1:
                vl = self.f(vl, self.segment_tree[l])
                l += 1
            if r & 1:
                r -= 1
                vr = self.f(self.segment_tree[r], vr)
            l >>= 1
            r >>= 1
        if f(self.f(vl, vr)):
            return 0
        v = self.e
        while True:
            R -= 1
            while R > 1 and R % 2:
                R >>= 1
            vv = self.f(self.segment_tree[R], v)
            if f(vv):
                v = vv
            else:
                while R < self.N:
                    R = 2 * R + 1
                    vv = self.f(self.segment_tree[R], v)
                    if f(vv):
                        v = vv
                        R -= 1
                return R + 1 - self.N

    def __str__(self):
        return '[' + ', '.join(map(str, self.segment_tree[self.N:])) + ']'
(N, M) = map(int, readline().split())
A = list(map(int, readline().split()))
B = list(map(int, readline().split()))
idxA = [None] * N
idxB = [None] * M
for i in range(N):
    A[i] -= 1
    idxA[A[i]] = i
for i in range(M):
    B[i] -= 1
    idxB[B[i]] = i
base = 4
mod = (1 << 61) - 1
base_pow = [1]
for i in range(1, M + 1):
    base_pow.append(base_pow[-1] * base % mod)

def f(tpl0, tpl1):
    (x0, y0) = tpl0
    (x1, y1) = tpl1
    return (x0 + x1, (y0 + y1) % mod)
ans = 0
hashA = sum((idxA[i] * base_pow[i] % mod for i in range(N))) % mod
comp = {x: i for (i, x) in enumerate(sorted(idxB[:N]))}
hashB = sum((comp[idxB[i]] * base_pow[i] % mod for i in range(N))) % mod
if hashA == hashB:
    ans += 1
lst = [(0, 0)] * M
(X, Y) = (0, 0)
for i in range(N):
    lst[idxB[i]] = (1, base_pow[i])
    X += 1
    Y += base_pow[i]
    Y %= mod
ST = Segment_Tree(M, f, (0, 0), lst)
for i in range(M - N):
    (x, y) = ST[idxB[i]]
    X -= x
    Y -= y
    Y %= mod
    ST[idxB[i]] = (0, 0)
    (x, y) = ST.Fold(0, idxB[i])
    y = Y - y
    hashB -= x * base_pow[i] % mod + y
    hashB %= mod
    ST[idxB[i + N]] = (1, base_pow[i + N])
    X += 1
    Y += base_pow[i + N]
    Y %= mod
    (x, y) = ST.Fold(0, idxB[i + N])
    y = Y - y - base_pow[i + N]
    hashB += x * base_pow[i + N] % mod + y
    hashB %= mod
    if hashA * base_pow[i + 1] % mod == hashB:
        ans += 1
print(ans)

Solution (Python):
import sys
readline = sys.stdin.readline

class Segment_Tree:

    def __init__(self, N, f, e, lst=None):
        self.f = f
        self.e = e
        self.N = N
        if lst == None:
            self.segment_tree = [self.e] * 2 * self.N
        else:
            assert len(lst) <= self.N
            self.segment_tree = [self.e] * self.N + [x for x in lst] + [self.e] * (N - len(lst))
            for i in range(self.N - 1, 0, -1):
                self.segment_tree[i] = self.f(self.segment_tree[i << 1], self.segment_tree[i << 1 | 1])

    def __getitem__(self, i):
        if type(i) == int:
            if -self.N <= i < 0:
                return self.segment_tree[i + self.N * 2]
            elif 0 <= i < self.N:
                return self.segment_tree[i + self.N]
            else:
                raise IndexError('list index out of range')
        else:
            (a, b, c) = (i.start, i.stop, i.step)
            if a == None:
                a = self.N
            else:
                a += self.N
            if b == None:
                b = self.N * 2
            else:
                b += self.N
            return self.segment_tree[slice(a, b, c)]

    def __setitem__(self, i, x):
        if -self.N <= i < 0:
            i += self.N * 2
        elif 0 <= i < self.N:
            i += self.N
        else:
            raise IndexError('list index out of range')
        self.segment_tree[i] = x
        while i > 1:
            i >>= 1
            self.segment_tree[i] = self.f(self.segment_tree[i << 1], self.segment_tree[i << 1 | 1])

    def Build(self, lst):
        for (i, x) in enumerate(lst, self.N):
            self.segment_tree[i] = x
        for i in range(self.N - 1, 0, -1):
            self.segment_tree[i] = self.f(self.segment_tree[i << 1], self.segment_tree[i << 1 | 1])

    def Fold(self, L=None, R=None):
        if L == None:
            L = self.N
        else:
            L += self.N
        if R == None:
            R = self.N * 2
        else:
            R += self.N
        vL = self.e
        vR = self.e
        while L < R:
            if L & 1:
                vL = self.f(vL, self.segment_tree[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.f(self.segment_tree[R], vR)
            L >>= 1
            R >>= 1
        return self.f(vL, vR)

    def Fold_Index(self, L=None, R=None):
        if L == None:
            L = self.N
        else:
            L += self.N
        if R == None:
            R = self.N * 2
        else:
            R += self.N
        if L == R:
            return None
        x = self.Fold(L - self.N, R - self.N)
        while L < R:
            if L & 1:
                if self.segment_tree[L] == x:
                    i = L
                    break
                L += 1
            if R & 1:
                R -= 1
                if self.segment_tree[R] == x:
                    i = R
                    break
            L >>= 1
            R >>= 1
        while i < self.N:
            if self.segment_tree[i] == self.segment_tree[i << 1]:
                i <<= 1
            else:
                i <<= 1
                i |= 1
        i -= self.N
        return i

    def Bisect_Right(self, L=None, f=None):
        if L == self.N:
            return self.N
        if L == None:
            L = 0
        L += self.N
        vl = self.e
        vr = self.e
        (l, r) = (L, self.N * 2)
        while l < r:
            if l & 1:
                vl = self.f(vl, self.segment_tree[l])
                l += 1
            if r & 1:
                r -= 1
                vr = self.f(self.segment_tree[r], vr)
            l >>= 1
            r >>= 1
        if f(self.f(vl, vr)):
            return self.N
        v = self.e
        while True:
            while L % 2 == 0:
                L >>= 1
            vv = self.f(v, self.segment_tree[L])
            if f(vv):
                v = vv
                L += 1
            else:
                while L < self.N:
                    L <<= 1
                    vv = self.f(v, self.segment_tree[L])
                    if f(vv):
                        v = vv
                        L += 1
                return L - self.N

    def Bisect_Left(self, R=None, f=None):
        if R == 0:
            return 0
        if R == None:
            R = self.N
        R += self.N
        vl = self.e
        vr = self.e
        (l, r) = (self.N, R)
        while l < r:
            if l & 1:
                vl = self.f(vl, self.segment_tree[l])
                l += 1
            if r & 1:
                r -= 1
                vr = self.f(self.segment_tree[r], vr)
            l >>= 1
            r >>= 1
        if f(self.f(vl, vr)):
            return 0
        v = self.e
        while True:
            R -= 1
            while R > 1 and R % 2:
                R >>= 1
            vv = self.f(self.segment_tree[R], v)
            if f(vv):
                v = vv
            else:
                while R < self.N:
                    R = 2 * R + 1
                    vv = self.f(self.segment_tree[R], v)
                    if f(vv):
                        v = vv
                        R -= 1
                return R + 1 - self.N

    def __str__(self):
        return '[' + ', '.join(map(str, self.segment_tree[self.N:])) + ']'
(N, M) = map(int, readline().split())
A = list(map(int, readline().split()))
B = list(map(int, readline().split()))
idxA = [None] * N
idxB = [None] * M
for i in range(N):
    A[i] -= 1
    idxA[A[i]] = i
for i in range(M):
    B[i] -= 1
    idxB[B[i]] = i
base = 5
mod = (1 << 61) - 1
base_pow = [1]
for i in range(1, M + 1):
    base_pow.append(base_pow[-1] * base % mod)

def f(tpl0, tpl1):
    (x0, y0) = tpl0
    (x1, y1) = tpl1
    return (x0 + x1, (y0 + y1) % mod)
ans = 0
hashA = sum((idxA[i] * base_pow[i] % mod for i in range(N))) % mod
comp = {x: i for (i, x) in enumerate(sorted(idxB[:N]))}
hashB = sum((comp[idxB[i]] * base_pow[i] % mod for i in range(N))) % mod
if hashA == hashB:
    ans += 1
lst = [(0, 0)] * M
(X, Y) = (0, 0)
for i in range(N):
    lst[idxB[i]] = (1, base_pow[i])
    X += 1
    Y += base_pow[i]
    Y %= mod
ST = Segment_Tree(M, f, (0, 0), lst)
for i in range(M - N):
    (x, y) = ST[idxB[i]]
    X -= x
    Y -= y
    Y %= mod
    ST[idxB[i]] = (0, 0)
    (x, y) = ST.Fold(0, idxB[i])
    y = Y - y
    hashB -= x * base_pow[i] % mod + y
    hashB %= mod
    ST[idxB[i + N]] = (1, base_pow[i + N])
    X += 1
    Y += base_pow[i + N]
    Y %= mod
    (x, y) = ST.Fold(0, idxB[i + N])
    y = Y - y - base_pow[i + N]
    hashB += x * base_pow[i + N] % mod + y
    hashB %= mod
    if hashA * base_pow[i + 1] % mod == hashB:
        ans += 1
print(ans)

Solution (Python):
import sys
readline = sys.stdin.readline

class Segment_Tree:

    def __init__(self, N, f, e, lst=None):
        self.f = f
        self.e = e
        self.N = N
        if lst == None:
            self.segment_tree = [self.e] * 2 * self.N
        else:
            assert len(lst) <= self.N
            self.segment_tree = [self.e] * self.N + [x for x in lst] + [self.e] * (N - len(lst))
            for i in range(self.N - 1, 0, -1):
                self.segment_tree[i] = self.f(self.segment_tree[i << 1], self.segment_tree[i << 1 | 1])

    def __getitem__(self, i):
        if type(i) == int:
            if -self.N <= i < 0:
                return self.segment_tree[i + self.N * 2]
            elif 0 <= i < self.N:
                return self.segment_tree[i + self.N]
            else:
                raise IndexError('list index out of range')
        else:
            (a, b, c) = (i.start, i.stop, i.step)
            if a == None:
                a = self.N
            else:
                a += self.N
            if b == None:
                b = self.N * 2
            else:
                b += self.N
            return self.segment_tree[slice(a, b, c)]

    def __setitem__(self, i, x):
        if -self.N <= i < 0:
            i += self.N * 2
        elif 0 <= i < self.N:
            i += self.N
        else:
            raise IndexError('list index out of range')
        self.segment_tree[i] = x
        while i > 1:
            i >>= 1
            self.segment_tree[i] = self.f(self.segment_tree[i << 1], self.segment_tree[i << 1 | 1])

    def Build(self, lst):
        for (i, x) in enumerate(lst, self.N):
            self.segment_tree[i] = x
        for i in range(self.N - 1, 0, -1):
            self.segment_tree[i] = self.f(self.segment_tree[i << 1], self.segment_tree[i << 1 | 1])

    def Fold(self, L=None, R=None):
        if L == None:
            L = self.N
        else:
            L += self.N
        if R == None:
            R = self.N * 2
        else:
            R += self.N
        vL = self.e
        vR = self.e
        while L < R:
            if L & 1:
                vL = self.f(vL, self.segment_tree[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.f(self.segment_tree[R], vR)
            L >>= 1
            R >>= 1
        return self.f(vL, vR)

    def Fold_Index(self, L=None, R=None):
        if L == None:
            L = self.N
        else:
            L += self.N
        if R == None:
            R = self.N * 2
        else:
            R += self.N
        if L == R:
            return None
        x = self.Fold(L - self.N, R - self.N)
        while L < R:
            if L & 1:
                if self.segment_tree[L] == x:
                    i = L
                    break
                L += 1
            if R & 1:
                R -= 1
                if self.segment_tree[R] == x:
                    i = R
                    break
            L >>= 1
            R >>= 1
        while i < self.N:
            if self.segment_tree[i] == self.segment_tree[i << 1]:
                i <<= 1
            else:
                i <<= 1
                i |= 1
        i -= self.N
        return i

    def Bisect_Right(self, L=None, f=None):
        if L == self.N:
            return self.N
        if L == None:
            L = 0
        L += self.N
        vl = self.e
        vr = self.e
        (l, r) = (L, self.N * 2)
        while l < r:
            if l & 1:
                vl = self.f(vl, self.segment_tree[l])
                l += 1
            if r & 1:
                r -= 1
                vr = self.f(self.segment_tree[r], vr)
            l >>= 1
            r >>= 1
        if f(self.f(vl, vr)):
            return self.N
        v = self.e
        while True:
            while L % 2 == 0:
                L >>= 1
            vv = self.f(v, self.segment_tree[L])
            if f(vv):
                v = vv
                L += 1
            else:
                while L < self.N:
                    L <<= 1
                    vv = self.f(v, self.segment_tree[L])
                    if f(vv):
                        v = vv
                        L += 1
                return L - self.N

    def Bisect_Left(self, R=None, f=None):
        if R == 0:
            return 0
        if R == None:
            R = self.N
        R += self.N
        vl = self.e
        vr = self.e
        (l, r) = (self.N, R)
        while l < r:
            if l & 1:
                vl = self.f(vl, self.segment_tree[l])
                l += 1
            if r & 1:
                r -= 1
                vr = self.f(self.segment_tree[r], vr)
            l >>= 1
            r >>= 1
        if f(self.f(vl, vr)):
            return 0
        v = self.e
        while True:
            R -= 1
            while R > 1 and R % 2:
                R >>= 1
            vv = self.f(self.segment_tree[R], v)
            if f(vv):
                v = vv
            else:
                while R < self.N:
                    R = 2 * R + 1
                    vv = self.f(self.segment_tree[R], v)
                    if f(vv):
                        v = vv
                        R -= 1
                return R + 1 - self.N

    def __str__(self):
        return '[' + ', '.join(map(str, self.segment_tree[self.N:])) + ']'
(N, M) = map(int, readline().split())
A = list(map(int, readline().split()))
B = list(map(int, readline().split()))
idxA = [None] * N
idxB = [None] * M
for i in range(N):
    A[i] -= 1
    idxA[A[i]] = i
for i in range(M):
    B[i] -= 1
    idxB[B[i]] = i
base = 3
mod = (1 << 61) - 1
base_pow = [1]
for i in range(1, M + 1):
    base_pow.append(base_pow[-1] * base % mod)

def f(tpl0, tpl1):
    (x0, y0) = tpl0
    (x1, y1) = tpl1
    return (x0 + x1, (y0 + y1) % mod)
ans = 0
hashA = sum((idxA[i] * base_pow[i] % mod for i in range(N))) % mod
comp = {x: i for (i, x) in enumerate(sorted(idxB[:N]))}
hashB = sum((comp[idxB[i]] * base_pow[i] % mod for i in range(N))) % mod
if hashA == hashB:
    ans += 1
lst = [(0, 0)] * M
(X, Y) = (0, 0)
for i in range(N):
    lst[idxB[i]] = (1, base_pow[i])
    X += 1
    Y += base_pow[i]
    Y %= mod
ST = Segment_Tree(M, f, (0, 0), lst)
for i in range(M - N):
    (x, y) = ST[idxB[i]]
    X -= x
    Y -= y
    Y %= mod
    ST[idxB[i]] = (0, 0)
    (x, y) = ST.Fold(0, idxB[i])
    y = Y - y
    hashB -= x * base_pow[i] % mod + y
    hashB %= mod
    ST[idxB[i + N]] = (1, base_pow[i + N])
    X += 1
    Y += base_pow[i + N]
    Y %= mod
    (x, y) = ST.Fold(0, idxB[i + N])
    y = Y - y - base_pow[i + N]
    hashB += x * base_pow[i + N] % mod + y
    hashB %= mod
    if hashA * base_pow[i + 1] % mod == hashB:
        ans += 1
print(ans)