提高1 蚯蚓排队 TLE 64分求调

[赵泽龙]

思路就是在拼接和拆分时重新计算附近 2k - 2 个字符的答案

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 550000;
const int mod = 998244353;
const int maxk = 51;
const int MOD = (1 << 24) - 1;
int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
    while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}
struct Hash
{
    struct edge
    {
        unsigned long long x;
        int cnt,nxt;
    }e[21000000];
    int head[MOD + 1],tot;
    void add(int x,int d)
    {
        int u = (x & MOD);
        for(int i = head[u];i;i = e[i].nxt)
        {
            if(e[i].x == x)
            {
                e[i].cnt += d;
                return ;
            }
        }
        e[++tot].nxt = head[u];
        head[u] = tot;
        e[tot].cnt = d;
        e[tot].x = x;
    }
    int query(int x)
    {
        int u = (x & MOD);
        for(int i = head[u];i;i = e[i].nxt)
        {
            if(e[i].x == x)
            {
                return e[i].cnt;
            }
        }
        return 0;
    }
}h;
unsigned long long g[maxk << 1 + 10],bin[maxk << 1 + 10];
int f[maxk << 1 + 10];
int pre[maxn],nxt[maxn],cnt[maxn];
int a[maxn];
int n,m,p;
void merge()
{
    int x = read(),y = read();
    memset(f,0,sizeof(f));
    int L = maxk,R = L - 1;
    for(int i = x;i && L > 1;i = pre[i])
    {
        f[--L] = a[i];
    }
    for(int i = y;i && R + 1 < maxk * 2;i = nxt[i])
    {
        f[++R] = a[i];
    }
    for(int i = 1;i <= R;i++)
    {
        g[i] = g[i - 1] * p + f[i];
    }
    for(int i = L;i < maxk;i++)
    {
        for(int j = maxk;j <= min(R, i + 49);j++)
        {
            h.add(g[j] - g[i - 1] * bin[j - i + 1],1);
        }
    }
    nxt[x] = y;
    pre[y] = x;
}
void split()
{
    int x = read();
    int y = nxt[x];
    memset(f,0,sizeof(f));
    int L = maxk,R = L - 1;
    for(int i = x;i && L > 1;i = pre[i])
    {
        f[--L] = a[i];
    }
    for(int i = y;i && R + 1 < maxk * 2;i = nxt[i])
    {
        f[++R] = a[i];
    }
    for(int i = 1;i <= R;i++)
    {
        g[i] = g[i - 1] * p + f[i];
    }
    for(int i = L;i < maxk;i++)
    {
        for(int j = maxk;j <= min(R,i + 49);j++)
        {
            h.add(g[j] - g[i - 1] * bin[j - i + 1],-1);
        }
    }
    nxt[x] = 0;
    pre[y] = 0;
}
char s[11000000];

int query()
{
    scanf("%s",s + 1);
    int k = read(),ans = 1,n = strlen(s + 1);
    unsigned long long val = 0;
    if(k == 1)
    {
        for(int i = 1;i <= n;i++)
        {
            ans = (ans * cnt[s[i]]) % mod;
        }
        return ans;
    }
    for(int i = 1;i <= n;i++)
    {
        val = val * p + s[i];
        if(i > k)
        {
            val -= bin[k] * s[i - k];
        }
        if(i >= k)
        {
            ans = (ans * h.query(val)) % mod;
        }
    }
    return ans;
}

signed main()
{
    n = read();
    m = read();
    bin[0] = 1;
    p = 19260817;
    for(int i = 1;i < maxk;i++)
    {
        bin[i] = bin[i - 1] * p;
    }
    for(int i = 1;i <= n;i++)
    {
        a[i] = read();
        a[i] = a[i] + '0';
        cnt[a[i]]++;
    }
    while(m--)
    {
        int opt = read();
        if(opt == 1)
        {
            merge();
        }
        else if(opt == 2)
        {
            split();
        }
        else
        {
            cout << query() << '\n';
        }
    }
    return 0;
}