← Real problems

noi17p2

unratedStatement on DMOJ

CP Lang

40 lines0.3 spec
// NOI 2017 "Earthworm Queue": worms of length 1..=6 join and split queues;
// for a string s and k, multiply over its k-windows how many times each one
// appears as k consecutive worms in some queue. Windows are at most 50 long,
// so a join or split changes only the windows crossing the cut: count them in
// a hash counter, adding or removing each crossing window.
use std.strings.{HashVal}

type Z = Mod<998244353>
enum Op = Join(i: W, j: W) | Split(i: W) | Ask(s: Str, k: 1..=50)

let (n, q) = read<(1..=2e5, 1..=5e5)>()
domain W = 1..=n
let len = read<[W]1..=6>()
var next: [W]?W = None
var prev: [W]?W = None
let hasher = RollingHash.new(List<Int>())
var seen = Counter<HashVal, Int>(0)
for w in W:
    seen.add(hasher.hash_of([len[w]]), 1)

fn crossing(i: W, j: W, sign: Int):
    let left = List(iterate(Some(i), w => prev[w]).take(49))
    let right = List(iterate(Some(j), w => next[w]).take(49))
    for a in 1..=left.len:
        var h = RollingHash.new(left.take(a).rev.map(w => len[w]))
        for w in right.take(50 - a):
            h.push(len[w])
            seen.add(h.all, sign)

for op in read<[q]Op>():
    match op:
        Join(i, j) =>
            crossing(i, j, 1)
            (next[i], prev[j]) = (Some(j), Some(i))
        Split(i) =>
            let j = next[i]!
            crossing(i, j, -1)
            (next[i], prev[j]) = (None, None)
        Ask(s, k) =>
            print(s.windows(k).map(w => Z(seen.get(hasher.hash_of(w.map(c => c.digit()))))).prod())

Accepted C++

397 lines · 3.35 s on the judge
#pragma GCC optimize("Ofast")

#include "bits/extc++.h"

using namespace std;

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t;
    ((cerr << " | " << u), ...);
    cerr << endl;
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__)
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

using u32 = uint32_t;
using u64 = uint64_t;

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

template <typename T>
void sort_unique(T& arr) {
    sort(begin(arr), end(arr));
    arr.erase(unique(begin(arr), end(arr)), arr.end());
}

template <int MOD>
struct Mint {
    static constexpr int norm(long x) {
        x %= MOD;
        if (x < 0) {
            x += MOD;
        }
        return int(x);
    }

    int x;

    constexpr Mint() : x(0) {}
    constexpr Mint(long x) : x(norm(x)) {}

    static constexpr Mint from_unchecked(int x) {
        Mint m;
        m.x = x;
        return m;
    }

    friend ostream& operator<<(ostream& out, const Mint& m) {
        return out << m.x;
    }

    constexpr Mint operator-() const {
        if (!x) {
            return {};
        }
        return Mint::from_unchecked(MOD - x);
    }

    constexpr Mint& operator+=(const Mint& m) {
        x += m.x;
        if (x >= MOD) {
            x -= MOD;
        }
        return *this;
    }
    constexpr Mint& operator-=(const Mint& m) {
        return *this += -m;
    }

    constexpr Mint& operator*=(const Mint& m) {
        x = int(long(x) * m.x % MOD);
        return *this;
    }

    constexpr friend Mint operator+(Mint a, const Mint& b) {
        return a += b;
    }
    constexpr friend Mint operator-(Mint a, const Mint& b) {
        return a -= b;
    }
    constexpr friend Mint operator*(Mint a, const Mint& b) {
        return a *= b;
    }
};

constexpr int MAXK = 55;

template <typename T, int MAXN>
struct Pow {
    T v[MAXN];

    constexpr Pow(T base) : v {} {
        v[0] = 1;
        for (int i = 1; i < MAXN; i++) {
            v[i] = v[i - 1] * base;
        }
    }

    constexpr const T& operator[](int ind) const {
        return v[ind];
    }
};

template <typename T, int BASE>
struct Hash {
    static constexpr Pow<T, MAXK> pow {BASE};

    int len;
    T x;

    Hash() : len(0), x() {}
    Hash(int x) : len(1), x(x) {}
    Hash(char c) : Hash(c - '0') {}
    Hash(int len, T x) : len(len), x(x) {}

    Hash operator+(const Hash& h) const {
        return {len + h.len, x * pow[h.len] + h.x};
    }

    Hash sub_pref(const Hash& h) const {
        return {len - h.len, x - pow[len - h.len] * h.x};
    }

    explicit operator u32() const {
        return x.x;
    }
};

template <typename A, typename B>
struct HashMult {
    A a;
    B b;

    HashMult() : a(), b() {}
    HashMult(int x) : a(x), b(x) {}
    HashMult(char c) : a(c), b(c) {}
    HashMult(const A& a, const B& b) : a(a), b(b) {}

    HashMult operator+(const HashMult& h) const {
        return {a + h.a, b + h.b};
    }

    HashMult sub_pref(const HashMult& h) const {
        return {a.sub_pref(h.a), b.sub_pref(h.b)};
    }
};

constexpr int MOD = 998244353;

using mint = Mint<MOD>;
// using H = HashMult<Hash<mint, 1412>, Hash<mint, 2141>>;

// u64 to_u64(const H& h) {
//     return (u64(u32(h.a)) << 32) | u32(h.b);
// }

using H = Hash<u64, 2141>;

u64 to_u64(const H& h) {
    return h.x;
}

vector<u64> part_hash(const string& s, int kv) {
    assert(kv <= sz(s));

    vector<u64> ans;

    H h;

    for (int i = 0; i < kv; i++) {
        h = h + s[i];
    }

    ans.push_back(to_u64(h));
    for (int i = kv; i < sz(s); i++) {
        h = h.sub_pref(s[i - kv]) + s[i];

        ans.push_back(to_u64(h));
    }

    return ans;
}

struct Node {
    int v;
    Node *l, *r;
};

struct HT {
    // map<u64, int> keys;
    // HT(const vector<u64>&) {}
    // int& operator[](u64 x) {
    //     return keys[x];
    // }
    // vector<u64> keys;
    // vector<int> vals;
    // int ignore = 0;

    // HT(const vector<u64>& _keys) : keys(_keys), vals(sz(keys)) {
    //     sort_unique(keys);
    // }

    // int& operator[](u64 x) {
    //     auto it = lower_bound(begin(keys), end(keys), x);

    //     if (it != keys.end() && *it == x) {
    //         return vals[it - keys.begin()];
    //     }
    //     return ignore;
    // }

    int n, ignore = 0;
    vector<u64> keys;
    vector<int> vals;

    int to_ind(u64 x) {
        x ^= x >> 33;
        x ^= x << 11;
        x ^= x >> 22;
        return x & (n - 1);
    }

    template <bool INSERT>
    int& find(u64 k) {
        for (int i = to_ind(k);; i = (i + 1) & (n - 1)) {
            if (keys[i] == -1) {
                if constexpr (INSERT) {
                    keys[i] = k;
                    return vals[i];
                } else {
                    return ignore;
                }
            }
            if (keys[i] == k) {
                return vals[i];
            }
        }
    }

    HT(const vector<u64>& init_keys)
        : n(1 << (__lg(sz(init_keys) + 10) + 2)), keys(n, -1), vals(n) {
        for (auto& a : init_keys) {
            find<true>(a);
        }
    }

    int& operator[](u64 x) {
        return find<false>(x);
    }
};

void solve() {
    int n, q;
    cin >> n >> q;
    int arr[n];
    for (auto& a : arr) {
        cin >> a;
    }

    vector<string> s_queries;
    vector<array<int, 3>> queries(q);

    for (auto& [ty, u, v] : queries) {
        cin >> ty;

        if (ty == 1) {
            cin >> u >> v;
            u--;
            v--;
        } else if (ty == 2) {
            cin >> u;
            u--;
        } else {
            string s;
            cin >> s >> v;
            u = sz(s_queries);
            s_queries.push_back(s);
        }
    }

    Node nodes[n] {};
    for (int i = 0; i < n; i++) {
        nodes[i].v = arr[i];
    }

    vector<HT> hts;
    vector<vector<u64>> s_part(sz(s_queries));

    for (int ckv = 0; ckv < MAXK; ckv++) {
        vector<u64> cvals;

        for (auto& [ty, sind, kv] : queries) {
            if (!(ty == 3 && kv == ckv)) {
                continue;
            }

            string& s = s_queries[sind];
            s_part[sind] = part_hash(s, kv);
            cvals.insert(cvals.end(), begin(s_part[sind]), end(s_part[sind]));
        }

        hts.emplace_back(cvals);
    }

    for (auto& a : arr) {
        hts[1][to_u64(H(a))]++;
    }

    auto update = [&](Node* u, Node* v, int inc) -> void {
        vector<H> u_suff, v_pref;

        {
            Node* o = u;

            u_suff.emplace_back();
            while (o && sz(u_suff) < MAXK) {
                u_suff.push_back(H(o->v) + u_suff.back());
                o = o->l;
            }
        }

        {
            Node* o = v;

            v_pref.emplace_back();
            while (o && sz(v_pref) < MAXK) {
                v_pref.push_back(v_pref.back() + H(o->v));
                o = o->r;
            }
        }

        for (int k = 1; k < MAXK; k++) {
            for (int ql = min(sz(u_suff) - 1, k - 1); ql >= 1; ql--) {
                int qr = k - ql;
                assert(qr >= 1);

                if (qr >= sz(v_pref)) {
                    break;
                }

                hts[k][to_u64(u_suff[ql] + v_pref[qr])] += inc;
            }
        }
    };

    auto do_merge = [&](Node* u, Node* v) -> void {
        update(u, v, +1);

        u->r = v;
        v->l = u;
    };

    auto do_split = [&](Node* u) -> void {
        Node* v = u->r;

        update(u, v, -1);

        u->r = nullptr;
        v->l = nullptr;
    };

    for (auto& [ty, u, v] : queries) {
        if (ty == 1) {
            do_merge(&nodes[u], &nodes[v]);
        } else if (ty == 2) {
            do_split(&nodes[u]);
        } else {
            mint ans = 1;

            int kv = v;

            for (auto& a : s_part[u]) {
                ans *= hts[kv][a];
            }

            cout << ans << endl;
        }
    }
}

int main() {
    cin.tie(nullptr);
    cin.exceptions(ios::failbit);
    ios_base::sync_with_stdio(false);
    solve();
}