题目
具体思路与KMP板子很像;
大致思路是将两个数字的排名来当字符比较
用树状数组 \(log_2(n)\) 的复杂度来找排名。
一定要注意边界问题
具体实现思路可以看代码
(PS:有奆佬说这题很板子，也许是我太弱了叭QAQ)
//9:30 开始写题，有些思路
// 40 思路被pass，不会写了
// 55 决定去看kmp板子及思想找思路
// 其主要思想是当出现字符串不匹配的情况时，
// 可以知道一部分之前已经匹配的的文本内容，
// 利用这些信息避免从头再去做匹配，而其中前缀表担负重任。
// 也许有用？？？
//10:50 什么思路依然没有，感觉不会，要寄
//11:30 看题解吧，寄寄寄
//15:30 看了题解也学不会呜呜呜┭┮﹏┭┮
//16:20 蛙趣，终于整明白这道题了
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int n, m, s;
int a[5211314 >> 3], b[5211314 >> 3], bit[5211314 >> 3];
int rank1[5211314 >> 3], rank2[5211314 >> 3], nex[5211314 >> 3];
int ans[5211314 >> 2], tot;
struct BinaryIndexedTree {
inline int lowbit(int x) {
return (x & (-x));
}
inline void Add(int x, int val) {
while (x <= s) {
bit[x] += val;
x += lowbit(x);
}
return;
}
inline int Query(int x) {
int ans = 0;
while (x > 0) {
ans += bit[x];
x -= lowbit(x);
}
return ans;
}
}tree;
inline bool compared(int x, int y) {
if (tree.Query(y) == rank1[x] && tree.Query(y - 1) == rank2[x]) {
return true;
}
else {
return false;
}
}
int main() {
cin >> n >> m >> s;
for (int i = 1; i <= n; ++ i) cin >> a[i];
for (int i = 1; i <= m; ++ i) {
cin >> b[i];
tree.Add(b[i], 1);
rank1[i] = tree.Query(b[i]);
rank2[i] = tree.Query(b[i] - 1);
//将b数组的排名保存
}
memset(bit, 0, sizeof(bit));
nex[0] = 1;
for (int i = 2, j = 0; i <= m; ++ i) {
tree.Add(b[i], 1);
while (j > 0 && !compared(j + 1, b[i])) {
for (int k = i - j; k < i - nex[j]; ++ k) {
//注意，此时j没有加1。则i-j到i-nex[j] - 1为以j为下标的数组向右移动的长度
//可以自己手模一下
//因为下一个不能将nex[j]的点减去，所以
tree.Add(b[k], -1);
}
j = nex[j];
}
if (compared(j + 1, b[i]) == true) j ++;
//这里可以抽象的理解为每次b[j+1]与b[j]的排名名次的差和b[i]与b[i-1]的排名名次的差一样
//也可以抽象的理解为每次加在的排名区间一样
//(如在数组1,2,5后插入4中树状数组的bit[4]和bit[3]
// 与在数组1,2,10后插入5中的树状数组bit[5]与bit[4]的值一样)
nex[i] = j;
}//处理出来自己的nex
memset(bit, 0, sizeof(bit));
for (int i = 1, j = 0; i <= n; ++ i) {
tree.Add(a[i], 1);
while (j > 0 && !compared(j + 1, a[i])) {
for (int k = i - j; k < i - nex[j]; ++ k) {
tree.Add(a[k], -1);
}
j = nex[j];
}
if (compared(j + 1, a[i])) j ++;
if (j == m) {
ans[++ tot] = i - m + 1;
for (int q = i - j + 1; q <= i - nex[j]; ++ q) {
//此时j已经加1，所以这里i - j + 1到i - nex[j]为以j为下标的数组移动的长度
//可以自己手模一下
tree.Add(a[q], -1);
}
j = nex[j];
}
}
cout << tot << endl;
for (int i = 1; i <= tot; ++ i) {
cout << ans[i] << endl;
}
return 0;
}