NOI 2017 - 蚯蚓排队
Problem Statement: LOJ2303
Solution
Let $K$ be the maximum $k$ across all queries. For the full solution, $K = 50$.
We can solve this problem using brute force and hashing. When merging/separating queues, we enumerate all substrings covering the intersection of length less than or equal to $K$. We find the frequency of each substring using a hash table and maintain the queues using a doubly-linked list.
At first glance, we may think the time complexity is $\mathcal{O}(mL^2)$, because we add/remove at most $\mathcal{O}(K^2)$ substrings for each query. However, the actual number is smaller.
Looking back to the problem, we see another constraint $c \leq 10^3$, which means that the number of queries of type $2$ is at most $c$. Because the number of substrings at a given time is bounded by $\mathcal{O}(nK)$, the actual number of substrings we add/remove is $\mathcal{O}(nK + cK^2)$, because we remove at most $\mathcal{O}(cK^2)$ substrings. This runs in time, but with a large constant factor.
To avoid hashing collisions, consider using a $64$-bit modulus,
with __int128_t for multiplication. To decrease the
constant factor, use gp_hash_table instead of std::unordered_map. Then,
you should get AC.
Implementation
/**
* @author n685
* @brief
* @date 2024-07-31 15:14:32
*
*
*/
#include <bits/stdc++.h>
#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbgP(...) 420
#define dbgRP(...) 420420
void nline() {}
void bar() {}
#endif
template <class T> constexpr std::pair<T, T> exEucl(T a, T b) {
if (a < b) {
auto [x, y] = exEucl(b, a);
return {y, x};
}
if (b == 0) {
assert(a == 1);
return {1, 0};
}
auto [x, y] = exEucl(b, a % b);
return {y, x - (a / b) * y};
}
template <class Md, class V = int64_t>
// requires std::signed_integral<std::decay_t<decltype(Md::value)>>
struct Mod {
using T = std::decay_t<decltype(Md::value)>;
T val = 0;
static constexpr T normalize(auto val) {
using U = decltype(Md::value + val);
U uval = static_cast<U>(val);
U umd = static_cast<U>(Md::value);
if (uval <= -umd || umd <= uval) {
uval %= umd;
}
if (val < 0) {
uval += umd;
}
return static_cast<T>(uval);
}
constexpr Mod() : val(0) {}
constexpr explicit Mod(auto _val) : val(normalize(_val)) {}
static inline const Mod ZERO = Mod(0);
static inline const Mod ONE = Mod(1);
static inline const Mod TWO = Mod(2);
// addition
constexpr Mod &operator+=(Mod b) {
val += b.val;
if (val >= Md::value) {
val -= Md::value;
}
return *this;
}
friend constexpr Mod operator+(Mod a, Mod b) { return (a += b); }
constexpr Mod &operator++() { return (*this += Mod(1)); }
constexpr Mod operator++(int) {
Mod res = *this;
++(*this);
return res;
}
// subtraction
constexpr Mod &operator-=(Mod b) {
val -= b.val;
if (val < 0) {
val += Md::value;
}
return *this;
}
friend constexpr Mod operator-(Mod a, Mod b) { return (a -= b); }
constexpr Mod &operator--() { return (*this -= Mod(1)); }
constexpr Mod operator--(int) {
Mod res = *this;
--(*this);
return res;
}
// negation
constexpr Mod operator-() const { return Mod(-val); }
// multiplication
constexpr Mod &operator*=(Mod b) {
// auto q = static_cast<long long>(static_cast<long double>(val) * b.val /
// Md::value);
// val = normalize(val * b.val - q * Md::value);
// return *this;
val = static_cast<T>(static_cast<V>(val) * b.val % Md::value);
return *this;
}
friend constexpr Mod operator*(Mod a, Mod b) { return (a *= b); }
constexpr Mod binpow(std::integral auto b) const {
Mod res = Mod(1), a = *this;
while (b > 0) {
if (b % 2 == 1) {
res *= a;
}
a *= a;
b /= 2;
}
return res;
}
// factorial
// align with fft, if code fails to compile make this smaller (if using array)
static constexpr int MXINV = 1 << 22;
static inline bool init = false;
static inline std::vector<Mod> ff, iff;
static void resetFac() { init = false; }
static void initFac() {
if (init) {
return;
}
ff.resize(MXINV + 1);
ff[0] = Mod(1);
for (int i = 1; i <= MXINV; ++i) {
ff[i] = ff[i - 1] * Mod(i);
}
iff.resize(MXINV + 1);
iff[MXINV] = ff[MXINV].largeInv();
for (int i = MXINV - 1; i >= 0; --i) {
iff[i] = iff[i + 1] * Mod(i + 1);
}
init = true;
}
static Mod fac(int v) {
if (!init) {
initFac();
}
return ff[v];
}
static Mod ifac(int v) {
if (!init) {
initFac();
}
return iff[v];
}
static Mod comb(int n, int k) {
if (n < 0 || k < 0 || n < k) {
return Mod(0);
}
return fac(n) * ifac(n - k) * ifac(k);
}
static Mod perm(int n, int k) {
if (n < 0 || k < 0 || n < k) {
return Mod(0);
}
return fac(n) * ifac(n - k);
}
// inverse
Mod smallInv() const {
return ifac(static_cast<int>(val)) * fac(static_cast<int>(val) - 1);
}
constexpr Mod largeInv() const {
return Mod(exEucl(static_cast<V>(val), static_cast<V>(Md::value)).first);
// return binpow(Md::value - 2);
}
Mod inv() const {
if (val <= MXINV) {
return smallInv();
}
return largeInv();
}
// sqrt
std::optional<Mod> sqrt() {
static std::mt19937 rng(
std::chrono::steady_clock::now().time_since_epoch().count());
Mod c = Mod::ZERO;
while ((c * c - *this).binpow((Md::value - 1) / 2) == Mod::ONE) {
c = Mod(rng());
}
if (c == Mod::ZERO) {
return std::nullopt;
}
std::pair<Mod, Mod> res(Mod::ONE, Mod::ZERO), a(c, Mod::ONE);
T b = (Md::value + 1) / 2;
auto mul = [&c, this](const std::pair<Mod, Mod> &u,
const std::pair<Mod, Mod> &v) -> std::pair<Mod, Mod> {
return {u.first * v.first + u.second * v.second * (c * c - *this),
u.second * v.first + u.first * v.second};
};
while (b > 0) {
if (b % 2 == 1) {
res = mul(res, a);
}
a = mul(a, a);
b /= 2;
}
return res.first;
// return std::min(res.first, -res.first);
}
// comparison
constexpr bool operator==(const Mod &b) const = default;
constexpr std::strong_ordering operator<=>(const Mod &b) const = default;
// io
friend std::istream &operator>>(std::istream &in, Mod &a) {
int64_t v;
in >> v;
a = Mod(v);
return in;
}
friend std::ostream &operator<<(std::ostream &out, const Mod &a) {
out << a.val;
return out;
}
// conversion
constexpr T value() const { return val; }
};
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
const auto RANDOM =
std::chrono::high_resolution_clock::now().time_since_epoch().count();
struct chash {
static constexpr long double PI = std::numbers::pi_v<long double>;
// any random-ish large odd number will do
static inline const uint64_t C = static_cast<uint64_t>(2e18 * PI) + 71;
// random 32-bit number
static inline const uint32_t RANDOM = static_cast<uint32_t>(
std::chrono::steady_clock::now().time_since_epoch().count());
auto operator()(uint64_t x) const -> size_t {
// see https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
return __builtin_bswap64((x ^ RANDOM) * C);
}
};
template <std::integral T, class U> using Map = gp_hash_table<T, U, chash>;
// template <class T, class U> using Map = std::unordered_map<T, U>;
constexpr int64_t MOD = (int64_t{1} << 61) - 1;
using Mint =
Mod<std::integral_constant<std::decay_t<decltype(MOD)>, MOD>, __int128_t>;
constexpr int MOD2 = 998244353;
using Mint2 = Mod<std::integral_constant<std::decay_t<decltype(MOD2)>, MOD2>>;
constexpr int MX = 50;
struct LL {
Mint v;
int l = -1, r = -1;
};
int main() {
#ifndef LOCAL
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
#endif
std::mt19937_64 rng(
std::chrono::steady_clock::now().time_since_epoch().count());
const Mint p(rng());
int n, m;
std::cin >> n >> m;
std::vector<Mint> ppow(n + 1), invp(n + 1);
ppow[0] = Mint::ONE;
invp[0] = Mint::ONE;
for (int i = 1; i <= n; ++i) {
ppow[i] = ppow[i - 1] * p;
if (i == 1) {
invp[i] = p.inv();
} else {
invp[i] = invp[i - 1] * invp[1];
}
}
Map<int64_t, Mint2> freq;
std::vector<LL> ll(n);
for (int i = 0; i < n; ++i) {
std::cin >> ll[i].v;
ll[i].v += Mint('0');
++freq[ll[i].v.value()];
}
while ((m--) != 0) {
int op;
std::cin >> op;
if (op == 1) {
int i, j;
std::cin >> i >> j;
--i;
--j;
assert(ll[i].r == -1);
assert(ll[j].l == -1);
ll[i].r = j;
ll[j].l = i;
for (int k = 2; k <= MX; ++k) {
int l = i, r = j;
Mint hsh = ll[l].v + ppow[1] * ll[r].v;
for (int t = 2; t < k; ++t) {
if (ll[r].r == -1) {
hsh *= ppow[1];
l = ll[l].l;
if (l == -1) {
break;
}
hsh += ll[l].v;
} else {
r = ll[r].r;
hsh += ppow[t] * ll[r].v;
}
}
if (l == -1) {
continue;
}
while (r != i) {
++freq[hsh.value()];
hsh -= ppow[k - 1] * ll[r].v;
l = ll[l].l;
r = ll[r].l;
if (l == -1) {
break;
}
hsh *= ppow[1];
hsh += ll[l].v;
}
}
} else if (op == 2) {
int i;
std::cin >> i;
--i;
assert(ll[i].r != -1);
assert(ll[ll[i].r].l != -1);
for (int k = 2; k <= MX; ++k) {
int l = i, r = i;
Mint hsh = ll[l].v;
for (int t = 1; t < k; ++t) {
if (ll[r].r == -1) {
hsh *= ppow[1];
l = ll[l].l;
if (l == -1) {
break;
}
hsh += ll[l].v;
} else {
r = ll[r].r;
hsh += ppow[t] * ll[r].v;
}
}
if (l == -1) {
continue;
}
while (r != i) {
--freq[hsh.value()];
hsh -= ppow[k - 1] * ll[r].v;
l = ll[l].l;
r = ll[r].l;
if (l == -1) {
break;
}
hsh *= ppow[1];
hsh += ll[l].v;
}
}
ll[ll[i].r].l = -1;
ll[i].r = -1;
} else {
std::string s;
int k;
std::cin >> s >> k;
if (k > n) {
std::cout << "0\n";
continue;
}
Mint2 ans(1);
Mint hsh(0);
for (int i = 0; i < k; ++i) {
hsh += Mint(s[i]) * ppow[i];
}
ans *= freq[hsh.value()];
for (int i = 1; i < std::ssize(s) - k + 1; ++i) {
hsh -= Mint(s[i - 1]);
hsh *= invp[1];
hsh += Mint(s[i + k - 1]) * ppow[k - 1];
ans *= freq[hsh.value()];
}
std::cout << ans << '\n';
}
}
}