(POI) XXI OI Round II - day 1 Task Criminal

https://szkopul.edu.pl/problemset/problem/APWi6y6XTt5ujve8ynI_FNJ1/site/?key=statement

神奇的線性解XDD

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <utility>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cassert>
using namespace std;

#define LL   long long
#define ld   long double
#define pii  pair<int,int>
#define pLL  pair<LL,LL>
#define vint vector<int>
#define vLL  vector<LL>
#define vpii vector<pii>

#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define F first
#define S second
#define MP make_pair
#define PB push_back

#define Si(x) scanf("%d",&(x));
#define Sii(x,y) scanf("%d %d",&(x),&(y));
#define Siii(x,y,z) scanf("%d %d %d",&(x),&(y),&(z));
#define Siiii(x,y,z,w) scanf("%d %d %d %d",&(x),&(y),&(z),&(w));
#define Siiiii(x,y,z,w,a) scanf("%d %d %d %d %d",&(x),&(y),&(z),&(w),&(a));
#define Siiiiii(x,y,z,w,a,b) scanf("%d %d %d %d %d %d",&(x),&(y),&(z),&(w),&(a),&(b));
#define SL(x) scanf("%lld",&(x));
#define SLL(x,y) scanf("%lld %lld",&(x),&(y));
#define SLLL(x,y,z) scanf("%lld %lld %lld",&(x),&(y),&(z));
#define SLLLL(x,y,z,w) scanf("%lld %lld %lld %lld",&(x),&(y),&(z),&(w));
#define SLLLLL(x,y,z,w,a) scanf("%lld %lld %lld %lld %lld",&(x),&(y),&(z),&(w),&(a));
#define SLLLLLL(x,y,z,w,a,b) scanf("%lld %lld %lld %lld %lld %lld",&(x),&(y),&(z),&(w),&(a),&(b));

#define Pi(x) printf("%d\n",(x));
#define Pii(x,y) printf("%d %d\n",(x),(y));
#define Piii(x,y,z) printf("%d %d %d\n",(x),(y),(z));
#define Piiii(x,y,z,w) printf("%d %d %d %d\n",(x),(y),(z),(w));
#define Piiiii(a,b,c,d,e) printf("%d %d %d %d %d\n",(a),(b),(c),(d),(e));
#define Piiiiii(a,b,c,d,e,f) printf("%d %d %d %d %d %d\n",(a),(b),(c),(d),(e),(f));
#define PL(x) printf("%lld\n",(x)*1LL);
#define PLL(x,y) printf("%lld %lld\n",(x)*1LL,(y)*1LL);
#define PLLL(x,y,z) printf("%lld %lld %lld\n",(x)*1LL,(y)*1LL,(z)*1LL);
#define PLLLL(x,y,z,w) printf("%lld %lld %lld %lld\n",(x)*1LL,(y)*1LL,(z)*1LL,(w)*1LL);
#define PLLLLL(a,b,c,d,e) printf("%lld %lld %lld %lld %lld\n",(a)*1LL,(b)*1LL,(c)*1LL,(d)*1LL,(e)*1LL);
#define PLLLLLL(a,b,c,d,e,f) printf("%lld %lld %lld %lld %lld %lld\n",(a)*1LL,(b)*1LL,(c)*1LL,(d)*1LL,(e)*1LL,(f)*1LL);

#define Pi1(x) printf("%d",  (x));
#define PL1(x) printf("%lld",(x));
#define Pspace putchar(' ');
#define Pendl  puts("");

#define MEM0(x) memset( (x), 0, sizeof( (x) ) )
#define MEM1(x) memset( (x),-1, sizeof( (x) ) )
#define REP1(i,n)  for (int i = 1; (n) >= i ; ++i)
#define REP0(i,n)  for (int i = 0; (n) >  i ; ++i)

int myRnd() {
    return abs(  ((rand()<<15) ^ rand()) );
}

int myRnd(int L,int R) {
    return abs(( (rand()<<15)^rand() ) ) % (R-L+1) + L;
}

void Parr(int *arr,int L,int R) {
    for (int i=L;R>=i;i++) {
        printf("%d%c",arr[i]," \n"[i==R]);
    }
}

void Pvec(vint v) {
    for (int i=0;SZ(v)>i;i++) {
        printf("%d%c",v[i]," \n"[i==SZ(v)-1]);
    }
}

void Sarr(int *arr,int L,int R) {
    for (int i=L;R>=i;i++)
    {
        Si(arr[i]);
    }
}

const int N = 1e6 + 6;

int a[N];
int x[N];
int on_x[N];
int y[N];
int on_y[N];
int pre[N],suf[N];
int last[N];

int now_ans;
int pre_cnt[N];
int suf_cnt[N];

bool can[N];

int n;

void add(int L,int R)
{
    L = max(L,1);
    R = min(R,n);
    if (L>R) return;
    for (int i=L;R>=i;i++)
    {
        int now = a[i];
        pre_cnt[now]++;
        if (pre_cnt[now] == 1 && suf_cnt[now]>0 && now > 0) now_ans++;
    }
}

void del(int L,int R)
{
    L = max(L,1);
    R = min(R,n);
    if (L>R) return;
    for (int i=L;R>=i;i++)
    {
        int now = a[i];
        suf_cnt[now]--;
        if (suf_cnt[now] == 0 && pre_cnt[now]>0 && now > 0) now_ans--;
    }
}

int main () {
    //srand(time(NULL));
    int k;
    Sii(n,k);
    Sarr(a,1,n);
    int m,l;
    Sii(m,l);
    //if (m==l && l==1) for(;;);
    REP1(i,m)
    {
        Si(x[i]);
        on_x[ x[i] ] = i;
        can[ x[i] ] = 1;
    }
    REP1(i,l)
    {
        Si(y[i]);
        on_y[ y[i] ] = i;
        can[ y[i] ] = 1;
    }
    REP1(i,m)
    {
        last[i] = -1;
    }
    pre[0] = -1;
    REP1(i,n)
    {
        int now = a[i];
        if (!on_x[now])
        {
            pre[i] = pre[i-1];
            continue;
        }
        int tmpp;
        if (on_x[now] == 1)
        {
            //tmpp = last[1];
            last[1] = i;
        }
        else
        {
            last[ on_x[now] ] = last[ on_x[now]-1 ];
        }
        pre[i] = last[m];
        //if (pre[i] != -1) pre[i]--;
        //if (m == 1) pre[i] = tmpp;
    }
    suf[n+1] = n+1;
    REP1(i,l)
    {
        last[i] = n+1;
    }
    for (int i=n;i>=1;i--)
    {
        int now = a[i];
        if (!on_y[now])
        {
            suf[i] = suf[i+1];
            continue;
        }
        int tmpp;
        if (on_y[now] == 1)
        {
            //tmpp = last[1];
            last[1] = i;
        }
        else
        {
            last[ on_y[now] ] = last[ on_y[now]-1 ];
        }
        suf[i] = last[l];
        //if (suf[i] != n+1) suf[i]++;
        //if (l==1) suf[i] = tmpp;
    }
    REP1(i,n)
    {
        suf_cnt[ a[i] ]++;
    }
    //cout<<"pre = ";Parr(pre,1,n);
    //cout<<"suf = ";Parr(suf,1,n);
    int last_pre = 0,last_suf = 0;
    vint ans;
    for (int i=2;n>i;i++)
    {
        del(last_suf+1,suf[i]);
        //cout<<"last_suf+1 = "<<last_suf+1<<" , suf = "<<suf[i+1]<<endl;
        last_suf = suf[i];
        add(last_pre+1,pre[i]-1);
        //cout<<"last_pre + 1 = "<<last_pre+1<<" , pre = "<<pre[i-1]<<endl;
        last_pre = pre[i]-1;
        if (a[i] == x[m] && now_ans != 0)
        {
            ans.PB(i);
        }
        //cout<<"i = "<<i<<" , now_ans = "<<now_ans<<endl;
    }
    Pi(SZ(ans));
    Pvec(ans);
}