bzoj2384

树状数组+KMP

匹配问题上KMP

但是问题在于如何判断两个位置相等，我们认为如果一个位置之前比他小的数数量相同那么就是相等。

那么我们用树状数组动态维护这个东西，每次跳nxt的时候用树状数组删除数。因为每个数只加入一次，所以复杂度是nlogn的，为什么这样是对的呢？我们这么想，对于当前加入最后的一个字符，这个肯定是对的，如果我们再加入一个数，如果比这个数小，那么影响，否则不影响，现在两个串同时加入两个数，那么如果一个相对大一个相对小，那么这个位置肯定是不匹配的，所以即使影响了之前也没关系。大概是这样吧

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 1e6 + ;

int n, m;

int a[N], tree[N], s[N], v[N], b[N], c[N], nxt[N], ans[N];

void update(int x, int d)

{

    for(; x <= m; x += x & -x) tree[x] += d;

}

int query(int x)

{

    int ret = ;

    for(; x; x -= x & -x) ret += tree[x];

    return ret;

}

int main()

{

    scanf("%d%d", &n, &m);

    for(int i = ; i <= n; ++i) scanf("%d", &a[i]), s[a[i]] = i;

    for(int i = ; i <= n; ++i) v[i] = query(s[i]), update(s[i], );

    for(int i = ; i <= m; ++i) scanf("%d", &b[i]), c[i] = b[i];

    memset(tree, , sizeof(tree));

    for(int i = , j = ; i <= n; ++i)

    {

        while(query(s[i]) != v[j + ])

        {

            for(int k = i - j; k < i - nxt[j]; ++k) update(s[k], -);

            j = nxt[j];

        }

        if(query(s[i]) == v[j + ])

        {

            update(s[i], );

            ++j;

        }

        nxt[i] = j;

    }

    sort(c + , c + m + );

    memset(tree, , sizeof(tree));

    for(int i = , j = ; i <= m; ++i)

    {

        b[i] = lower_bound(c + , c + m + , b[i]) - c;

        while(j == n || query(b[i]) != v[j + ])

        {

            for(int k = i - j; k < i - nxt[j]; ++k) update(b[k], -);

            j = nxt[j];

        }

        if(query(b[i]) == v[j + ])

        {

            ++j;

            update(b[i], );

        }

        if(j == n) ans[++ans[]] = i - j + ;

    }

    printf("%d\n", ans[]);

    for(int i = ; i <= ans[]; ++i) printf("%d%c", ans[i], i == ans[] ? '\n' : ' ');

    return ;

}

巴特西

bzoj2384

最新文章

热门文章