NOIP22 比賽

match.cpp

#include <array>
#include <iostream>
#include <tuple>
#include <vector>

using i64 = long long;
using i128 = __int128_t;
using u32 = unsigned int;
using u64 = unsigned long long;
using u128 = __uint128_t;

struct MatrixSum
{
  u64 v0, v1, v2, v3, v4;

  constexpr MatrixSum() : MatrixSum(0, 0, 0, 0, 0) {}
  constexpr MatrixSum(u64 v0, u64 v1, u64 v2, u64 v3, u64 v4)
      : v0(v0), v1(v1), v2(v2), v3(v3), v4(v4)
  {
  }
};

// clang-format off
MatrixSum operator*(const MatrixSum &b, const MatrixSum &c)
{
  return {
    b.v0 + c.v0,
    b.v1 + c.v1,
    b.v2 + c.v2,
    b.v3 + c.v3,
    b.v4 + c.v4,
  };
}

struct MatrixMul
{
  u64 a00, a01, a02, a03, a04, a11, a12, a13, a14, a22, a24, a33, a34, a44;

  constexpr MatrixMul() : MatrixMul{
    1, 0, 0, 0, 0,
       1, 0, 0, 0,
          1,    0,
             1, 0,
                1,
  } {}

  constexpr MatrixMul(u64 a00, u64 a01, u64 a02, u64 a03, u64 a04,
                               u64 a11, u64 a12, u64 a13, u64 a14,
                                        u64 a22,          u64 a24,
                                                 u64 a33, u64 a34,
                                                          u64 a44)
    : a00(a00), a01(a01), a02(a02), a03(a03), a04(a04), 
                a11(a11), a12(a12), a13(a13), a14(a14), 
                          a22(a22),           a24(a24),
                                    a33(a33), a34(a34),
                                              a44(a44) {}

  MatrixSum operator()(const MatrixSum &v) const
  {
    return {
      a00 * v.v0 + a01 * v.v1 + a02 * v.v2 + a03 * v.v3 + a04 * v.v4,
      a11 * v.v1 + a12 * v.v2 + a13 * v.v3 + a14 * v.v4,
      a22 * v.v2 + a24 * v.v4,
      a33 * v.v3 + a34 * v.v4,
      a44 * v.v4,
    };
  }
};

MatrixMul operator*(const MatrixMul &c, const MatrixMul &b)
{
  return {
    b.a00 * c.a00,
    b.a00 * c.a01 + b.a01 * c.a11,
    b.a00 * c.a02 + b.a01 * c.a12 + b.a02 * c.a22,
    b.a00 * c.a03 + b.a01 * c.a13 + b.a03 * c.a33,
    b.a00 * c.a04 + b.a01 * c.a14 + b.a02 * c.a24 + b.a03 * c.a34 + b.a04 * c.a44,
    b.a11 * c.a11,
    b.a11 * c.a12 + b.a12 * c.a22,
    b.a11 * c.a13 + b.a13 * c.a33,
    b.a11 * c.a14 + b.a12 * c.a24 + b.a13 * c.a34 + b.a14 * c.a44,
    b.a22 * c.a22,
    b.a22 * c.a24 + b.a24 * c.a44,
    b.a33 * c.a33,
    b.a33 * c.a34 + b.a34 * c.a44,
    b.a44 * c.a44,
  };
}
// clang-format on

int ceil_pow2(int x)
{
  int y = 0;
  while ((1 << y) < x) y++;
  return y;
}

template <typename S, typename T> struct LazySegtree
{
  int n, log, size;
  std::vector<S> s;
  std::vector<T> t;

  template <typename F>
  LazySegtree(int n, F &&f)
      : n(n), log(ceil_pow2(n)), size(1 << log), s(size * 2), t(size)
  {
    for (int i = 0; i < n; i++) { s[i + size] = f(i); }
    for (int i = size; --i;) update(i);
  }

  void update(int x) { s[x] = s[x * 2] * s[x * 2 + 1]; }

  void apply_at(int x, const T &tag)
  {
    s[x] = tag(s[x]);
    if (x < size) t[x] = t[x] * tag;
  }

  void push(int x)
  {
    apply_at(x * 2, t[x]);
    apply_at(x * 2 + 1, t[x]);
    t[x] = {};
  }

  S prod(int l, int r)
  {
    l += size;
    r += size;

    for (int i = log; i >= 1; i--) {
      if (((l >> i) << i) != l) push(l >> i);
      if (((r >> i) << i) != r) push((r - 1) >> i);
    }

    S ls, rs;
    while (l < r) {
      if (l & 1) ls = ls * s[l++];
      if (r & 1) rs = s[--r] * rs;
      l >>= 1;
      r >>= 1;
    }

    return ls * rs;
  }

  void apply(int l, int r, const T &tag)
  {
    l += size;
    r += size;

    for (int i = log; i >= 1; i--) {
      if (((l >> i) << i) != l) push(l >> i);
      if (((r >> i) << i) != r) push((r - 1) >> i);
    }

    {
      int l2 = l, r2 = r;
      while (l < r) {
        if (l & 1) apply_at(l++, tag);
        if (r & 1) apply_at(--r, tag);
        l >>= 1;
        r >>= 1;
      }
      std::tie(l, r) = {l2, r2};
    }

    for (int i = 1; i <= log; i++) {
      if (((l >> i) << i) != l) update(l >> i);
      if (((r >> i) << i) != r) update((r - 1) >> i);
    }
  }
};

// clang-format off
constexpr MatrixMul gen_change_a_mat(u64 x)
{
  return {
      1, 0, 0, 0, 0,
         0, 0, x, 0,
            0,    x,
               1, 0,
                  1,
  };
}

constexpr MatrixMul gen_change_b_mat(u64 x)
{
  return {
      1, 0, 0, 0, 0, 
         0, x, 0, 0,
            1,    0,
               0, x,
                  1,
  };
}

constexpr MatrixMul gen_history_sum_mat()
{
  return {
      1, 1, 0, 0, 0,
         1, 0, 0, 0,
            1,    0,
               1, 0,
                  1,
  };
}
// clang-format on

int main()
{
  int testcase_id;
  std::cin >> testcase_id;

  int n;
  std::cin >> n;

  std::vector<u64> a(n), b(n);
  for (auto &i : a) std::cin >> i;
  for (auto &i : b) std::cin >> i;

  int m;
  std::cin >> m;
  std::vector<std::array<int, 2>> q;
  std::vector<std::vector<int>> qr(n + 1);
  for (int i = 0; i < m; i++) {
    int l, r;
    std::cin >> l >> r;
    l--;
    q.emplace_back(std::array{l, r});
    qr[r].emplace_back(i);
  }

  std::vector<u64> ans(m);

  LazySegtree<MatrixSum, MatrixMul> s(n, [&](int) -> MatrixSum {
    return {
        0ull, 0ull, 0ull, 0ull, 1ull,
    };
  });
  std::vector<int> sa, sb;
  for (int i = 0; i < n; i++) {
    while (!sa.empty() && a[sa.back()] < a[i]) sa.pop_back();
    int a_last = sa.empty() ? 0 : sa.back() + 1;
    s.apply(a_last, i + 1, gen_change_a_mat(a[i]));
    sa.emplace_back(i);

    while (!sb.empty() && b[sb.back()] < b[i]) sb.pop_back();
    int b_last = sb.empty() ? 0 : sb.back() + 1;
    s.apply(b_last, i + 1, gen_change_b_mat(b[i]));
    sb.emplace_back(i);

    s.apply(0, i + 1, gen_history_sum_mat());

    for (auto qi : qr[i + 1]) {
      int l = q[qi][0];
      ans[qi] = s.prod(l, i + 1).v0;
    }
  }

  for (auto i : ans) std::cout << i << "\n";
}