QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#311914#4255. Sone2hos_lyric#50 113ms33252kbC++1420.2kb2024-01-22 23:33:322024-07-04 03:21:21

Judging History

你现在查看的是最新测评结果

  • [2024-07-04 03:21:21]
  • 评测
  • 测评结果:50
  • 用时:113ms
  • 内存:33252kb
  • [2024-01-22 23:33:32]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


////////////////////////////////////////////////////////////////////////////////
// SA-IS
//   String: string, vector<int>, vector<long long>
//   if sigma <= n,  O(n) time, O(n) space
//   if sigma >  n,  O(n log n) time, O(n) space
template <class String> vector<int> suffixArrayRec(const String &as) {
  const int n = as.size();
  if (n == 0) return {};
  const auto minmaxA = minmax_element(as.begin(), as.end());
  const auto minA = *minmaxA.first, maxA = *minmaxA.second;
  if (static_cast<unsigned long long>(maxA) - minA >=
      static_cast<unsigned long long>(n)) {
    vector<int> us(n);
    for (int u = 0; u < n; ++u) us[u] = u;
    std::sort(us.begin(), us.end(), [&](int u, int v) -> bool {
      return (as[u] < as[v]);
    });
    int b = 0;
    vector<int> bs(n, 0);
    for (int i = 1; i < n; ++i) {
      if (as[us[i - 1]] != as[us[i]]) ++b;
      bs[us[i]] = b;
    }
    return suffixArrayRec(bs);
  }
  const int sigma = maxA - minA + 1;
  vector<int> pt(sigma + 1, 0), poss(sigma);
  for (int u = 0; u < n; ++u) ++pt[as[u] - minA + 1];
  for (int a = 0; a < sigma; ++a) pt[a + 1] += pt[a];
  // cmp[u] := (as[u, n) < as[u + 1, n))
  vector<bool> cmp(n);
  cmp[n - 1] = false;
  for (int u = n - 1; --u >= 0; ) {
    cmp[u] = (as[u] != as[u + 1]) ? (as[u] < as[u + 1]) : cmp[u + 1];
  }
  // ><,  nn - id (0 <= id < n)
  int nn = 0;
  vector<int> ids(n, 0);
  int last = n;
  vector<int> nxt(n, 0);
  // put ><, from the tail of each bucket
  vector<int> us(n, 0);
  memcpy(poss.data(), pt.data() + 1, sigma * sizeof(int));
  for (int u = n - 1; --u >= 1; ) if (!cmp[u - 1] && cmp[u]) {
    ids[u] = ++nn;
    nxt[u] = last;
    last = u;
    us[--poss[as[u] - minA]] = u;
  }
  // follow > backwards, from the head of each bucket
  memcpy(poss.data(), pt.data(), sigma * sizeof(int));
  us[poss[as[n - 1] - minA]++] = n - 1;
  for (int i = 0; i < n; ++i) {
    const int u = us[i];
    if (u && !cmp[u - 1]) us[poss[as[u - 1] - minA]++] = u - 1;
  }
  // follow < backwards, from the tail of each bucket
  memcpy(poss.data(), pt.data() + 1, sigma * sizeof(int));
  for (int i = n; --i >= 0; ) {
    const int u = us[i];
    if (u && cmp[u - 1]) us[--poss[as[u - 1] - minA]] = u - 1;
  }
  if (nn) {
    int vsLen = 0;
    vector<int> vs(nn);
    for (const int u : us) if (ids[u]) vs[vsLen++] = u;
    int b = 0;
    vector<int> bs(nn, 0);
    for (int j = 1; j < nn; ++j) {
      // as[v1, w1] (< or =) as[v0, w0]
      int v1 = vs[j - 1], v0 = vs[j];
      const int w1 = nxt[v1], w0 = nxt[v0];
      if (w1 - v1 != w0 - v0) {
        ++b;
      } else {
        for (; ; ++v1, ++v0) {
          if (v1 == n) { ++b; break; }
          if (as[v1] != as[v0]) { ++b; break; }
          if (v1 == w1) break;
        }
      }
      bs[nn - ids[vs[j]]] = b;
    }
    for (int u = 0; u < n; ++u) if (ids[u]) vs[nn - ids[u]] = u;
    const auto sub = suffixArrayRec(bs);
    // put ><, from the tail of each bucket
    memset(us.data(), 0, n * sizeof(int));
    memcpy(poss.data(), pt.data() + 1, sigma * sizeof(int));
    for (int j = nn; --j >= 0; ) {
      const int u = vs[sub[j]];
      us[--poss[as[u] - minA]] = u;
    }
    // follow > backwards, from the head of each bucket
    memcpy(poss.data(), pt.data(), sigma * sizeof(int));
    us[poss[as[n - 1] - minA]++] = n - 1;
    for (int i = 0; i < n; ++i) {
      const int u = us[i];
      if (u && !cmp[u - 1]) us[poss[as[u - 1] - minA]++] = u - 1;
    }
    // follow < backwards, from the tail of each bucket
    memcpy(poss.data(), pt.data() + 1, sigma * sizeof(int));
    for (int i = n; --i >= 0; ) {
      const int u = us[i];
      if (u && cmp[u - 1]) us[--poss[as[u - 1] - minA]] = u - 1;
    }
  }
  return us;
}

// us[i]: i-th suffix
// su[u]: index of as[u, n)
// hs[i]: longest common prefix of as[us[i - 1], n) and as[us[i], n)
struct SuffixArray {
  int n;
  bool rmq;
  vector<int> us, su, hs, bsr;
  SuffixArray() : n(0), rmq(false) {}
  SuffixArray(const string &as, bool rmq_) : rmq(rmq_) { build(as); }
  SuffixArray(const vector<int> &as, bool rmq_) : rmq(rmq_) { build(as); }
  SuffixArray(const vector<long long> &as, bool rmq_) : rmq(rmq_) { build(as); }
  template <class String> void build(const String &as) {
    n = as.size();
    us = suffixArrayRec(as);
    su.resize(n + 1);
    for (int i = 0; i < n; ++i) su[us[i]] = i;
    su[n] = -1;
    hs.assign(n, 0);
    for (int h = 0, u = 0; u < n; ++u) if (su[u]) {
      for (int v = us[su[u] - 1]; v + h < n && as[v + h] == as[u + h]; ++h) {}
      hs[su[u]] = h;
      if (h) --h;
    }
    if (rmq) {
      const int logN = n ? (31 - __builtin_clz(n)) : 0;
      hs.resize((logN + 1) * n - (1 << logN) + 1);
      for (int e = 0; e < logN; ++e) {
        int *hes = hs.data() + e * n;
        for (int i = 0; i <= n - (1 << (e + 1)); ++i) {
          hes[n + i] = min(hes[i], hes[i + (1 << e)]);
        }
      }
      bsr.resize(n + 1);
      bsr[0] = -1;
      for (int i = 1; i <= n; ++i) bsr[i] = bsr[i >> 1] + 1;
    }
  }
  // Returns longest common prefix of as[u, n) and as[v, n).
  //   0 <= u, v <= n
  //   Assumes rmq.
  inline int lcp(int u, int v) const {
    if (u == v) return n - u;
    int i = su[u], j = su[v];
    if (i > j) swap(i, j);
    const int e = bsr[j - i];
    return min(hs[e * n + i + 1], hs[e * n + j + 1 - (1 << e)]);
  }
};
////////////////////////////////////////////////////////////////////////////////


// zs[i] := lcp(as[0, n), as[i, n))
// 0    i-j     j     i
// |-------|    |-------|    zs[j]
// |---| |---|  |---| |---|  zs[i-j]
template <class T> void suffixZ(const T *as, int n, int *zs) {
  if (n == 0) return;
  zs[0] = 0;
  for (int j = 0, i = 1; i < n; ++i) {
    if (i + zs[i - j] < j + zs[j]) {
      zs[i] = zs[i - j];
    } else {
      int &z = zs[i] = max(j + zs[j] - i, 0);
      for (; i + z < n && as[z] == as[i + z]; ++z) {}
      j = i;
    }
  }
  zs[0] = n;
}
template <class T> vector<int> suffixZ(const T &as) {
  vector<int> zs(as.size());
  suffixZ(as.data(), as.size(), zs.data());
  return zs;
}

////////////////////////////////////////////////////////////////////////////////


template <class X, class Y, class T> struct StaticPointAddRectSum {
  struct Rect {
    X x0, x1;
    Y y0, y1;
  };
  vector<pair<X, Y>> as;
  vector<Rect> bs;
  vector<T> vals, anss;
  // Adds val to (x, y).
  void add(X x, Y y, const T &val) {
    as.emplace_back(x, y);
    vals.push_back(val);
  }
  // Gets sum of [x0, x1) * [y0, y1).
  //   ~~> Gets (x*, y*)
  void get(X x0, X x1, Y y0, Y y1) {
    assert(x0 <= x1); assert(y0 <= y1);
    bs.push_back(Rect{x0, x1, y0, y1});
  }

  void run() {
    const int asLen = as.size(), bsLen = bs.size();

    // same x ==> get then add
    vector<pair<X, int>> events((bsLen << 1) + asLen);
    for (int i = 0; i < asLen; ++i) {
      events[(bsLen << 1) + i] = std::make_pair(as[i].first, (bsLen << 1) + i);
    }
    for (int j = 0; j < bsLen; ++j) {
      events[j << 1    ] = std::make_pair(bs[j].x0, j << 1    );
      events[j << 1 | 1] = std::make_pair(bs[j].x1, j << 1 | 1);
    }
    std::sort(events.begin(), events.end());

    vector<Y> ys(asLen);
    for (int i = 0; i < asLen; ++i) {
      ys[i] = as[i].second;
    }
    std::sort(ys.begin(), ys.end());
    ys.erase(std::unique(ys.begin(), ys.end()), ys.end());
    const int ysLen = ys.size();
    vector<T> bit(ysLen, 0);

    anss.assign(bsLen, 0);
    for (const auto &event : events) {
      if (event.second >= bsLen << 1) {
        const int i = event.second - (bsLen << 1);
        for (int l = std::lower_bound(ys.begin(), ys.end(), as[i].second) - ys.begin(); l < ysLen; l |= l + 1) {
          bit[l] += vals[i];
        }
      } else {
        const int j = event.second >> 1;
        T sum = 0;
        for (int l = std::lower_bound(ys.begin(), ys.end(), bs[j].y0) - ys.begin(); l > 0; l &= l - 1) {
          sum -= bit[l - 1];
        }
        for (int l = std::lower_bound(ys.begin(), ys.end(), bs[j].y1) - ys.begin(); l > 0; l &= l - 1) {
          sum += bit[l - 1];
        }
        (event.second & 1) ? (anss[j] += sum) : (anss[j] -= sum);
      }
    }
  }
};

////////////////////////////////////////////////////////////////////////////////

// T: monoid representing information of an interval.
//   T()  should return the identity.
//   T(S s)  should represent a single element of the array.
//   T::pull(const T &l, const T &r)  should pull two intervals.
template <class T> struct SegmentTreePoint {
  int logN, n;
  vector<T> ts;
  SegmentTreePoint() : logN(0), n(0) {}
  explicit SegmentTreePoint(int n_) {
    for (logN = 0, n = 1; n < n_; ++logN, n <<= 1) {}
    ts.resize(n << 1);
  }
  template <class S> explicit SegmentTreePoint(const vector<S> &ss) {
    const int n_ = ss.size();
    for (logN = 0, n = 1; n < n_; ++logN, n <<= 1) {}
    ts.resize(n << 1);
    for (int i = 0; i < n_; ++i) at(i) = T(ss[i]);
    build();
  }
  T &at(int i) {
    return ts[n + i];
  }
  void build() {
    for (int u = n; --u; ) pull(u);
  }

  inline void pull(int u) {
    ts[u].pull(ts[u << 1], ts[u << 1 | 1]);
  }

  // Changes the value of point a to s.
  template <class S> void change(int a, const S &s) {
    assert(0 <= a); assert(a < n);
    ts[a += n] = T(s);
    for (; a >>= 1; ) pull(a);
  }

  // Applies T::f(args...) to point a.
  template <class F, class... Args>
  void ch(int a, F f, Args &&... args) {
    assert(0 <= a); assert(a < n);
    (ts[a += n].*f)(args...);
    for (; a >>= 1; ) pull(a);
  }

  // Calculates the product for [a, b).
  T get(int a, int b) {
    assert(0 <= a); assert(a <= b); assert(b <= n);
    if (a == b) return T();
    a += n; b += n;
    T prodL, prodR, t;
    for (int aa = a, bb = b; aa < bb; aa >>= 1, bb >>= 1) {
      if (aa & 1) { t.pull(prodL, ts[aa++]); prodL = t; }
      if (bb & 1) { t.pull(ts[--bb], prodR); prodR = t; }
    }
    t.pull(prodL, prodR);
    return t;
  }

  // Calculates T::f(args...) of a monoid type for [a, b).
  //   op(-, -)  should calculate the product.
  //   e()  should return the identity.
  template <class Op, class E, class F, class... Args>
#if __cplusplus >= 201402L
  auto
#else
  decltype((std::declval<T>().*F())())
#endif
  get(int a, int b, Op op, E e, F f, Args &&... args) {
    assert(0 <= a); assert(a <= b); assert(b <= n);
    if (a == b) return e();
    a += n; b += n;
    auto prodL = e(), prodR = e();
    for (int aa = a, bb = b; aa < bb; aa >>= 1, bb >>= 1) {
      if (aa & 1) prodL = op(prodL, (ts[aa++].*f)(args...));
      if (bb & 1) prodR = op((ts[--bb].*f)(args...), prodR);
    }
    return op(prodL, prodR);
  }

  // Find min b s.t. T::f(args...) returns true,
  // when called for the partition of [a, b) from left to right.
  //   Returns n + 1 if there is no such b.
  template <class F, class... Args>
  int findRight(int a, F f, Args &&... args) {
    assert(0 <= a); assert(a <= n);
    if ((T().*f)(args...)) return a;
    if (a == n) return n + 1;
    a += n;
    for (; ; a >>= 1) if (a & 1) {
      if ((ts[a].*f)(args...)) {
        for (; a < n; ) {
          if (!(ts[a <<= 1].*f)(args...)) ++a;
        }
        return a - n + 1;
      }
      ++a;
      if (!(a & (a - 1))) return n + 1;
    }
  }

  // Find max a s.t. T::f(args...) returns true,
  // when called for the partition of [a, b) from right to left.
  //   Returns -1 if there is no such a.
  template <class F, class... Args>
  int findLeft(int b, F f, Args &&... args) {
    assert(0 <= b); assert(b <= n);
    if ((T().*f)(args...)) return b;
    if (b == 0) return -1;
    b += n;
    for (; ; b >>= 1) if ((b & 1) || b == 2) {
      if ((ts[b - 1].*f)(args...)) {
        for (; b <= n; ) {
          if (!(ts[(b <<= 1) - 1].*f)(args...)) --b;
        }
        return b - n - 1;
      }
      --b;
      if (!(b & (b - 1))) return -1;
    }
  }
};

////////////////////////////////////////////////////////////////////////////////

constexpr int INF = 1001001001;

struct NodeCountMax {
  int mx, lz;
  int cnt;
  NodeCountMax() : mx(-INF), lz(0), cnt(0) {}
  NodeCountMax(int val) : mx(val), lz(0), cnt(1) {}
  void push(NodeCountMax &l, NodeCountMax &r) {
    if (lz) {
      l.add(lz);
      r.add(lz);
      lz = 0;
    }
  }
  void pull(const NodeCountMax &l, const NodeCountMax &r) {
    if (l.mx > r.mx) {
      mx = l.mx;
      cnt = l.cnt;
    } else if (l.mx < r.mx) {
      mx = r.mx;
      cnt = r.cnt;
    } else {
      mx = l.mx;
      cnt = l.cnt + r.cnt;
    }
  }
  void add(int val) {
    mx += val;
    lz += val;
  }
  // leaf
  void change(int val) {
    mx = val;
    cnt = 1;
  }
};


int ID;
int ALen, BLen;
vector<int> A, B;
int Q;
vector<int> O, Y, Z, Y2, Z2;

SuffixArray saB, saRevB;


namespace brute {
vector<pair<int, int>> run() {
  vector<pair<int, int>> ans(Q, make_pair(-1, -1));
  auto as = A;
#define A do_not_use_A
  for (int q = 0; q < Q; ++q) {
    switch (O[q]) {
      case 1: {
        as[Y[q]] = Z[q];
        for (int i = 0; i < ALen; ++i) {
          int l = 0;
          for (; i + l < ALen && l < BLen && as[i + l] == B[l]; ++l) {}
          if (chmax(ans[q].first, l)) ans[q].second = 0;
          if (ans[q].first == l) ++ans[q].second;
        }
// cerr<<as<<" "<<B<<": "<<ans[q]<<endl;
      } break;
      case 2: {
        for (int i = Y[q]; i < Z[q]; ++i) {
          int l = 0;
          for (; i + l < Z[q] && l < BLen && as[i + l] == B[l]; ++l) {}
          if (chmax(ans[q].first, l)) ans[q].second = 0;
          if (ans[q].first == l) ++ans[q].second;
        }
      } break;
      case 3: {
        int l = 0;
        for (; Y[q] + l < BLen && Z[q] + l < BLen && B[Y[q] + l] == B[Z[q] + l]; ++l) {}
        ans[q].first = l;
      } break;
      case 4: {
        vector<int> cat;
        cat.insert(cat.end(), B.begin() + Y[q], B.begin() + Z[q]);
        cat.insert(cat.end(), B.begin() + Y2[q], B.begin() + Z2[q]);
        const int catLen = cat.size();
        ans[q].first = 0;
        for (int i = 0; i + catLen <= BLen; ++i) {
          bool ok = true;
          for (int j = 0; j < catLen; ++j) if (B[i + j] != cat[j]) {
            ok = false;
            break;
          }
          if (ok) {
            ++ans[q].first;
          }
        }
      } break;
      default: assert(false);
    }
  }
#undef A
  return ans;
}
}  // brute


vector<int> solve3() {
  vector<int> ans(Q, -1);
  for (int q = 0; q < Q; ++q) if (O[q] == 3) {
    ans[q] = saB.lcp(Y[q], Z[q]);
  }
  return ans;
}

vector<int> solve4() {
  StaticPointAddRectSum<int, int, int> f;
  for (int i = 1; i < BLen; ++i) {
    f.add(saRevB.su[BLen - i], saB.su[i], +1);
  }
#define saB do_not_use_saB
#define saRevB do_not_use_saRevB
  // jL <= j < jR <=> [l, r) matches [sa.us[j], *)
  auto sub = [&](const SuffixArray &sa, int l, int r) -> pair<int, int> {
    pair<int, int> ret;
    {
      int lo = -1, hi = sa.su[l];
      for (; lo + 1 < hi; ) {
        const int mid = (lo + hi) / 2;
        ((sa.lcp(sa.us[mid], l) >= r - l) ? hi : lo) = mid;
      }
      ret.first = hi;
    }
    {
      int lo = sa.su[l], hi = sa.n;
      for (; lo + 1 < hi; ) {
        const int mid = (lo + hi) / 2;
        ((sa.lcp(l, sa.us[mid]) >= r - l) ? lo : hi) = mid;
      }
      ret.second = hi;
    }
    return ret;
  };
#undef saB
#undef saRevB
  for (int q = 0; q < Q; ++q) if (O[q] == 4) {
    const auto res1 = sub(saRevB, BLen - Z[q], BLen - Y[q]);
    const auto res2 = sub(saB, Y2[q], Z2[q]);
    f.get(res1.first, res1.second, res2.first, res2.second);
  }
  f.run();
  vector<int> ans(Q, 0);
  int pos = 0;
  for (int q = 0; q < Q; ++q) if (O[q] == 4) {
    ans[q] = f.anss[pos++];
  }
  return ans;
}


namespace slow {
vector<int> as;
vector<int> fs;
SegmentTreePoint<NodeCountMax> seg;
void init() {
  as = A;
  auto B0A = B;
  B0A.push_back(0);
  B0A.insert(B0A.end(), A.begin(), A.end());
  const auto zs = suffixZ(B0A);
  fs.resize(ALen);
  seg = SegmentTreePoint<NodeCountMax>(ALen);
  for (int i = 0; i < ALen; ++i) {
    seg.at(i) = fs[i] = zs[BLen + 1 + i];
  }
  seg.build();
}
#define A do_not_use_A
void block(int pos) {
  for (int i = max(pos - BLen + 1, 0); i <= pos; ++i) {
    if (chmin(fs[i], pos - i)) {
      seg.change(i, fs[i]);
    }
  }
}
void allow(int pos) {
  const int i0 = max(pos - BLen + 1, 0);
  auto b0a = B;
  b0a.push_back(0);
  b0a.insert(b0a.end(), as.begin() + i0, as.begin() + min(pos + BLen, ALen));
  const auto zs = suffixZ(b0a);
  for (int i = i0; i <= pos; ++i) {
    const int f = zs[BLen + 1 + i - i0];
    if (fs[i] != f) {
      seg.change(i, fs[i] = f);
    }
  }
}
pair<int, int> get(int l, int r) {
  const auto res = seg.get(l, r);
  return make_pair(res.mx, res.cnt);
}
#undef A
vector<pair<int, int>> run() {
  vector<pair<int, int>> ans(Q, make_pair(-1, -1));
  init();
  for (int q = 0; q < Q; ++q) {
    if (O[q] == 1) {
      if (as[Y[q]] != Z[q]) {
        block(Y[q]);
        as[Y[q]] = Z[q];
        allow(Y[q]);
      }
      ans[q] = get(0, ALen);
    } else if (O[q] == 2) {
      if (Z[q] < ALen) block(Z[q]);
      ans[q] = get(Y[q], Z[q]);
      if (Z[q] < ALen) allow(Z[q]);
    }
  }
  {
    const auto res = solve3();
    for (int q = 0; q < Q; ++q) if (O[q] == 3) ans[q].first = res[q];
  }
  {
    const auto res = solve4();
    for (int q = 0; q < Q; ++q) if (O[q] == 4) ans[q].first = res[q];
  }
  return ans;
}
}  // slow


int main() {
  for (; ~scanf("%d", &ID); ) {
    scanf("%d", &ALen);
    A.resize(ALen);
    for (int i = 0; i < ALen; ++i) scanf("%d", &A[i]);
    scanf("%d", &BLen);
    B.resize(BLen);
    for (int i = 0; i < BLen; ++i) scanf("%d", &B[i]);
    scanf("%d", &Q);
    O.assign(Q, -1);
    Y.assign(Q, -1);
    Z.assign(Q, -1);
    Y2.assign(Q, -1);
    Z2.assign(Q, -1);
    for (int q = 0; q < Q; ++q) {
      scanf("%d%d%d", &O[q], &Y[q], &Z[q]);
      switch (O[q]) {
        case 1: {
          --Y[q];
        } break;
        case 2: {
          --Y[q];
        } break;
        case 3: {
          --Y[q];
          --Z[q];
        } break;
        case 4: {
          scanf("%d%d", &Y2[q], &Z2[q]);
          --Y[q];
          --Y2[q];
        } break;
        default: assert(false);
      }
    }
    
    auto revB = B;
    reverse(revB.begin(), revB.end());
    saB = SuffixArray(B, true);
    saRevB = SuffixArray(revB, true);
    
    const auto ans = slow::run();
    for (int q = 0; q < Q; ++q) {
      switch (O[q]) {
        case 1: case 2: {
          printf("%d %d\n", ans[q].first, ans[q].second);
        } break;
        case 3: {
          printf("%d\n", ans[q].first);
        } break;
        case 4: {
          puts(ans[q].first ? "yes" : "no");
        } break;
        default: assert(false);
      }
    }
#ifdef LOCAL
const auto brt=brute::run();
assert(brt==ans);
#endif
  }
  return 0;
}

詳細信息

Test #1:

score: 5
Accepted
time: 1ms
memory: 3892kb

input:

1
1000
2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 2 3 1 299 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 2 3 1 2 3 2 3 1 2 3 2 3 1 2 3 2 824 1...

output:

46 1
12 2
46 1
46 1
73 1
100 1
51 1
100 1
100 1
73 1
0
73 1
73 1
73 1
73 1
73 1
19 1
51 1
73 1
73 1
73 1
44 1
51 1
51 1
73 1
22 2
73 1
46 1
0
73 1
yes
57 1
73 1
73 1
73 1
73 1
73 1
73 1
73 1
73 1
51 1
yes
73 1
51 1
73 1
30 1
73 1
73 1
15 1
73 1
73 1
73 1
73 1
46 1
73 1
65 1
0
73 1
12 1
3 1
73 1
73 1...

result:

ok 1911 tokens

Test #2:

score: 5
Accepted
time: 1ms
memory: 3972kb

input:

2
1000
3 2 4 3 2 4 3 2 4 3 2 3 2 4 3 2 4 3 2 4 3 2 3 2 4 3 2 4 3 2 4 406 2 3 2 4 3 2 4 3 3 2 4 3 2 4 3 2 4 3 2 3 2 4 3 2 4 3 2 4 3 2 3 2 98 3 2 4 3 2 4 3 2 3 2 4 3 2 4 3 3 2 4 3 2 4 3 2 4 3 2 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 3 2 4 3 2 4 3 2 4 3 2 3 2 4 3 2 970 3 2 4 3 2 3 2 4 3 2 4 3 3 2 4 3 ...

output:

62 1
93 1
62 3
93 1
62 2
65 1
93 1
93 1
93 1
93 1
93 1
62 2
1
93 1
93 1
62 2
62 2
62 3
42 1
93 1
93 1
62 2
44 1
93 1
62 2
93 1
62 1
93 1
72 1
72 1
62 1
72 1
23 1
72 1
no
62 2
72 1
72 1
72 1
62 3
72 1
72 1
72 1
no
43 1
72 1
62 2
40 1
62 2
8 1
62 2
62 2
0
62 2
62 1
62 1
62 1
62 2
62 2
62 1
62 2
5
62 1...

result:

ok 1915 tokens

Test #3:

score: 5
Accepted
time: 25ms
memory: 11100kb

input:

3
100000
1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 3 1 1 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 3 1 1 3 1 1 3 1 1 3 1 1 3 1 3 1 1...

output:

100 979
100 978
4
100 978
100 977
100 976
100 975
100 974
100 973
100 972
100 971
100 971
100 970
100 969
100 968
100 967
100 966
100 966
100 965
100 965
9
100 964
no
100 964
100 963
100 962
100 961
100 960
100 959
100 958
100 957
100 956
100 955
yes
100 954
100 954
100 953
100 952
100 951
100 950
1...

result:

ok 191356 tokens

Test #4:

score: 5
Accepted
time: 25ms
memory: 11116kb

input:

4
100000
1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 2 3 1 2 3 1 2 3 1 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 1...

output:

100 979
100 978
100 977
100 976
100 975
100 974
100 974
100 973
no
100 972
100 971
100 970
100 970
100 969
100 968
100 967
100 966
no
100 965
100 964
100 963
100 962
100 961
100 960
100 959
100 959
0
100 958
100 957
100 957
100 957
100 956
100 955
100 954
100 953
0
100 952
2
100 951
100 950
100 950
...

result:

ok 191356 tokens

Test #5:

score: 5
Accepted
time: 48ms
memory: 11288kb

input:

5
100000
5 3 3 5 3 3 5 3 3 5 3 3 5 3 5 3 3 5 3 3 5 3 3 5 3 3 5 3 5 3 5 3 3 5 3 3 5 3 3 5 3 3 5 3 5 3 3 5 3 3 5 3 3 5 3 3 5 3 5 3 5 3 3 5 3 3 5 3 3 5 3 3 5 3 5 3 3 5 3 3 5 3 3 5 3 3 5 3 5 3 5 3 3 5 3 3 5 3 3 5 3 3 5 3 5 3 3 5 3 3 5 3 3 5 3 3 5 3 5 3 5 3 3 5 3 3 5 3 3 5 3 3 5 3 5 3 3 5 3 3 5 3 3 5 3 3...

output:

30 3312
30 1774
30 3311
30 2286
0
30 365
30 3310
30 3309
30 3308
30 3307
30 3306
30 3305
30 1856
30 387
30 1033
30 3304
30 1681
30 3303
30 3302
30 3302
30 3301
30 3300
30 845
30 544
30 2719
30 3299
30 1344
30 3298
30 3298
yes
30 3297
30 3296
30 3295
30 473
30 3294
30 3293
30 3292
yes
30 859
30 3291
...

result:

ok 191359 tokens

Test #6:

score: 5
Accepted
time: 63ms
memory: 11056kb

input:

6
100000
2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2 3 2 2...

output:

30 33114
30 12379
30 33114
30 33104
30 23307
30 33094
30 33084
30 1497
no
30 33074
30 13431
30 33064
30 19
30 33054
30 33044
30 4288
30 10728
30 33034
30 6847
30 33024
30 10621
30 33014
30 10308
1
30 11959
30 3935
30 19153
30 33004
30 32994
30 2789
30 32984
30 32984
0
30 21909
30 32984
30 10889
30 3...

result:

ok 191357 tokens

Test #7:

score: 5
Accepted
time: 58ms
memory: 29388kb

input:

7
100000
1 2 1 1 1 1 1 2 1 1 1 4 1 1 1 1 1 1 1 1 1 1 1 2 5 1 1 1 3 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 3 1 2 1 1 3 4 2 2 1 1 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 4 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

1
0
1
4
1
5
1
12
2
7
3
4
4
0
0
1
0
1
3
2
2
2
1
3
0
3
2
3
2
7
0
2
1
1
3
78193
0
5
2
8
7
10
4
4
2
1
0
0
1
1
9
0
1
2
1
7
10
0
0
0
6
0
0
4
7
4
3
1
2
0
0
1
12
2
0
2
5
3
1
0
3
4
7
1
0
9
4
1
5
2
6
23
0
12
6
6
0
2
8
4
2
5
2
1
0
3
10
8
0
2
5
1
2
6
5
9
1
0
0
9
4
3
0
5
0
0
6
4
4
0
1
3
13
0
2
4
1
5
2
0
5
4
2
1
...

result:

ok 100000 tokens

Test #8:

score: 5
Accepted
time: 57ms
memory: 29460kb

input:

8
100000
1 2 1 1 1 1 1 2 1 1 1 4 1 1 1 1 1 1 1 1 1 1 1 2 5 1 1 1 3 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 3 1 2 1 1 3 4 2 2 1 1 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 4 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

0
8
5
2
0
8
4
8
1
2
0
2
0
1
9
1
0
0
0
2
2
0
0
3
0
4
3
1
5
1
5
2
3
11
8
2
3
3
6
2
0
3
0
1
1
1
3
1
0
16
8
0
0
8
13
4
0
3
0
3
0
0
0
0
0
4
7
2
0
2
8
10
0
0
0
4
0
8
2
0
0
7
1
3
5
9
1
0
2
4
0
8
0
3
2
4
1
3
0
0
1
1
5
8
1
0
0
2
4
2
0
3
0
1
3
0
2
0
1
2
15
0
5
2
13
0
3
0
0
0
1
1
3
4
1
1
2
0
4
2
2
14
1
4
5
9
0...

result:

ok 100000 tokens

Test #9:

score: 5
Accepted
time: 113ms
memory: 33240kb

input:

9
100000
1 1 1 1 1 1 1 3 1 1 1 1 2 3 1 2 1 1 1 1 1 1 1 1 2 1 2 1 1 1 3 1 1 1 1 1 2 2 1 1 1 1 1 1 2 2 1 1 1 3 1 1 1 1 2 1 1 1 3 1 1 1 1 2 1 1 1 2 1 1 3 3 1 2 1 1 2 1 1 1 1 1 1 1 1 1 1 3 1 1 2 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 2 1 2 3 2 2 1 3 1 1 1 3 3 1 2 1 1 1 1 1 1 3 1 3 2 1 1 1 1 1 1 1 1 1 2 3 1 1 1...

output:

no
no
no
no
no
no
no
no
no
no
no
yes
no
no
no
no
no
no
no
no
no
no
no
yes
no
no
yes
no
no
no
no
no
no
no
no
no
no
no
no
yes
no
no
yes
yes
no
no
no
no
no
no
no
no
no
no
no
no
no
yes
no
no
no
no
no
no
no
no
no
no
no
yes
no
no
yes
no
no
no
no
no
no
no
no
no
no
no
no
yes
no
no
yes
yes
no
no
no
no
no
no
...

result:

ok 100000 tokens

Test #10:

score: 5
Accepted
time: 99ms
memory: 33252kb

input:

10
100000
1 1 3 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 3 1 1 1 1 2 3 1 2 1 1 1 1 1 1 1 1 2 1 2 1 1 1 3 1 1 1 1 1 2 2 1 1 1 1 1 1 2 2 1 1 1 3 1 1 1 1 2 1 1 1 3 1 1 1 1 2 1 1 1 2 1 1 3 3 1 2 1 1 2 1 1 1 1 1 1 1 1 1 1 3 1 1 2 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 2 1 2 3 2 2 1 3 1 1 1 3 3 1 2 1 ...

output:

no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
yes
yes
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
yes
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
yes
yes
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
no
yes
no
no
no
no
no
no
no
no
no
no
no
...

result:

ok 100000 tokens

Test #11:

score: 0
Time Limit Exceeded

input:

11
100000
1 1 1 1 1 1 1 1 1 1 1 1 1 4 1 1 1 1 1 1 1 1 2 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 4 1 1 1 4 2 1 1 2 1 1 1 1 1 2 1 1 1 4 1 1 1 1 1 1 1 1 1 1 1 2 5 1 1 1 3 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 3 1 2 1 1 3 4 2 2 1 1 1 1 2 2 1 1 1 ...

output:


result:


Test #12:

score: 0
Time Limit Exceeded

input:

12
100000
1 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 4 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 3 3 1 1 1 3 1 1 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 1 3 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 4 1 1 1 1 1 1 1 1 2 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 4 ...

output:


result:


Test #13:

score: 0
Time Limit Exceeded

input:

13
100000
1 1 1 1 1 1 4 1 1 1 4 2 1 1 2 1 1 1 1 1 2 1 1 1 4 1 1 1 1 1 1 1 1 1 1 1 2 5 1 1 1 3 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 3 1 2 1 1 3 4 2 2 1 1 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 4 1 1 3 1 1 1 1 ...

output:


result:


Test #14:

score: 0
Time Limit Exceeded

input:

14
100000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 3 3 1 1 1 3 1 1 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 1 3 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 4 1 1 1 1 1 1 1 1 2 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 4 1 1 1 4 2 1 1 2 1 1 1 1 1 2 1 1 1 4 1 1 1 1 1 1 1 1 1 1 1 2 5 1 1 ...

output:


result:


Test #15:

score: 0
Time Limit Exceeded

input:

15
100000
5 1 1 1 3 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 2 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 3 1 2 1 1 3 4 2 2 1 1 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 3 1 1 1 1 4 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 ...

output:


result:


Test #16:

score: 0
Time Limit Exceeded

input:

16
100000
1 1 1 1 1 1 1 3 3 1 1 1 3 1 1 1 1 1 1 1 1 2 1 1 1 1 1 2 1 1 1 1 1 1 1 3 1 1 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 4 1 1 1 1 1 1 1 1 2 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 4 1 1 1 4 2 1 1 2 1 1 1 1 1 2 1 1 1 4 1 1 1 1 1 1 1 1 1 1 1 2 5 1 1 1 3 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 2 1 1 1 1 ...

output:


result:


Test #17:

score: 0
Time Limit Exceeded

input:

17
100000
5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 2 1 5 2 1 5 3 2 5 1 ...

output:


result:


Test #18:

score: 0
Time Limit Exceeded

input:

18
100000
4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 3 2 3 4 5 4 2 2 1 1 ...

output:


result:


Test #19:

score: 0
Time Limit Exceeded

input:

19
100000
1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 5 5 1 4 5 1 5 2 4 3 ...

output:


result:


Test #20:

score: 0
Time Limit Exceeded

input:

20
100000
2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 5 5 3 5 2 2 1 3 1 3 ...

output:


result: