Codefroces 213E. Two Permutations

E. Two Permutations

time limit per test

3 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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.

Examples

Input

1 1
1
1

Output

Input

1 2
1
2 1

Output

Input

3 3
2 3 1
1 2 3

Output

【题解】

由于a和b都是排列，其实就是找b中i...i + n - 1的相对位置与a中1...n的相对位置是否相同

康托展开显然是不好做的（反正我不会）

于是我们可以hash，拿线段树做即可

线段树下标是排列位置，线段数内的值是该位置的值

先把1...n的位置放进去，然后查行不行

然后把1拿出来，把n + 1的位置放进去，看看行不行

（注意由于每个数字都增加1，因此hash值应增加B^0 + B^1 + B^2.. + B^n，前缀和处理即可）

以此类推

因为没有膜够所以WA了好几发

具体看代码

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #define max(a, b) ((a) > (b) ? (a) : (b))

 #define min(a, b) ((a) < (b) ? (a) : (b))

 inline void swap(long long &a, long long &b)

 {

     long long tmp = a;a = b;b = tmp;

 }

 inline void read(long long &x)

 {

     x = ;char ch = getchar(), c = ch;

     while(ch < '' || ch > '')c = ch, ch = getchar();

     while(ch <= '' && ch >= '')x = x *  + ch - '', ch = getchar();

     if(c == '-')x = -x;

 }

 const long long MAXN =  + ;

 const long long MOD1 = ;

 const long long MOD2 = ;

 const long long B = ;

 const long long MOD = ;

 long long data[][MAXN], ans, sum1, sum2, sum[MAXN], val1, val2, bit1[MAXN], bit2[MAXN], cnt[MAXN << ], size1[MAXN], size2[MAXN], n, m;

 //在权值p这个位置，[x == 1]增加k,[x == -1]减小k

 void modify(long long p, long long k, long long x, long long o = , long long l = , long long r = m)

 {

     if(l == r && p == l)

     {

         data[][o] += k * x % MOD1;

         data[][o] += k * x % MOD2;

         size1[o] += x, size2[o] += x;

         return;

     }

     long long mid = (l + r) >> ;

     if(mid >= p) modify(p, k, x, o << , l, mid);

     else modify(p, k, x, o <<  | , mid + , r);

     data[][o] = ((data[][o <<  | ] * bit1[size1[o << ]]) % MOD1 + data[][o << ]) % MOD1;

     data[][o] = ((data[][o <<  | ] * bit2[size2[o << ]]) % MOD2 + data[][o << ]) % MOD2;

     size1[o] = size1[o << ] + size1[o <<  | ];

     size2[o] = size2[o << ] + size2[o <<  | ];

     return;

 }

 int main()

 {

 //    freopen("data.txt", "r", stdin);

     read(n) ,read(m);

     bit1[] = ;bit2[] = ;

     for(register long long i = ;i <= m;++ i)

         bit1[i] = (bit1[i - ] * B)%MOD1, bit2[i] = (bit2[i - ] * B)%MOD2;

     for(register long long i = ;i <= n;++ i)

     {

         long long tmp;

         read(tmp);

         val1 += tmp * bit1[i - ] % MOD1;

         val1 %= MOD1;

         val2 += tmp * bit2[i - ] % MOD2;

         val2 %= MOD2;

         sum1 += bit1[i - ];sum1 %= MOD1;

         sum2 += bit2[i - ];sum2 %= MOD2;

     }

     for(register long long i = ;i <= m;++ i)

     {

         long long tmp;

         read(tmp);

         cnt[tmp] = i;

     }

     for(register long long i = ;i <= m;++ i)

     {

         modify(cnt[i], i, );

         if(i >= n)

         {

             if(data[][] == (val2 + (sum2 * (i - n))%MOD2)%MOD2 && data[][] == (val1 + (sum1 * (i - n))%MOD1)%MOD1)

                 ++ ans;

             modify(cnt[i - n + ], i - n + , -);

         }

     }

     printf("%d", ans);

     return ;

 }

Codeforces213E

巴特西

Codefroces 213E. Two Permutations

最新文章

热门文章