1 /* 2 線段樹 + hash： 3 首先我們可以知道A序列是1~n的排列，那么我們可以先在B序列中把1~n的排列找出來(lái)，看其相對(duì)位置是否與A相同(hash可做)，相同即表明存在一個(gè)d滿足條件。 4 以此類推，我們接下來(lái)可以把B中 2~ n + 1的排列找出來(lái)，如果其每位-1后相對(duì)順序還是與A序列一致，即存在d-1也滿足。。。 5 線段樹中保存一個(gè)長(zhǎng)度為n的序列的hash。具體看代碼 6 */ 7 #include <bits/stdc++.h> 8 9 using namespace std; 10 11 #define lson l, m ,rt<<1 12 #define rson m + 1, r, rt <<1|1 13 const int maxn = 2e5 + 5; 14 const int M = 10007;//hash底數(shù) 15 typedef long long ll; 16 int pw[maxn], s, h; 17 int n, m; 18 19 int hash[maxn << 2],sz[maxn << 2]; 20 void pushUp(int rt){ 21 hash[rt] = hash[rt<<1] * pw[sz[rt<<1|1]] + hash[rt<<1|1]; 22 sz[rt] = sz[rt<<1] + sz[rt<<1|1]; 23 } 24 void update(int p, int val, int tag, int l, int r, int rt){ 25 if (l == r){ 26 hash[rt] += tag * val; 27 sz[rt] += tag; 28 return ; 29 } 30 int m = (l + r) >> 1; 31 if (p <= m) update(p, val, tag, lson); 32 else update(p, val, tag, rson); 33 pushUp(rt); 34 } 35 int pos[maxn]; 36 int main(){ 37 int x; 38 while (~scanf("%d%d", &n, &m)){ 39 pw[0] = 1; 40 h = s = 0; 41 for (int i = 1; i <= n; ++i){ 42 scanf("%d", &x); 43 h = h * M + x; 44 pw[i] = pw[i - 1] * M;//M的i次方 45 s += pw[i - 1];//1 ~n的排列的hash轉(zhuǎn)化成 2 ~ n + 1的hash需要+s.......自己算算 46 } 47 for (int i = 1; i <= m; ++i){ 48 scanf("%d", &x); 49 pos[x] = i; 50 } 51 memset(hash, 0, sizeof(hash)); 52 memset(sz, 0, sizeof(sz)); 53 int ans = 0; 54 for (int i = 1; i <= m; ++i){ 55 update(pos[i], i, 1, 1, m, 1); 56 if (i >= n){ 57 if ((hash[1] - (s * (i - n)) == h)) 58 ans++; 59 update(pos[i - n + 1], i - n + 1, -1, 1, m, 1); 60 } 61 } 62 printf("%d\n", ans); 63 } 64 return 0; 65 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Missa/p/3447706.html

總結(jié)

以上是生活随笔為你收集整理的CodeForces 213 E的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。