QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #612045 | #9425. Generated String | ucup-team4435 | WA | 0ms | 3800kb | C++20 | 67.5kb | 2024-10-05 03:02:54 | 2024-10-05 03:02:56 |
Judging History
answer
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
#define rep1n(i, n) for (int i = 1; i <= (n); ++i)
#define repr(i, n) for (int i = (n) - 1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define each(x, a) for (auto &x : a)
#define ar array
#define vec vector
#define range(i, n) rep(i, n)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using str = string;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pair<int, int>>;
using vvi = vector<vi>;
int Bit(int mask, int b) { return (mask >> b) & 1; }
template<class T>
bool ckmin(T &a, const T &b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<class T>
bool ckmax(T &a, const T &b) {
if (b > a) {
a = b;
return true;
}
return false;
}
#include <algorithm>
#include <bit>
#include <cassert>
#include <cstdint>
#include <cstring>
#include <functional>
#include <numeric>
#include <type_traits>
#include <vector>
#ifndef __OY_LINUXIO__
#define __OY_LINUXIO__
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <string>
#include <vector>
#ifdef __unix__
#include <sys/mman.h>
#include <sys/stat.h>
#endif
#if __cpp_constexpr >= 201907L
#define CONSTEXPR20 constexpr
#define INLINE20 constexpr
#else
#define CONSTEXPR20
#define INLINE20 inline
#endif
#define cin OY::LinuxIO::InputHelper<>::get_instance()
#define cout OY::LinuxIO::OutputHelper::get_instance()
#define endl '\n'
#ifndef INPUT_FILE
#define INPUT_FILE "in.txt"
#endif
#ifndef OUTPUT_FILE
#define OUTPUT_FILE "out.txt"
#endif
namespace OY {
namespace LinuxIO {
static constexpr size_t INPUT_BUFFER_SIZE = 1 << 26, OUTPUT_BUFFER_SIZE = 1 << 20;
#ifdef OY_LOCAL
static constexpr char input_file[] = INPUT_FILE, output_file[] = OUTPUT_FILE;
#else
static constexpr char input_file[] = "", output_file[] = "";
#endif
template <typename U, size_t E>
struct TenPow {
static constexpr U value = TenPow<U, E - 1>::value * 10;
};
template <typename U>
struct TenPow<U, 0> {
static constexpr U value = 1;
};
struct InputPre {
uint32_t m_data[0x10000];
CONSTEXPR20 InputPre() {
std::fill(m_data, m_data + 0x10000, -1);
for (size_t i = 0, val = 0; i != 10; i++)
for (size_t j = 0; j != 10; j++) m_data[0x3030 + i + (j << 8)] = val++;
}
};
struct OutputPre {
uint32_t m_data[10000];
CONSTEXPR20 OutputPre() {
uint32_t *c = m_data;
for (size_t i = 0; i != 10; i++)
for (size_t j = 0; j != 10; j++)
for (size_t k = 0; k != 10; k++)
for (size_t l = 0; l != 10; l++) *c++ = i + (j << 8) + (k << 16) + (l << 24) + 0x30303030;
}
};
template <size_t MMAP_SIZE = 1 << 30>
struct InputHelper {
static INLINE20 InputPre pre{};
struct stat m_stat;
char *m_p, *m_c, *m_end;
InputHelper(FILE *file = stdin) {
#ifdef __unix__
auto fd = fileno(file);
fstat(fd, &m_stat);
m_c = m_p = (char *)mmap(nullptr, m_stat.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
m_end = m_p + m_stat.st_size;
#else
uint32_t size = fread(m_c = m_p = new char[INPUT_BUFFER_SIZE], 1, INPUT_BUFFER_SIZE, file);
m_end = m_p + size;
#endif
}
static InputHelper<MMAP_SIZE> &get_instance() {
static InputHelper<MMAP_SIZE> s_obj(*input_file ? fopen(input_file, "rt") : stdin);
return s_obj;
}
template <typename Tp, typename std::enable_if<std::is_unsigned<Tp>::value & std::is_integral<Tp>::value>::type * = nullptr>
InputHelper &operator>>(Tp &x) {
x = 0;
while (!isdigit(*m_c)) m_c++;
x = *m_c++ ^ '0';
while (~pre.m_data[*reinterpret_cast<uint16_t *&>(m_c)]) x = x * 100 + pre.m_data[*reinterpret_cast<uint16_t *&>(m_c)++];
if (isdigit(*m_c)) x = x * 10 + (*m_c++ ^ '0');
return *this;
}
template <typename Tp, typename std::enable_if<std::is_signed<Tp>::value & std::is_integral<Tp>::value>::type * = nullptr>
InputHelper &operator>>(Tp &x) {
typename std::make_unsigned<Tp>::type t{};
bool sign{};
while (!isdigit(*m_c)) sign = (*m_c++ == '-');
t = *m_c++ ^ '0';
while (~pre.m_data[*reinterpret_cast<uint16_t *&>(m_c)]) t = t * 100 + pre.m_data[*reinterpret_cast<uint16_t *&>(m_c)++];
if (isdigit(*m_c)) t = t * 10 + (*m_c++ ^ '0');
x = sign ? -t : t;
return *this;
}
InputHelper &operator>>(char &x) {
while (*m_c <= ' ') m_c++;
x = *m_c++;
return *this;
}
InputHelper &operator>>(std::string &x) {
while (*m_c <= ' ') m_c++;
char *c = m_c;
while (*c > ' ') c++;
x.assign(m_c, c - m_c), m_c = c;
return *this;
}
InputHelper &operator>>(std::string_view &x) {
while (*m_c <= ' ') m_c++;
char *c = m_c;
while (*c > ' ') c++;
x = std::string_view(m_c, c - m_c), m_c = c;
return *this;
}
};
struct OutputHelper {
static INLINE20 OutputPre pre{};
FILE *m_file;
char m_p[OUTPUT_BUFFER_SIZE], *m_c, *m_end;
OutputHelper(FILE *file = stdout) {
m_file = file;
m_c = m_p, m_end = m_p + OUTPUT_BUFFER_SIZE;
}
~OutputHelper() { flush(); }
static OutputHelper &get_instance() {
static OutputHelper s_obj(*output_file ? fopen(output_file, "wt") : stdout);
return s_obj;
}
void flush() { fwrite(m_p, 1, m_c - m_p, m_file), m_c = m_p; }
OutputHelper &operator<<(char x) {
if (m_end - m_c < 20) flush();
*m_c++ = x;
return *this;
}
OutputHelper &operator<<(std::string_view s) {
if (m_end - m_c < s.size()) flush();
memcpy(m_c, s.data(), s.size()), m_c += s.size();
return *this;
}
OutputHelper &operator<<(uint64_t x) {
if (m_end - m_c < 20) flush();
#define CASEW(w) \
case TenPow<uint64_t, w - 1>::value... TenPow<uint64_t, w>::value - 1: \
*(uint32_t *)m_c = pre.m_data[x / TenPow<uint64_t, w - 4>::value]; \
m_c += 4, x %= TenPow<uint64_t, w - 4>::value;
switch (x) {
CASEW(19);
CASEW(15);
CASEW(11);
CASEW(7);
case 100 ... 999:
*(uint32_t *)m_c = pre.m_data[x * 10];
m_c += 3;
break;
CASEW(18);
CASEW(14);
CASEW(10);
CASEW(6);
case 10 ... 99:
*(uint32_t *)m_c = pre.m_data[x * 100];
m_c += 2;
break;
CASEW(17);
CASEW(13);
CASEW(9);
CASEW(5);
case 0 ... 9:
*m_c++ = '0' + x;
break;
default:
*(uint32_t *)m_c = pre.m_data[x / TenPow<uint64_t, 16>::value];
m_c += 4;
x %= TenPow<uint64_t, 16>::value;
CASEW(16);
CASEW(12);
CASEW(8);
case 1000 ... 9999:
*(uint32_t *)m_c = pre.m_data[x];
m_c += 4;
break;
}
#undef CASEW
return *this;
}
OutputHelper &operator<<(uint32_t x) {
if (m_end - m_c < 20) flush();
#define CASEW(w) \
case TenPow<uint32_t, w - 1>::value... TenPow<uint32_t, w>::value - 1: \
*(uint32_t *)m_c = pre.m_data[x / TenPow<uint32_t, w - 4>::value]; \
m_c += 4, x %= TenPow<uint32_t, w - 4>::value;
switch (x) {
default:
*(uint32_t *)m_c = pre.m_data[x / TenPow<uint32_t, 6>::value];
m_c += 4;
x %= TenPow<uint32_t, 6>::value;
CASEW(6);
case 10 ... 99:
*(uint32_t *)m_c = pre.m_data[x * 100];
m_c += 2;
break;
CASEW(9);
CASEW(5);
case 0 ... 9:
*m_c++ = '0' + x;
break;
CASEW(8);
case 1000 ... 9999:
*(uint32_t *)m_c = pre.m_data[x];
m_c += 4;
break;
CASEW(7);
case 100 ... 999:
*(uint32_t *)m_c = pre.m_data[x * 10];
m_c += 3;
break;
}
#undef CASEW
return *this;
}
OutputHelper &operator<<(int64_t x) {
if (x >= 0)
return (*this) << uint64_t(x);
else
return (*this) << '-' << uint64_t(-x);
}
OutputHelper &operator<<(int32_t x) {
if (x >= 0)
return (*this) << uint32_t(x);
else
return (*this) << '-' << uint32_t(-x);
}
};
}
}
#endif
namespace SPARSE {
#ifndef __OY_CATTREE__
#define __OY_CATTREE__
namespace OY {
namespace CAT {
using size_type = uint32_t;
template <typename Tp, typename Operation>
struct BaseMonoid {
using value_type = Tp;
static value_type op(const value_type &x, const value_type &y) { return Operation()(x, y); }
};
template <typename Tp, typename Compare>
struct ChoiceByCompare {
Tp operator()(const Tp &x, const Tp &y) const { return Compare()(x, y) ? y : x; }
};
template <typename Tp, Tp (*Fp)(Tp, Tp)>
struct FpTransfer {
Tp operator()(const Tp &x, const Tp &y) const { return Fp(x, y); }
};
template <typename Monoid, size_t MAX_LEVEL = 30>
class Table {
public:
using monoid = Monoid;
using value_type = typename Monoid::value_type;
private:
std::vector<value_type> m_sub[MAX_LEVEL];
size_type m_size, m_depth;
void _update(size_type i) {
auto sub = m_sub[0].data();
for (size_type j = 1, k = 4; j != m_depth; j++, k <<= 1) {
auto cur = m_sub[j].data();
size_type l = i & -(1 << (j + 1));
if (i >> j & 1) {
size_type j = i, end = std::min(l + k, m_size);
cur[j] = (j == l + (k >> 1)) ? sub[j] : Monoid::op(cur[j - 1], sub[j]);
while (++j != end) cur[j] = Monoid::op(cur[j - 1], sub[j]);
} else {
if (m_size <= l + k / 2) continue;
size_type j = i + 1;
cur[j - 1] = (j == l + (k >> 1)) ? sub[j - 1] : Monoid::op(sub[j - 1], cur[j]);
while (--j != l) cur[j - 1] = Monoid::op(sub[j - 1], cur[j]);
}
}
}
public:
Table() = default;
template <typename InitMapping>
Table(size_type length, InitMapping mapping) { resize(length, mapping); }
template <typename Iterator>
Table(Iterator first, Iterator last) { reset(first, last); }
template <typename InitMapping>
void resize(size_type length, InitMapping mapping) {
if (!(m_size = length)) return;
m_depth = m_size == 1 ? 1 : std::bit_width(m_size - 1);
for (size_type i = 0; i != m_depth; i++) m_sub[i].resize(m_size);
auto sub = m_sub[0].data();
for (size_type i = 0; i != m_size; i++) sub[i] = mapping(i);
for (size_type j = 1, k = 4, l; j != m_depth; j++, k <<= 1) {
auto cur = m_sub[j].data();
for (l = 0; l + k <= m_size; l += k) {
size_type i = l + (k >> 1);
cur[i - 1] = sub[i - 1];
while (--i != l) cur[i - 1] = Monoid::op(sub[i - 1], cur[i]);
i = l + (k >> 1);
cur[i] = sub[i];
while (++i != l + k) cur[i] = Monoid::op(cur[i - 1], sub[i]);
}
if (l != m_size && (l + (k >> 1) < m_size)) {
size_type i = l + (k >> 1);
cur[i - 1] = sub[i - 1];
while (--i != l) cur[i - 1] = Monoid::op(sub[i - 1], cur[i]);
i = l + (k >> 1);
cur[i] = sub[i];
while (++i != m_size) cur[i] = Monoid::op(cur[i - 1], sub[i]);
}
}
}
template <typename Iterator>
void reset(Iterator first, Iterator last) {
resize(last - first, [&](size_type i) { return *(first + i); });
}
size_type size() const { return m_size; }
void modify(size_type i, value_type val) { m_sub[0][i] = val, _update(i); }
value_type query(size_type i) const { return m_sub[0][i]; }
value_type query(size_type left, size_type right) const {
if (left == right) return m_sub[0][left];
size_type d = std::bit_width(left ^ right) - 1;
return Monoid::op(m_sub[d][left], m_sub[d][right]);
}
value_type query_all() const { return query(0, m_size - 1); }
template <typename Judger>
size_type max_right(size_type left, Judger &&judge) const {
value_type val = m_sub[0][left];
if (!judge(val)) return left - 1;
if (++left == m_size) return left - 1;
size_type d = std::bit_width(left ^ (m_size - 1));
while (d && left < m_size) {
size_type split = (left & -(1 << (d - 1))) | (1 << (d - 1));
if (m_size <= split)
while (--d && (left >> (d - 1) & 1)) {}
else {
value_type a = Monoid::op(val, m_sub[d - 1][left]);
if (judge(a))
val = a, --d, left = split;
else
while (--d && (left >> (d - 1) & 1)) {}
}
}
if (left < m_size && judge(Monoid::op(val, m_sub[0][left]))) left++;
return std::min(left, m_size) - 1;
}
template <typename Judger>
size_type min_left(size_type right, Judger &&judge) const {
value_type val = m_sub[0][right];
if (!judge(val)) return right + 1;
if (!right--) return right + 1;
size_type d = std::bit_width(right);
while (d) {
value_type a = Monoid::op(m_sub[d - 1][right], val);
if (judge(a))
val = a, --d, right = (right & -(1 << d)) - 1;
else
while (--d && !(right >> (d - 1) & 1)) {}
}
if (!(right & 1) && judge(Monoid::op(m_sub[0][right], val))) right--;
return right + 1;
}
};
template <typename Ostream, typename Monoid, size_t MAX_LEVEL>
Ostream &operator<<(Ostream &out, const Table<Monoid, MAX_LEVEL> &x) {
out << "[";
for (size_type i = 0; i != x.size(); i++) {
if (i) out << ", ";
out << x.query(i);
}
return out << "]";
}
}
template <typename Tp, size_t MAX_LEVEL = 30, typename Operation, typename InitMapping, typename TreeType = CAT::Table<CAT::BaseMonoid<Tp, Operation>, MAX_LEVEL>>
auto make_CatTree(CAT::size_type length, Operation op, InitMapping mapping) -> TreeType { return TreeType(length, mapping); }
template <size_t MAX_LEVEL = 30, typename Iterator, typename Operation, typename Tp = typename std::iterator_traits<Iterator>::value_type, typename TreeType = CAT::Table<CAT::BaseMonoid<Tp, Operation>, MAX_LEVEL>>
auto make_CatTree(Iterator first, Iterator last, Operation op) -> TreeType { return TreeType(first, last); }
template <typename Tp, size_t MAX_LEVEL = 30>
using CatMaxTable = CAT::Table<CAT::BaseMonoid<Tp, CAT::ChoiceByCompare<Tp, std::less<Tp>>>, MAX_LEVEL>;
template <typename Tp, size_t MAX_LEVEL = 30>
using CatMinTable = CAT::Table<CAT::BaseMonoid<Tp, CAT::ChoiceByCompare<Tp, std::greater<Tp>>>, MAX_LEVEL>;
template <typename Tp, size_t MAX_LEVEL = 30>
using CatGcdTable = CAT::Table<CAT::BaseMonoid<Tp, CAT::FpTransfer<Tp, std::gcd<Tp>>>, MAX_LEVEL>;
template <typename Tp, size_t MAX_LEVEL = 30>
using CatLcmTable = CAT::Table<CAT::BaseMonoid<Tp, CAT::FpTransfer<Tp, std::lcm<Tp>>>, MAX_LEVEL>;
template <typename Tp, size_t MAX_LEVEL = 30>
using CatBitAndTable = CAT::Table<CAT::BaseMonoid<Tp, std::bit_and<Tp>>, MAX_LEVEL>;
template <typename Tp, size_t MAX_LEVEL = 30>
using CatBitOrTable = CAT::Table<CAT::BaseMonoid<Tp, std::bit_or<Tp>>, MAX_LEVEL>;
template <typename Tp, size_t MAX_LEVEL = 30>
using CatBitXorTable = CAT::Table<CAT::BaseMonoid<Tp, std::bit_xor<Tp>>, MAX_LEVEL>;
template <typename Tp, size_t MAX_LEVEL = 30>
using CatSumTable = CAT::Table<CAT::BaseMonoid<Tp, std::plus<Tp>>, MAX_LEVEL>;
}
#endif
#ifndef __OY_SQRTTREE__
#define __OY_SQRTTREE__
namespace OY {
namespace SQRT {
using size_type = uint32_t;
using CAT::BaseMonoid;
using CAT::ChoiceByCompare;
using CAT::FpTransfer;
template <size_type BlockSize = 16>
struct StaticController {
void reserve(size_type capacity) {}
static constexpr bool is_first(size_type i) { return i % BlockSize == 0; }
static constexpr size_type block_id(size_type i) { return i / BlockSize; }
static constexpr size_type block_first(size_type i) { return i / BlockSize * BlockSize; }
static constexpr size_type block_size() { return BlockSize; }
static constexpr size_type block_count(size_type length) { return (length + BlockSize - 1) / BlockSize; }
};
template <size_type DefaultDepth = 5>
struct RandomController {
size_type m_mask = (1 << DefaultDepth) - 1, m_depth = DefaultDepth;
void reserve(size_type capacity) { m_depth = (std::bit_width(capacity) - 1) / 2, m_mask = (1 << m_depth) - 1; }
bool is_first(size_type i) const { return !(i & m_mask); }
size_type block_id(size_type i) const { return i >> m_depth; }
size_type block_first(size_type i) const { return i & ~m_mask; }
size_type block_size() const { return m_mask + 1; }
size_type block_count(size_type length) const { return (length + m_mask) >> m_depth; }
};
template <size_type DefaultDepth = 5>
struct NonRandomController {
size_type m_mask = (1 << DefaultDepth) - 1, m_depth = DefaultDepth;
void reserve(size_type capacity) { m_depth = capacity >= 32 ? std::bit_width<size_type>(std::bit_width(capacity / std::bit_width(capacity)) - 1) : (std::bit_width(capacity) - 1) / 2, m_mask = (size_type(1) << m_depth) - 1; }
bool is_first(size_type i) const { return !(i & m_mask); }
size_type block_id(size_type i) const { return i >> m_depth; }
size_type block_first(size_type i) const { return i & ~m_mask; }
size_type block_size() const { return m_mask + 1; }
size_type block_count(size_type length) const { return (length + m_mask) >> m_depth; }
};
template <typename Monoid, typename Controller = RandomController<>, size_t MAX_LEVEL = 30>
class Table {
public:
using monoid = Monoid;
using value_type = typename Monoid::value_type;
using inner_table = CAT::Table<Monoid, MAX_LEVEL>;
private:
inner_table m_table;
std::vector<value_type> m_data, m_prefix, m_suffix;
size_type m_size;
Controller m_ctrl;
template <typename Judger>
size_type _max_right(size_type left, size_type end, Judger &&judge) const {
value_type val = m_data[left];
if (judge(val))
while (++left != end) {
value_type a = Monoid::op(val, m_data[left]);
if (!judge(a)) break;
val = a;
}
return left - 1;
}
template <typename Judger>
size_type _max_right2(size_type left, size_type end, Judger &&judge) const {
size_type low = left, high = end;
while (low != high) {
size_type mid = (low + high) / 2;
if (judge(m_prefix[mid]))
low = mid + 1;
else
high = mid;
}
return low - 1;
}
template <typename Judger>
size_type _min_left(size_type end, size_type right, Judger &&judge) const {
value_type val = m_data[right];
if (judge(val))
while (--right != end) {
value_type a = Monoid::op(m_data[right], val);
if (!judge(a)) break;
val = a;
}
return right + 1;
}
template <typename Judger>
size_type _min_left2(size_type end, size_type right, Judger &&judge) const {
size_type low = end, high = right;
while (low != high) {
size_type mid = (low + high + 1) / 2;
if (judge(m_suffix[mid]))
high = mid - 1;
else
low = mid;
}
return low + 1;
}
void _update(size_type i) {
size_type cur = m_ctrl.block_first(i), nxt = std::min(cur + m_ctrl.block_size(), m_size);
m_prefix[i] = (i == cur) ? m_data[i] : Monoid::op(m_prefix[i - 1], m_data[i]);
for (size_type j = i + 1; j != nxt; j++) m_prefix[j] = Monoid::op(m_prefix[j - 1], m_data[j]);
m_suffix[i] = (i == nxt - 1) ? m_data[i] : Monoid::op(m_data[i], m_suffix[i + 1]);
for (size_type j = i - 1; j != cur - 1; j--) m_suffix[j] = Monoid::op(m_data[j], m_suffix[j + 1]);
m_table.modify(m_ctrl.block_id(i), m_suffix[cur]);
}
public:
Table() = default;
template <typename InitMapping>
Table(size_type length, InitMapping mapping) { resize(length, mapping); }
template <typename Iterator>
Table(Iterator first, Iterator last) { reset(first, last); }
size_type size() const { return m_size; }
template <typename InitMapping>
void resize(size_type length, InitMapping mapping) {
if (!(m_size = length)) return;
m_ctrl.reserve(m_size);
m_data.resize(m_size);
for (size_type i = 0; i != m_size; i++) m_data[i] = mapping(i);
m_prefix = m_suffix = m_data;
for (size_type i = 1; i != m_size; i++)
if (!m_ctrl.is_first(i)) m_prefix[i] = Monoid::op(m_prefix[i - 1], m_prefix[i]);
for (size_type i = m_size - 1; i; i--)
if (!m_ctrl.is_first(i)) m_suffix[i - 1] = Monoid::op(m_suffix[i - 1], m_suffix[i]);
m_table.resize(m_ctrl.block_count(m_size), [&](size_type i) { return m_suffix[i * m_ctrl.block_size()]; });
}
template <typename Iterator>
void reset(Iterator first, Iterator last) {
resize(last - first, [&](size_type i) { return *(first + i); });
}
void modify(size_type i, value_type val) { m_data[i] = val, _update(i); }
value_type query(size_type i) const { return m_data[i]; }
value_type query(size_type left, size_type right) const {
size_type l = m_ctrl.block_id(left), r = m_ctrl.block_id(right);
if (l == r) {
value_type res = m_data[left];
#ifndef __clang__
#pragma GCC unroll 64
#endif
for (size_type i = left + 1; i <= right; i++) res = Monoid::op(res, m_data[i]);
return res;
} else if (l + 1 == r)
return Monoid::op(m_suffix[left], m_prefix[right]);
else
return Monoid::op(Monoid::op(m_suffix[left], m_table.query(l + 1, r - 1)), m_prefix[right]);
}
value_type query_all() const { return m_table.query_all(); }
template <typename Judger>
size_type max_right(size_type left, Judger &&judge) const {
value_type val = m_suffix[left];
if (!judge(val)) return _max_right(left, std::min(m_size, m_ctrl.block_first(left) + m_ctrl.block_size()), judge);
size_type l = m_ctrl.block_id(left);
if (l + 1 == m_table.size()) return m_size - 1;
size_type r = m_table.max_right(l + 1, [&](const value_type &x) { return judge(Monoid::op(val, x)); });
if (r + 1 == m_table.size()) return m_size - 1;
if (r > l) val = Monoid::op(val, m_table.query(l + 1, r));
return _max_right2((r + 1) * m_ctrl.block_size(), std::min(m_size, (r + 2) * m_ctrl.block_size()), [&](const value_type &x) { return judge(Monoid::op(val, x)); });
}
template <typename Judger>
size_type min_left(size_type right, Judger &&judge) const {
value_type val = m_prefix[right];
if (!judge(val)) return _min_left(m_ctrl.block_first(right) - 1, right, judge);
size_type r = m_ctrl.block_id(right);
if (!r) return 0;
size_type l = m_table.min_left(r - 1, [&](const value_type &x) { return judge(Monoid::op(x, val)); });
if (!l) return 0;
if (l < r) val = Monoid::op(m_table.query(l, r - 1), val);
return _min_left2(((l - 1) * m_ctrl.block_size()) - 1, (l * m_ctrl.block_size()) - 1, [&](const value_type &x) { return judge(Monoid::op(x, val)); });
}
};
template <typename Ostream, typename Node, typename Controller, size_t MAX_LEVEL>
Ostream &operator<<(Ostream &out, const Table<Node, Controller, MAX_LEVEL> &x) {
out << "[";
for (size_type i = 0; i != x.size(); i++) {
if (i) out << ", ";
out << x.query(i);
}
return out << "]";
}
}
template <typename Tp, typename Controller = SQRT::RandomController<>, size_t MAX_LEVEL = 30, typename Operation, typename InitMapping, typename TreeType = SQRT::Table<SQRT::BaseMonoid<Tp, Operation>, Controller, MAX_LEVEL>>
auto make_SqrtTree(SQRT::size_type length, Operation op, InitMapping mapping) -> TreeType { return TreeType(length, mapping); }
template <typename Controller = SQRT::RandomController<>, size_t MAX_LEVEL = 30, typename Iterator, typename Operation, typename Tp = typename std::iterator_traits<Iterator>::value_type, typename TreeType = SQRT::Table<SQRT::BaseMonoid<Tp, Operation>, Controller, MAX_LEVEL>>
auto make_SqrtTree(Iterator first, Iterator last, Operation op) -> TreeType { return TreeType(first, last); }
template <typename Tp,typename Controller = SQRT::RandomController<>, size_t MAX_LEVEL = 30>
using SqrtMaxTable = SQRT::Table<SQRT::BaseMonoid<Tp, SQRT::ChoiceByCompare<Tp, std::less<Tp>>>, Controller, MAX_LEVEL>;
template <typename Tp,typename Controller = SQRT::RandomController<>, size_t MAX_LEVEL = 30>
using SqrtMinTable = SQRT::Table<SQRT::BaseMonoid<Tp, SQRT::ChoiceByCompare<Tp, std::greater<Tp>>>, Controller, MAX_LEVEL>;
template <typename Tp,typename Controller = SQRT::RandomController<>, size_t MAX_LEVEL = 30>
using SqrtGcdTable = SQRT::Table<SQRT::BaseMonoid<Tp, SQRT::FpTransfer<Tp, std::gcd<Tp>>>, Controller, MAX_LEVEL>;
template <typename Tp,typename Controller = SQRT::RandomController<>, size_t MAX_LEVEL = 30>
using SqrtLcmTable = SQRT::Table<SQRT::BaseMonoid<Tp, SQRT::FpTransfer<Tp, std::lcm<Tp>>>, Controller, MAX_LEVEL>;
template <typename Tp, typename Controller = SQRT::RandomController<>, size_t MAX_LEVEL = 30>
using SqrtBitAndTable = SQRT::Table<SQRT::BaseMonoid<Tp, std::bit_and<Tp>>, Controller, MAX_LEVEL>;
template <typename Tp,typename Controller = SQRT::RandomController<>, size_t MAX_LEVEL = 30>
using SqrtBitOrTable = SQRT::Table<SQRT::BaseMonoid<Tp, std::bit_or<Tp>>, Controller, MAX_LEVEL>;
template <typename Tp, typename Controller = SQRT::RandomController<>, size_t MAX_LEVEL = 30>
using SqrtBitXorTable = SQRT::Table<SQRT::BaseMonoid<Tp, std::bit_xor<Tp>>, Controller, MAX_LEVEL>;
template <typename Tp,typename Controller = SQRT::RandomController<>, size_t MAX_LEVEL = 30>
using SqrtSumTable = SQRT::Table<SQRT::BaseMonoid<Tp, std::plus<Tp>>, Controller, MAX_LEVEL>;
}
#endif
}
namespace SOLVE_2D {
#ifndef __OY_WAVELET__
#define __OY_WAVELET__
namespace OY {
namespace WaveLet {
using size_type = uint32_t;
using mask_type = uint64_t;
struct Ignore {};
static constexpr size_type MASK_SIZE = sizeof(mask_type) << 3, MASK_WIDTH = MASK_SIZE / 32 + 4;
struct BitRank {
std::vector<mask_type> m_bits;
std::vector<size_type> m_sum;
void resize(size_type length) { m_bits.assign((length >> MASK_WIDTH) + 1, 0), m_sum.resize(m_bits.size()); }
void set(size_type i, mask_type val) { m_bits[i >> MASK_WIDTH] |= val << (i & (MASK_SIZE - 1)); }
void prepare() {
for (size_type i = 1; i != m_bits.size(); i++) m_sum[i] = m_sum[i - 1] + std::popcount(m_bits[i - 1]);
}
size_type rank1(size_type i) const { return m_sum[i >> MASK_WIDTH] + std::popcount(m_bits[i >> MASK_WIDTH] & ((mask_type(1) << (i & (MASK_SIZE - 1))) - 1)); }
size_type rank1(size_type l, size_type r) const { return rank1(r) - rank1(l); }
size_type rank0(size_type i) const { return i - rank1(i); }
size_type rank0(size_type l, size_type r) const { return rank0(r) - rank0(l); }
};
struct VoidTable {
template <typename Iterator>
void reset(Iterator first, Iterator last) {}
template <typename InitMapping>
void resize(size_type length, InitMapping) {}
size_type query(size_type left, size_type right) const { return right - left + 1; }
};
template <typename Tp, typename SumTable = VoidTable>
struct Table {
size_type m_size, m_alpha;
std::vector<BitRank> m_ranks;
std::vector<size_type> m_pos;
std::vector<SumTable> m_sumer;
Table() = default;
template <typename InitMapping, typename TableMapping = Ignore>
Table(size_type length, InitMapping mapping, size_type alpha = 0, TableMapping table_mapping = TableMapping()) { resize(length, mapping, alpha, table_mapping); }
template <typename Iterator, typename TableMapping = Ignore>
Table(Iterator first, Iterator last, size_type alpha = 0, TableMapping table_mapping = TableMapping()) { reset(first, last, alpha, table_mapping); }
template <typename InitMapping, typename TableMapping = Ignore>
void resize(size_type length, InitMapping mapping, size_type alpha = 0, TableMapping table_mapping = TableMapping()) {
static_assert(std::is_unsigned<Tp>::value, "Tp Must Be Unsigned Type");
if (!(m_size = length)) return;
std::vector<Tp> numbers(m_size);
for (size_type i = 0; i != m_size; i++) numbers[i] = mapping(i);
m_alpha = alpha ? alpha : std::max<uint32_t>(1, std::bit_width(*std::max_element(numbers.begin(), numbers.end())));
m_ranks.resize(m_alpha), m_pos.resize(m_alpha);
m_sumer.resize(m_alpha);
for (size_type d = m_alpha - 1; ~d; d--) {
m_ranks[d].resize(m_size);
for (size_type i = 0; i != m_size; i++) m_ranks[d].set(i, numbers[i] >> d & 1);
m_ranks[d].prepare();
m_pos[d] = std::stable_partition(numbers.begin(), numbers.end(), [&](size_type val) { return !(val >> d & 1); }) - numbers.begin();
if constexpr (std::is_same<TableMapping, Ignore>::value)
m_sumer[d].reset(numbers.begin(), numbers.end());
else
m_sumer[d].resize(m_size, [&](size_type i) { return table_mapping(numbers[i]); });
}
}
template <typename Iterator, typename TableMapping = Ignore>
void reset(Iterator first, Iterator last, size_type alpha = 0, TableMapping table_mapping = TableMapping()) {
resize(
last - first, [&](size_type i) { return *(first + i); }, alpha, table_mapping);
}
size_type count(size_type left, size_type right, Tp val) const {
right++;
for (size_type d = m_alpha - 1; ~d; d--) {
size_type zl = m_ranks[d].rank0(left), zr = m_ranks[d].rank0(right);
if (!(val >> d & 1))
left = zl, right = zr;
else
left += m_pos[d] - zl, right += m_pos[d] - zr;
}
return right - left;
}
size_type count(size_type left, size_type right, Tp minimum, Tp maximum) const {
size_type l1 = left, r1 = right + 1, l2 = left, r2 = right + 1, res = 0;
for (size_type d = m_alpha - 1; ~d; d--) {
size_type zl1 = m_ranks[d].rank0(l1), zr1 = m_ranks[d].rank0(r1), zl2 = m_ranks[d].rank0(l2), zr2 = m_ranks[d].rank0(r2);
if (!(minimum >> d & 1))
l1 = zl1, r1 = zr1;
else
res -= zr1 - zl1, l1 += m_pos[d] - zl1, r1 += m_pos[d] - zr1;
if (!(maximum >> d & 1))
l2 = zl2, r2 = zr2;
else
res += zr2 - zl2, l2 += m_pos[d] - zl2, r2 += m_pos[d] - zr2;
}
return r2 - l2 + res;
}
size_type rank(size_type left, size_type right, Tp val) const {
size_type ans = 0;
right++;
for (size_type d = m_alpha - 1; ~d; d--) {
size_type zl = m_ranks[d].rank0(left), zr = m_ranks[d].rank0(right);
if (!(val >> d & 1))
left = zl, right = zr;
else
left += m_pos[d] - zl, right += m_pos[d] - zr, ans += zr - zl;
}
return ans;
}
Tp minimum(size_type left, size_type right) const {
Tp ans = 0;
right++;
for (size_type d = m_alpha - 1; ~d; d--) {
size_type zl = m_ranks[d].rank0(left), zr = m_ranks[d].rank0(right);
if (zl != zr)
left = zl, right = zr;
else
left += m_pos[d] - zl, right += m_pos[d] - zr, ans |= Tp(1) << d;
}
return ans;
}
Tp maximum(size_type left, size_type right) const {
Tp ans = 0;
right++;
for (size_type d = m_alpha - 1; ~d; d--) {
size_type zl = m_ranks[d].rank0(left), zr = m_ranks[d].rank0(right);
if (zr - zl == right - left)
left = zl, right = zr;
else
left += m_pos[d] - zl, right += m_pos[d] - zr, ans |= Tp(1) << d;
}
return ans;
}
Tp quantile(size_type left, size_type right, size_type k) const {
Tp ans = 0;
right++;
for (size_type d = m_alpha - 1; ~d; d--) {
size_type zl = m_ranks[d].rank0(left), zr = m_ranks[d].rank0(right), z = zr - zl;
if (k < z)
left = zl, right = zr;
else
left += m_pos[d] - zl, right += m_pos[d] - zr, k -= z, ans |= Tp(1) << d;
}
return ans;
}
Tp max_bitxor(size_type left, size_type right, Tp val) const {
Tp ans = 0;
right++;
for (size_type d = m_alpha - 1; ~d; d--) {
size_type zl = m_ranks[d].rank0(left), zr = m_ranks[d].rank0(right), z = zr - zl;
if (val >> d & 1)
if (z)
left = zl, right = zr, ans |= Tp(1) << d;
else
left += m_pos[d] - zl, right += m_pos[d] - zr;
else if (right - left - z)
left += m_pos[d] - zl, right += m_pos[d] - zr, ans |= Tp(1) << d;
else
left = zl, right = zr;
}
return ans;
}
template <typename Callback>
void do_for_rank_range(size_type left, size_type right, size_type rk1, size_type rk2, Callback &&call) const {
right++;
auto handle = [&](size_type l1, size_type r1, size_type l2, size_type r2, size_type k1, size_type k2, size_type d) {
for (; ~d; d--) {
size_type one_l = m_ranks[d].rank1(l1), one_r = m_ranks[d].rank1(r1), one = one_r - one_l, zl = m_ranks[d].rank0(l2), zr = m_ranks[d].rank0(r2), z = zr - zl;
if (k1 < one)
l1 = m_pos[d] + one_l, r1 = m_pos[d] + one_r;
else {
l1 -= one_l, r1 -= one_r, k1 -= one;
if (one) call(m_sumer[d].query(m_pos[d] + one_l, m_pos[d] + one_r - 1));
}
if (k2 < z)
l2 = zl, r2 = zr;
else {
l2 += m_pos[d] - zl, r2 += m_pos[d] - zr, k2 -= z;
if (z) call(m_sumer[d].query(zl, zr - 1));
}
}
if (k1) call(m_sumer[0].query(l1, l1 + k1 - 1));
if (k2) call(m_sumer[0].query(r2 - k2, r2 - 1));
};
for (size_type d = m_alpha - 1; ~d; d--) {
size_type zl = m_ranks[d].rank0(left), zr = m_ranks[d].rank0(right), z = zr - zl;
if (rk2 < z)
left = zl, right = zr;
else if (rk1 >= z)
left += m_pos[d] - zl, right += m_pos[d] - zr, rk1 -= z, rk2 -= z;
else
return handle(zl, zr, left + m_pos[d] - zl, right + m_pos[d] - zr, z - rk1, rk2 - z + 1, d - 1);
}
if (left != right) call(m_sumer[0].query(left + rk1, left + rk2));
}
template <typename Callback>
void do_for_value_range(size_type left, size_type right, Tp floor, Tp ceil, Callback &&call) const {
right++;
auto handle = [&](size_type l1, size_type r1, size_type l2, size_type r2, size_type d) {
for (; ~d; d--) {
size_type one_l = m_ranks[d].rank1(l1), one_r = m_ranks[d].rank1(r1), one = one_r - one_l, zl = m_ranks[d].rank0(l2), zr = m_ranks[d].rank0(r2), z = zr - zl;
if (floor >> d & 1)
l1 = m_pos[d] + one_l, r1 = m_pos[d] + one_r;
else {
l1 -= one_l, r1 -= one_r;
if (one) call(m_sumer[d].query(m_pos[d] + one_l, m_pos[d] + one_r - 1));
}
if (!(ceil >> d & 1))
l2 = zl, r2 = zr;
else {
l2 += m_pos[d] - zl, r2 += m_pos[d] - zr;
if (z) call(m_sumer[d].query(zl, zr - 1));
}
}
if (l1 != r1) call(m_sumer[0].query(l1, r1 - 1));
if (l2 != r2) call(m_sumer[0].query(l2, r2 - 1));
};
for (size_type d = m_alpha - 1; ~d; d--) {
size_type zl = m_ranks[d].rank0(left), zr = m_ranks[d].rank0(right), z = zr - zl;
if ((floor >> d & 1) == (ceil >> d & 1))
if (!(floor >> d & 1))
left = zl, right = zr;
else
left += m_pos[d] - zl, right += m_pos[d] - zr;
else
return handle(zl, zr, left + m_pos[d] - zl, right + m_pos[d] - zr, d - 1);
}
if (left != right) call(m_sumer[0].query(left, right - 1));
}
template <typename Callback>
void do_in_table(size_type pos, Callback &&call) {
for (size_type d = m_alpha - 1; ~d; d--) {
size_type zl = m_ranks[d].rank0(pos), zr = m_ranks[d].rank0(pos + 1);
call(m_sumer[d], pos = zl == zr ? pos + m_pos[d] - zl : zl);
}
}
};
template <typename Tp, typename SumTable = VoidTable>
struct Tree {
Table<size_type, SumTable> m_table;
std::vector<Tp> m_discretizer;
size_type m_size;
size_type _find(const Tp &val) const { return std::lower_bound(m_discretizer.begin(), m_discretizer.end(), val) - m_discretizer.begin(); }
size_type _upper_find(const Tp &val) const { return std::upper_bound(m_discretizer.begin(), m_discretizer.end(), val) - m_discretizer.begin(); }
Tree() = default;
template <typename InitMapping, typename TableMapping = Ignore>
Tree(size_type length, InitMapping mapping, TableMapping table_mapping = TableMapping()) { resize(length, mapping, table_mapping); }
template <typename Iterator, typename TableMapping = Ignore>
Tree(Iterator first, Iterator last, TableMapping table_mapping = TableMapping()) { reset(first, last, table_mapping); }
template <typename InitMapping, typename TableMapping = Ignore>
void resize(size_type length, InitMapping mapping, TableMapping table_mapping = TableMapping()) {
if (!(m_size = length)) return;
std::vector<Tp> items(m_size);
for (size_type i = 0; i != m_size; i++) items[i] = mapping(i);
m_discretizer = items;
std::sort(m_discretizer.begin(), m_discretizer.end());
m_discretizer.erase(std::unique(m_discretizer.begin(), m_discretizer.end()), m_discretizer.end());
if constexpr (std::is_same<TableMapping, Ignore>::value)
m_table.resize(
m_size, [&](size_type i) { return _find(items[i]); }, std::bit_width(m_discretizer.size()), [&](size_type val) { return m_discretizer[val]; });
else
m_table.resize(
m_size, [&](size_type i) { return _find(items[i]); }, std::bit_width(m_discretizer.size()), [&](size_type val) { return table_mapping(m_discretizer[val]); });
}
template <typename Iterator, typename TableMapping>
void reset(Iterator first, Iterator last, TableMapping table_mapping = TableMapping()) {
resize(
last - first, [&](size_type i) { return *(first + i); }, table_mapping);
}
size_type count(size_type left, size_type right, const Tp &val) const {
size_type find = _find(val);
return find < m_discretizer.size() && m_discretizer[find] == val ? m_table.count(left, right, find) : 0;
}
size_type count(size_type left, size_type right, const Tp &minimum, const Tp &maximum) const {
size_type find1 = _find(minimum);
if (find1 == m_discretizer.size()) return 0;
size_type find2 = _find(maximum);
return find2 < m_discretizer.size() && m_discretizer[find2] == maximum ? m_table.count(left, right, find1, find2) : m_table.count(left, right, find1, find2 - 1);
}
size_type rank(size_type left, size_type right, const Tp &val) const { return m_table.rank(left, right, _find(val)); }
Tp minimum(size_type left, size_type right) const { return m_discretizer[m_table.minimum(left, right)]; }
Tp maximum(size_type left, size_type right) const { return m_discretizer[m_table.maximum(left, right)]; }
Tp quantile(size_type left, size_type right, size_type k) const { return m_discretizer[m_table.quantile(left, right, k)]; }
template <typename Callback>
void do_for_rank_range(size_type left, size_type right, size_type rk1, size_type rk2, Callback &&call) const { m_table.do_for_rank_range(left, right, rk1, rk2, call); }
template <typename Callback>
void do_for_value_range(size_type left, size_type right, const Tp &floor, const Tp &ceil, Callback &&call) const { m_table.do_for_value_range(left, right, _find(floor), _upper_find(ceil) - 1, call); }
};
}
}
#endif
#ifndef __OY_POINTADDRECTSUMCOUNTER2D__
#define __OY_POINTADDRECTSUMCOUNTER2D__
namespace OY {
namespace PARSC2D {
using size_type = uint32_t;
template <typename SizeType, typename WeightType, bool HasModify>
struct Point {
SizeType m_x, m_y;
WeightType m_w;
};
template <typename SizeType, typename WeightType>
struct Point<SizeType, WeightType, true> {
SizeType m_x, m_y;
size_type m_index;
WeightType m_w;
};
template <typename SizeType>
struct Point<SizeType, bool, false> {
SizeType m_x, m_y;
};
template <typename SizeType>
struct Point<SizeType, bool, true> {
SizeType m_x, m_y;
size_type m_index;
};
template <typename Tp>
struct AdjTable {
std::vector<Tp> m_sum;
template <typename InitMapping>
void resize(size_type length, InitMapping mapping) {
m_sum.resize(length + 1);
for (size_type i = 0; i != length; i++) m_sum[i + 1] = m_sum[i] + mapping(i);
}
Tp query(size_type left, size_type right) const { return m_sum[right + 1] - m_sum[left]; }
};
template <typename Tp>
struct SimpleBIT {
std::vector<Tp> m_sum;
static size_type _lowbit(size_type x) { return x & -x; }
template <typename InitMapping>
void resize(size_type length, InitMapping mapping) {
m_sum.resize(length);
for (size_type i = 0; i != length; i++) m_sum[i] = mapping(i);
for (size_type i = 0; i != length; i++) {
size_type j = i + _lowbit(i + 1);
if (j < length) m_sum[j] += m_sum[i];
}
}
void add(size_type i, size_type inc) {
while (i < m_sum.size()) m_sum[i] += inc, i += _lowbit(i + 1);
}
Tp presum(size_type i) const {
Tp res{};
for (size_type j = i; ~j; j -= _lowbit(j + 1)) res += m_sum[j];
return res;
}
Tp query(size_type left, size_type right) const { return presum(right) - presum(left - 1); }
};
template <typename SizeType, typename WeightType = bool, typename SumType = typename std::conditional<std::is_same<WeightType, bool>::value, size_type, WeightType>::type, bool HasModify = false>
struct Table {
static constexpr bool is_bool = std::is_same<WeightType, bool>::value;
using point = Point<SizeType, WeightType, HasModify>;
using inner_table = typename std::conditional<HasModify, SimpleBIT<SumType>, AdjTable<SumType>>::type;
using wavelet = WaveLet::Table<size_type, inner_table>;
std::vector<point> m_points;
std::vector<SizeType> m_sorted_xs, m_ys;
std::vector<size_type> m_point_pos;
wavelet m_table;
Table() = default;
Table(size_type point_cnt) { m_points.reserve(point_cnt); }
void add_point(SizeType x, SizeType y, WeightType w = 1) {
if constexpr (is_bool)
if constexpr (HasModify)
m_points.push_back({x, y, size_type(m_points.size())});
else
m_points.push_back({x, y});
else if constexpr (HasModify)
m_points.push_back({x, y, size_type(m_points.size()), w});
else
m_points.push_back({x, y, w});
}
void prepare() {
std::sort(m_points.begin(), m_points.end(), [](const point &x, const point &y) { return x.m_y < y.m_y; });
m_ys.reserve(m_points.size());
std::vector<WeightType> wtable;
if constexpr (!is_bool) wtable.reserve(m_points.size());
for (auto &p : m_points) {
m_ys.push_back(p.m_y), p.m_y = m_ys.size() - 1;
if constexpr (!is_bool) wtable.push_back(p.m_w);
}
std::sort(m_points.begin(), m_points.end(), [](const point &x, const point &y) { return x.m_x < y.m_x; });
auto mapping = [&](size_type i) { return m_points[i].m_y; };
auto table_mapping = [&](size_type y) -> SumType {
if constexpr (is_bool)
return 1;
else
return wtable[y];
};
m_table.resize(m_points.size(), mapping, std::bit_width(m_points.size()), table_mapping);
m_sorted_xs.reserve(m_points.size());
for (auto &p : m_points) m_sorted_xs.push_back(p.m_x);
if constexpr (HasModify) {
m_point_pos.resize(m_points.size());
for (size_type i = 0; i != m_points.size(); i++) m_point_pos[m_points[i].m_index] = i;
}
}
SumType query(SizeType x_min, SizeType x_max, SizeType y_min, SizeType y_max) const {
auto y1 = std::lower_bound(m_ys.begin(), m_ys.end(), y_min) - m_ys.begin(), y2 = std::upper_bound(m_ys.begin(), m_ys.end(), y_max) - m_ys.begin() - 1;
SumType res{};
if (y1 != y2 + 1) m_table.do_for_value_range(std::lower_bound(m_sorted_xs.begin(), m_sorted_xs.end(), x_min) - m_sorted_xs.begin(), std::upper_bound(m_sorted_xs.begin(), m_sorted_xs.end(), x_max) - m_sorted_xs.begin() - 1, y1, y2, [&](SumType val) { res += val; });
return res;
}
void add_point_value(size_type point_id, WeightType w) {
static_assert(HasModify, "HasModify Must Be True");
m_table.do_in_table(m_point_pos[point_id], [w](inner_table &tr, size_type pos) { tr.add(pos, w); });
}
};
};
}
#endif
}
// faster implementation
// source: https://judge.yosupo.jp/submission/42086
void SA_IS(const int *s, int *SA, int n, int K) {
// s 为字符串数组[0..n-1] 必须保证 s[n-1]=0 且为最小值
// SA 为存储后缀数组[0..n-1]
// n 为字符串长度
// K 为值域
bool *t = new bool[n]; // 类型数组
int *bkt = new int[K]; // 桶
int *bkt_l = new int[K];
int *bkt_r = new int[K];
int n1 = 0; // LMS-后缀的数量
int *p1; //按出现顺序存储所有 LMS-后缀的索引
#define is_S_type(x) (t[x])
#define is_L_type(x) (!t[x])
#define is_LMS_type(x) (is_S_type(x) && x != 0 && is_L_type(x - 1))
// 预处理每一个后缀的类型
t[n - 1] = true; // 0 为 S-型后缀且为 LMS-型后缀
for (int i = n - 2; i >= 0; --i) {
t[i] = (s[i] < s[i + 1] || (is_S_type(i + 1) && s[i] == s[i + 1]));
n1 += is_LMS_type(i + 1); // s[0] 必然不是 LMS-型后缀，不会影响
}
// 预处理桶的边界
for (int i = 0; i != K; ++i) bkt[i] = 0;
for (int i = 0; i != n; ++i) ++bkt[s[i]];
for (int i = 0, sum = 0; i != K; ++i) sum += bkt[i], bkt_r[i] = sum, bkt_l[i] = sum - bkt[i];
#define indecud_sort() \
do { \
for (int i = 0; i != K; ++i) bkt[i] = bkt_l[i]; \
for (int i = 0, j; i != n; ++i) \
if ((j = SA[i] - 1) >= 0 && is_L_type(j)) SA[bkt[s[j]]++] = j; \
for (int i = 0; i != K; ++i) bkt[i] = bkt_r[i]; \
for (int i = n - 1, j; i >= 0; --i) \
if ((j = SA[i] - 1) >= 0 && is_S_type(j)) SA[--bkt[s[j]]] = j; \
} while (0)
// 将所有 LMS-后缀放入 SA 对应桶的末尾并诱导排序
p1 = new int[n1];
for (int i = 0, j = 0; i != n; ++i) {
SA[i] = -1;
if (is_LMS_type(i)) p1[j++] = i;
}
for (int i = 0; i != K; ++i) bkt[i] = bkt_r[i];
for (int i = n1 - 1; i >= 0; --i) SA[--bkt[s[p1[i]]]] = p1[i];
indecud_sort();
int *s1 = new int[n1]; // 新的字符串
int *SA1 = new int[n1]; // 存储新的字符串排的后缀数组
for (int i = 0, j = 0; i != n; ++i)
if (is_LMS_type(SA[i])) SA1[j++] = SA[i]; // 存储 LMS-子串的相对顺序
int name = 0;
// 对所有 LMS-子串命名
for (int i = 0, prev = -1; i != n1; ++i) {
int pos = SA1[i];
for (int j = 0;; ++j) // 无需设置范围，因为 s[n-1]=0 为最小值且不会出现在其余位置
if (prev == -1 || s[pos + j] != s[prev + j] || is_S_type(pos + j) != is_S_type(prev + j)) {
prev = pos, ++name;
break;
} else if (j != 0 && (is_LMS_type(pos + j) || is_LMS_type(prev + j))) // 到末尾了停止比较
break;
SA[pos] = name - 1; // 利用 SA 暂时存储新字符串的 name
}
for (int i = 0; i != n1; ++i) s1[i] = SA[p1[i]];
if (name != n1)
SA_IS(s1, SA1, n1, name);
else
for (int i = 0; i != n1; ++i) SA1[s1[i]] = i;
for (int i = 0; i != K; ++i) bkt[i] = bkt_r[i];
for (int i = 0; i != n; ++i) SA[i] = -1;
for (int i = n1 - 1; i >= 0; --i) SA[--bkt[s[p1[SA1[i]]]]] = p1[SA1[i]];
indecud_sort();
delete[] SA1;
delete[] s1;
delete[] p1;
delete[] bkt_r;
delete[] bkt_l;
delete[] bkt;
delete[] t;
#undef is_S_type
#undef is_L_type
#undef is_LMS_type
#undef indecud_sort
}
const ll INF = 2e18;
const int INFi = 1e9;
const int N = 2e5 + 50;
const int LG = 20;
std::vector<int> get_sa(const std::string &s) {
int len = s.size();
std::vector<int> SA(len + 1), s_cpy(len + 1);
for (int i = 0; i != len; ++i) s_cpy[i] = s[i];
s_cpy.back() = 0;
SA_IS(s_cpy.data(), SA.data(), len + 1, 128);
return std::vector<int>(SA.begin() + 1, SA.end());
}
auto min_merge = [](int x, int y) {
return min(x, y);
};
struct suffix_array {
std::vector<int> order, suffix_position, lcp;
string s;
SPARSE::OY::SqrtMinTable<uint32_t, SPARSE::OY::SQRT::NonRandomController<4>, 16> sp;
suffix_array() {
}
void build(std::string str) {
order.clear();
suffix_position.clear();
lcp.clear();
s.clear();
s = str;
int n = str.size() + 1;
order = get_sa(str);
order.insert(order.begin(), n - 1);
suffix_position.resize(n);
for (int i = 0; i < n; i++) {
suffix_position[order[i]] = i;
}
lcp.resize(n);
int current_lcp = 0;
for (int suffix = 0; suffix < n - 1; suffix++, current_lcp = current_lcp == 0 ? 0 : current_lcp - 1) {
int previous_suffix = order[suffix_position[suffix] - 1];
while (str[suffix + current_lcp] == str[previous_suffix + current_lcp])
current_lcp++;
lcp[suffix_position[suffix]] = current_lcp;
}
sp = SPARSE::OY::SqrtMinTable<uint32_t, SPARSE::OY::SQRT::NonRandomController<4>, 16>(all(lcp));
}
int LCP(int l, int r) {
if (l == r) return (int) suffix_position.size() - 1 - l;
l = suffix_position[l];
r = suffix_position[r];
if (l > r) swap(l, r);
return sp.query(l + 1, r);
}
char Get(int pos) {
return s[pos];
}
} S;
struct Element {
vector<pair<uint32_t, uint32_t>> a;
uint32_t idx;
int priority;
ll length;
void read() {
uint32_t k;
cin >> k;
a.resize(k);
length = 0;
for (auto &[l, r]: a) {
cin >> l >> r;
l--;
length += r - l;
}
}
};
pair<bool, ll> Comp(const Element &a, const Element &b) {
if (a.a == b.a) return make_pair(a.priority < b.priority, a.length);
ll total = 0;
int i = 0;
int used_i = 0;
int j = 0;
int used_j = 0;
while (true) {
if (j == b.a.size() && i == a.a.size()) return make_pair(a.priority < b.priority, total);
if (j == b.a.size()) return make_pair(b.priority > 0 ? true : false, total);
if (i == a.a.size()) return make_pair(a.priority > 0 ? false : true, total);
int mx_i = a.a[i].second - a.a[i].first - used_i;
int mx_j = b.a[j].second - b.a[j].first - used_j;
int mx = min(mx_i, mx_j);
int len = S.LCP(a.a[i].first + used_i, b.a[j].first + used_j);
ckmin(len, mx);
used_i += len;
used_j += len;
total += len;
if (len < mx) return make_pair(S.Get(a.a[i].first + used_i) < S.Get(b.a[j].first + used_j), total);
if (mx_i == len) {
i++;
used_i = 0;
}
if (mx_j == len) {
j++;
used_j = 0;
}
}
return {false, 0};
}
bool operator<(const Element &a, const Element &b) {
return Comp(a, b).first;
}
void solve() {
uint32_t n, q;
cin >> n >> q;
string s;
cin >> s;
vector<Element> elems;
vector<int> ban;
auto Add = [&](Element e, int ww) {
e.idx = elems.size();
elems.push_back(e);
ban.push_back(ww);
return e.idx;
};
vector<ar<uint32_t, 5>> qs(q, {0, 0, 0, 0, 0});
for (auto &[tp, l1, r1, l2, r2]: qs) {
char t;
cin >> t;
if (t == '+') {
Element e;
e.read();
e.priority = -1;
tp = 1;
l1 = Add(e, -1);
} else if (t == '-') {
tp = q - 1;
int pos;
cin >> pos;
pos--;
l1 = qs[pos][1];
} else {
tp = 0;
Element e1, e2;
e1.read();
e2.read();
// e1.priority = -2;
// l1 = Add(e1, 1);
e1.priority = 2;
r1 = Add(e1, 1);
// e2.priority = -2;
// l2 = Add(e2, 0);
e2.priority = 2;
r2 = Add(e2, 0);
}
}
vector<ar<int, 2>> pos(elems.size()), pos2(elems.size());
rep(rot, 2) {
S.build(s);
vector<Element> els;
rep(i, elems.size()) if (ban[i] != rot) {
els.push_back(elems[i]);
}
sort(all(els));
vector<pair<ll, int>> stk;
rep(i, els.size()) {
if (i) {
ll val = Comp(els[i - 1], els[i]).second;
int j = i - 1;
while (!stk.empty() && stk.back().first >= val) {
j = stk.back().second;
stk.pop_back();
}
stk.emplace_back(val, j);
}
pos[els[i].idx][rot] = i;
if (!stk.empty() && stk.back().first == els[i].length) {
pos2[els[i].idx][rot] = stk.back().second;
} else {
pos2[els[i].idx][rot] = i;
}
}
reverse(all(s));
for (auto &e: elems) {
for (auto &[l, r]: e.a) {
r--;
swap(l, r);
l = n - 1 - l;
r = n - 1 - r;
r++;
}
reverse(all(e.a));
}
}
SOLVE_2D::OY::PARSC2D::Table<uint32_t, uint32_t, uint64_t, true> sol(0);
for (auto &[tp, l1, r1, l2, r2]: qs) {
if (tp == 1) {
int i = l1;
l1 = r1 = pos[i][0];
l2 = r2 = pos[i][1];
// cerr << "+ " << l1 << ' ' << l2 << endl;
sol.add_point(l1, l2, 0);
// rect1.update(l1, l2, 1);
} else if (tp == q-1) {
int i = l1;
l1 = r1 = pos[i][0];
l2 = r2 = pos[i][1];
// cerr << "- " << l1 << ' ' << l2 << endl;
sol.add_point(l1, l2, 0);
// rect2.update(l1, l2, 1);
} else {
l1 = pos2[r1][0];
r1 = pos[r1][0];
l2 = pos2[r2][1];
r2 = pos[r2][1];
// cerr << "? " << l1 << ' ' << r1 << ' ' << l2 << ' ' << r2 << endl;
// rect1.query(l1, r1, l2, r2);
// rect2.query(l1, r1, l2, r2);
}
}
sol.prepare();
int id = 0;
for (auto &[tp, l1, r1, l2, r2]: qs) {
if (tp == 1 || tp == -1) {
sol.add_point_value(id++, tp);
} else {
cout << sol.query(l1, r1, l2, r2) % q << '\n';
}
}
}
signed main() {
int t = 1;
// cin >> t;
rep(i, t) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3800kb
input:
8 7 abcaabbc + 3 1 3 2 4 3 8 + 2 1 4 1 8 + 1 2 4 ? 1 5 6 1 7 8 - 3 + 1 2 5 ? 1 2 3 1 5 5
output:
2 1 2
result:
wrong output format Extra information in the output file