CodeForces-213E：Two Permutations（神奇的线段树+hash）

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 a_i.

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 (c₁ = a₁ + d, c₂ = a₂ + d, ..., c_n = a_n + d) of length n is a subsequence of b.

Sequence a is a subsequence of sequence b, if there are such indices i₁, i₂, ..., i_n(1 ≤ i₁ < i₂ < ... < i_n ≤ m), that a₁ = b_i₁, a₂ = b_i₂, ..., a_n = b_{i_n}, 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.

Example

Input

1 1
1
1

Output

Input

1 2
1
2 1

Output

Input

3 3
2 3 1
1 2 3

Output

题意：给定全排列A（1-N），全排列B（1-M），问有多少个d，满足全排列A的每一位+d后，是B的子序列（不是字串）。

思路：对于全排列A，得到hashA，先在B中得到1-N的hashB。每次d++的新排列，等效于1到N+1的排列每一位减去1（hash实现）。

具体的代码一看就明白。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

typedef unsigned long long ull;

const int maxn=;

const int B=;

int N,M,pos[maxn],x;

ull g[maxn];

ull val,sum;

struct SegmentTree

{

    ull hash[maxn<<];

    int cnt[maxn<<];

    void build(int Now,int l,int r)

    {

        hash[Now]=cnt[Now]=;

        if(l==r) return ;

        int mid=(l+r)>>;

        build(Now<<,l,mid);

        build(Now<<|,mid+,r);

    }

    void pushup(int Now)

    {

        hash[Now]=hash[Now<<]*g[cnt[Now<<|]]+hash[Now<<|];

        cnt[Now]=cnt[Now<<]+cnt[Now<<|];

    }

    void update(int Now,int l,int r,int pos,int val,int num)

    {

        if(l==r)

        {

            hash[Now]+=num*val;

            cnt[Now]+=num;

            return;

        }

        int mid=(l+r)>>;

        if(pos<=mid) update(Now<<,l,mid,pos,val,num);

        else update(Now<<|,mid+,r,pos,val,num);

        pushup(Now);

    }

}Tree;

int main()

{

    while(~scanf("%d%d",&N,&M))

    {

        val=sum=;

        g[]=;

        for(int i=;i<=N;i++)  g[i]=g[i-]*B, sum+=g[i-];

        for(int i=;i<=N;i++){

            scanf("%d",&x);

            val=val*B+x;

        }

        for(int i=;i<=M;i++){

            scanf("%d",&x);

            pos[x]=i;

        }

        Tree.build(,,M);

        int ans=;

        for(int i=;i<=M;i++)//把数值1~M按顺序加入线段树中

        {

            Tree.update(,,M,pos[i],i,);

            if(i>=N)

            {

                if(Tree.hash[]-(sum*(i-N))==val) ans++;

                Tree.update(,,M,pos[i-N+],i-N+,-);

            }

        }

        printf("%d\n",ans);

    }

    return ;

}

巴特西

CodeForces-213E：Two Permutations（神奇的线段树+hash）

最新文章

热门文章