MorsLin 的博客

题解 CF213E 【Two Permutations】

posted on 2019-02-12 07:27:17 | under 题解 |

1. pos[i-n+1]~pos[i]减去$x$等于$a$排列
2. b[pos[i-n+1]]~b[pos[i]]是$b$的子序列

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ULL unsigned long long
#define ls (p << 1)
#define rs (p << 1 | 1)
#define mid ((l + r) >> 1)
using namespace std;
int k = 0, f = 1; char c = getchar();
while(c < '0' || c > '9'){
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9')
k = k * 10 + c - 48, c = getchar();
return k * f;
}
int a[200010], b[200010], pos[200010], ans;
ULL hasha, qpow[200010] = {1}, sum;
struct zzz{
ULL a, tot;
}tree[200010 << 2];
void up(int l, int r, int p) {
tree[p].tot = tree[ls].tot + tree[rs].tot;
tree[p].a = tree[ls].a * qpow[tree[rs].tot] + tree[rs].a;
}
void update(int l, int r, int pos, int p, int k) {
if(l == r) {
if(!k) tree[p].tot -= 1;
else tree[p].tot += 1;
tree[p].a = k; return ;
}
if(pos <= mid) update(l, mid, pos, ls, k);
if(pos > mid) update(mid+1, r, pos, rs, k);
up(l, r, p);
}
int main() {
for(int i = 1; i <= n; ++i) {
a[i] = read(), hasha = hasha * 23 + a[i];
qpow[i] = qpow[i-1] * 23;
sum += qpow[i-1];
}
for(int i = 1; i <= m; ++i) b[i] = read(), pos[b[i]] = i;
for(int i = 1; i <= m; ++i) {
if(i > n) update(1, m, pos[i-n], 1, 0);
update(1, m, pos[i], 1, i);
int d = i - n;
if(d >= 0 && tree[1].a == d*sum+hasha) ++ans;
}
printf("%d", ans);
return 0;
}