Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC optimize("Ofast")
- //#pragma GCC optimize ("unroll-loops")
- //#pragma GCC optimize ("fast-math")
- #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- //#include <bits/stdc++.h>
- #include <iostream>
- #include <algorithm>
- #include <string>
- #include <cmath>
- #include <vector>
- #include <map>
- #include <set>
- #include <list>
- #include <ctime>
- #include <stack>
- #include <queue>
- #include <iomanip>
- #include <cstdlib>
- #include <unordered_map>
- #include <unordered_set>
- #include <cstddef>
- #include <deque>
- #include <cstdio>
- #include <fstream>
- #include <random>
- #include <climits>
- #include <cassert>
- #include <chrono>
- /** Begin fast allocation */
- const int MAX_MEM = 2e8;
- int mpos = 0;
- char mem[MAX_MEM];
- inline void * operator new (size_t n) {
- assert((mpos += n) <= MAX_MEM);
- return (void *)(mem + mpos - n);
- }
- void operator delete (void *) noexcept { } // must have!
- void operator delete (void *, size_t) noexcept { } // must have!
- /** End fast allocation */
- /** Interface */
- inline int readChar();
- template <class T = int> inline T readInt();
- template <class T> inline void writeInt( T x, char end = 0 );
- inline void writeChar( int x );
- inline void writeWord( const char *s );
- /** Read */
- static const int buf_size = 4096;
- inline int getChar() {
- static char buf[buf_size];
- static int len = 0, pos = 0;
- if (pos == len)
- pos = 0, len = fread(buf, 1, buf_size, stdin);
- if (pos == len)
- return -1;
- return buf[pos++];
- }
- inline int readChar() {
- int c = getChar();
- while (c <= 32)
- c = getChar();
- return c;
- }
- template <class T>
- inline T readInt() {
- int s = 1, c = readChar();
- T x = 0;
- if (c == '-')
- s = -1, c = getChar();
- while ('0' <= c && c <= '9')
- x = x * 10 + c - '0', c = getChar();
- return s == 1 ? x : -x;
- }
- /** Write */
- static int write_pos = 0;
- static char write_buf[buf_size];
- inline void writeChar( int x ) {
- if (write_pos == buf_size)
- fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
- write_buf[write_pos++] = x;
- }
- template <class T>
- inline void writeInt( T x, char end ) {
- if (x < 0)
- writeChar('-'), x = -x;
- char s[24];
- int n = 0;
- while (x || !n)
- s[n++] = '0' + x % 10, x /= 10;
- while (n--)
- writeChar(s[n]);
- if (end)
- writeChar(end);
- }
- inline void writeWord( const char *s ) {
- while (*s)
- writeChar(*s++);
- }
- struct Flusher {
- ~Flusher() {
- if (write_pos)
- fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
- }
- } flusher;
- using namespace std;
- #define forn(i, j, k) for(int i = (int)(j); i < (int)(k); i++)
- #define forn1(i, j, k) for(int i = (int)(j); i <= (int)(k); i++)
- #define pb push_back
- #define mp make_pair
- #define f first
- #define s second
- #define all(x) begin(x), end(x)
- #define sz(a) ((int)((a).size()))
- #define endl '\n'
- const int INF = 1e9 + 1;
- const long long MOD = 998244353;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef long double ld;
- std::mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
- struct hash_function {
- size_t operator() (const pair<int, int>& p) const {
- return p.first ^ p.second;
- }
- };
- const int maxn = 1'000'007;
- vector<int> inv(vector<int> a) {
- vector<int> p(a.size());
- for (int i = 0; i < int(a.size()); ++i) {
- p[a[i] - 1] = i + 1;
- }
- return p;
- }
- vector<int> compress(vector<int> a) {
- vector<int> b = a;
- sort(b.begin(), b.end());
- unordered_map<int, int> m;
- for (int x : b)
- if (!m.count(x))
- m[x] = m.size();
- for (int &x : a)
- x = m[x] + 1;
- return a;
- }
- struct Fenwick {
- vector<int> t;
- int n;
- explicit Fenwick(int _n) : t(_n, 0), n(_n) {}
- int sum (int r) {
- int res = 0;
- for (; r > 0; r -= r & -r) {
- res += t[r];
- }
- return res;
- }
- int sum (int l, int r) {
- if (l == 0) {
- return sum(r);
- }
- return sum(r) - sum(l-1);
- }
- void add (int pos, int delta) {
- for (; pos <= n; pos += pos & -pos) {
- t[pos] += delta;
- }
- }
- };
- vector<int> prefix_function(vector<int>& s, vector<int>& perm) {
- assert(s.size() == perm.size());
- int n = int(s.size());
- Fenwick tree(maxn);
- vector<int> p(n, 0);
- for (int i = 1; i < n; i++) {
- int cur = p[i - 1];
- // уменьшаем cur значение, пока новый символ не сматчится
- assert(cur < n);
- while (tree.sum(perm[i]) != s[cur] && cur > 0) {
- for (int j = i - cur; j < i - p[cur - 1]; ++j) {
- tree.add(perm[j], -1);
- }
- cur = p[cur - 1];
- assert(cur < n);
- }
- tree.add(perm[i], 1);
- assert(cur < n);
- if (tree.sum(perm[i]) - 1 == s[cur]) {
- p[i] = cur + 1;
- }
- }
- return p;
- }
- vector<int> match_per(vector<int>& arr) {
- Fenwick tree(maxn);
- vector<int> ans;
- for (auto& i : arr) {
- tree.add(i, 1);
- ans.push_back(tree.sum(i) - 1);
- }
- return ans;
- }
- void solve() {
- int n, m;
- cin >> n >> m;
- vector<int> perm(n);
- for (auto& i : perm) cin >> i;
- perm = inv(perm);
- vector<int> arr(m);
- for (auto& i : arr) cin >> i;
- arr = compress(arr);
- vector<int> b = match_per(perm);
- vector<int> a = prefix_function(b, perm);
- vector<int> ans;
- int pref = 0;
- Fenwick tree(maxn);
- for (int i = 0; i < m; ++i) {
- int el = arr[i];
- while (pref > 0 && (pref == n || b[pref] != tree.sum(el))) {
- for (int j = i - pref; j < i - a[pref - 1]; ++j) {
- tree.add(arr[j], -1);
- }
- pref = a[pref - 1];
- }
- if (b[pref] == tree.sum(el)) {
- pref++;
- }
- tree.add(el, 1);
- if (pref == n) {
- ans.push_back(i);
- }
- }
- cout << int(ans.size()) << endl;
- for (auto& i : ans) {
- cout << i - n + 2 << " ";
- }
- cout << endl;
- }
- int32_t main() {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- cout.tie(NULL);
- cout.precision(30);
- int t;
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- t = 1;
- #else
- //freopen("inputik.txt", "r", stdin);
- //freopen("outputik.txt", "w", stdout);
- t = 1;
- #endif
- while (t--) {
- solve();
- #ifdef LOCAL
- cout << "__________________________" << endl;
- #endif
- }
- #ifdef LOCAL
- cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
- #endif
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement