jacky860226

#include <atomic>
#include <cassert>
#include <new>
#include <thread>
#include <utility>

#if __cplusplus >= 202002L
#include <bit>
#elif defined(_MSC_VER)
#include <intrin.h>

jacky860226

#pragma once
#include <atomic>
#include <cstdint>
#include <cstring>
#include <deque>
#include <functional>
#include <memory>
#include <thread>

namespace TLS::detail {

jacky860226

#pragma once
#include <algorithm>
#include <array>
#include <cstring>
#include <random>

template <typename T, size_t max_level = 32, typename Compare = std::less<T>>
class SkipList {
  struct Node {
    union {

jacky860226

#pragma once

#include <algorithm>
#include <atomic>
#include <cassert>
#include <cstddef>
#include <iterator>
#include <memory>
#include <thread>

jacky860226

using Point = pair<int,int>;
ll cross(const Point& a, const Point& b) {
    return 1ll * a.first * b.second - 1ll * a.second * b.first;
}
// 逆时针
// 参考 mnbvmar 的写法：https://codeforces.com/contest/1284/submission/68178688
bool cmp_polar(const Point& a, const Point& b) {
    bool aorig = a.second > 0;
    bool borig = b.second > 0;
    if (aorig != borig) {

jacky860226

using LL = long long;
auto garner(const std::vector<LL> &A, const std::vector<LL> &M, LL mod) {
    assert(A.size() == M.size());
    auto X = A;
    for (size_t i = 0; i < A.size(); ++i) {
        for (size_t j = 0; j < i; ++j) {
            X[i] = mod_inv(M[j], M[i]) * (X[i] - X[j]) % M[i];
            if (X[i] < 0) X[i] += M[i];
        }
    }

jacky860226

#include <algorithm>
#include <cassert>
#include <cstddef>
template <typename T, typename Policy>
class CooleyTukeyAlgorithm {
    size_t reverse_bits_len(size_t N, size_t len) {
        return ::reverse_bits(N) >> (sizeof(N) * 8 - len);
    }

   public:

jacky860226

template <class ValueTy> struct Tree {
  int L, R;
  Tree *lc, *rc;
  ValueTy Val;
  Tree() = default;
  Tree(int L, int R) : L(L), R(R), lc(nullptr), rc(nullptr), Val() {}
  void pull() {
    Val = 0;
    if (lc)
      Val += lc->Val;

jacky860226

#include <bits/stdc++.h>
using namespace std;

namespace system_test {

const size_t KB = 1024;
const size_t MB = KB * 1024;
const size_t GB = MB * 1024;

size_t block_size, bound;

jacky860226

#include <algorithm>
#include <stdexcept>
#include <vector>
template <typename T, typename Alloc = std::allocator<T>>
class Discretizer : private std::vector<T, Alloc> {
  void build() {
    std::sort(std::vector<T, Alloc>::begin(), std::vector<T, Alloc>::end());
    std::vector<T, Alloc>::erase(std::unique(std::vector<T, Alloc>::begin(),
                                             std::vector<T, Alloc>::end()),
                                 std::vector<T, Alloc>::end());