#1190526 (C++17) No.3748 Three Pruning Order

• 問題: No.3748 Three Pruning Order
• ユーザー: 👑 potato167
• 提出日時: 2026-09-25 23:27:43
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 879 ms / 2,000 ms
• コード長: 9,675 bytes
• コンパイル時間: 1,485 ms
• コンパイル使用メモリ: 237,252 KB
• 実行使用メモリ: 94,396 KB
• 最終ジャッジ日時: 2026-09-25 23:28:21
• 合計ジャッジ時間: 27,223 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge3_0

ファイルパターン	結果
sample	AC * 1
other	AC * 42

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll ILL=2167167167167167167;
const int INF=2100000000;
#define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
#define all(p) p.begin(),p.end()
template<class T> using pq_ = priority_queue<T, vector<T>, greater<T>>;
template<class T> int LB(vector<T> &v,T a){return lower_bound(v.begin(),v.end(),a)-v.begin();}
template<class T> int UB(vector<T> &v,T a){return upper_bound(v.begin(),v.end(),a)-v.begin();}
template<class T> bool chmin(T &a,T b){if(b<a){a=b;return 1;}else return 0;}
template<class T> bool chmax(T &a,T b){if(a<b){a=b;return 1;}else return 0;}
template<class T> void So(vector<T> &v) {sort(v.begin(),v.end());}
template<class T> void Sore(vector<T> &v) {sort(v.begin(),v.end(),[](T x,T y){return x>y;});}
bool yneos(bool a,bool upp=false){if(a){cout<<(upp?"YES\n":"Yes\n");}else{cout<<(upp?"NO\n":"No\n");}return a;}
template<class T> void vec_out(vector<T> &p,int ty=0){
    if(ty==2){cout<<'{';for(int i=0;i<(int)p.size();i++){if(i){cout<<",";}cout<<'"'<<p[i]<<'"';}cout<<"}\n";}
    else{if(ty==1){cout<<p.size()<<"\n";}for(int i=0;i<(int)(p.size());i++){if(i) cout<<" ";cout<<p[i];}cout<<"\n";}}
template<class T> T vec_min(vector<T> &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmin(ans,x);return ans;}
template<class T> T vec_max(vector<T> &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmax(ans,x);return ans;}
template<class T> T vec_sum(vector<T> &a){T ans=T(0);for(auto &x:a) ans+=x;return ans;}
int pop_count(long long a){int res=0;while(a){res+=(int)(a&1),a>>=1;}return res;}
template<class T> T square(T a){return a * a;}

#line 2 "data-structure-2d/dynamic-binary-indexed-tree-2d.hpp"

#line 2 "data-structure/dynamic-binary-indexed-tree.hpp"

#line 2 "data-structure/hash-map-variable-length.hpp"

template <typename Key, typename Val>
struct HashMap {
  using u32 = uint32_t;
  using u64 = uint64_t;

  u32 cap, s;
  vector<Key> keys;
  vector<Val> vals;
  vector<bool> flag;
  u64 r;
  u32 shift;
  Val DefaultValue;

  static u64 rng() {
    u64 m = chrono::duration_cast<chrono::nanoseconds>(
                chrono::high_resolution_clock::now().time_since_epoch())
                .count();
    m ^= m >> 16;
    m ^= m << 32;
    return m;
  }

  void reallocate() {
    cap <<= 1;
    vector<Key> k(cap);
    vector<Val> v(cap);
    vector<bool> f(cap);
    u32 sh = shift - 1;
    for (int i = 0; i < (int)flag.size(); i++) {
      if (flag[i]) {
        u32 hash = (u64(keys[i]) * r) >> sh;
        while (f[hash]) hash = (hash + 1) & (cap - 1);
        k[hash] = keys[i];
        v[hash] = vals[i];
        f[hash] = 1;
      }
    }
    keys.swap(k);
    vals.swap(v);
    flag.swap(f);
    --shift;
  }

  explicit HashMap()
      : cap(8),
        s(0),
        keys(cap),
        vals(cap),
        flag(cap),
        r(rng()),
        shift(64 - __lg(cap)),
        DefaultValue(Val()) {}

  Val& operator[](const Key& i) {
    u32 hash = (u64(i) * r) >> shift;
    while (true) {
      if (!flag[hash]) {
        if (s + s / 4 >= cap) {
          reallocate();
          return (*this)[i];
        }
        keys[hash] = i;
        flag[hash] = 1;
        ++s;
        return vals[hash] = DefaultValue;
      }
      if (keys[hash] == i) return vals[hash];
      hash = (hash + 1) & (cap - 1);
    }
  }

  // exist -> return pointer of Val
  // not exist -> return nullptr
  const Val* find(const Key& i) const {
    u32 hash = (u64(i) * r) >> shift;
    while (true) {
      if (!flag[hash]) return nullptr;
      if (keys[hash] == i) return &(vals[hash]);
      hash = (hash + 1) & (cap - 1);
    }
  }

  // return vector< pair<const Key&, val& > >
  vector<pair<Key, Val>> enumerate() const {
    vector<pair<Key, Val>> ret;
    for (u32 i = 0; i < cap; ++i)
      if (flag[i]) ret.emplace_back(keys[i], vals[i]);
    return ret;
  }

  int size() const { return s; }

  // set default_value
  void set_default(const Val& val) { DefaultValue = val; }
};

/**
 * @brief Hash Map(可変長版)
 * @docs docs/data-structure/hash-map.md
 */
#line 4 "data-structure/dynamic-binary-indexed-tree.hpp"

template <typename S, typename T>
struct DynamicFenwickTree {
  S N;
  HashMap<S, T> data;
  explicit DynamicFenwickTree() = default;
  explicit DynamicFenwickTree(S size) { N = size + 1; }

  void add(S k, T x) {
    for (++k; k < N; k += k & -k) data[k] += x;
  }

  // [0, k)
  T sum(S k) const {
    if (k < 0) return 0;
    T ret = T();
    for (; k > 0; k -= k & -k) {
      const T* p = data.find(k);
      ret += p ? *p : T();
    }
    return ret;
  }

  // [a, b)
  T sum(S a, S b) const { return sum(b) - sum(a); }

  T operator[](S k) const { return sum(k + 1) - sum(k); }

  S lower_bound(T w) {
    if (w <= 0) return 0;
    S x = 0;
    for (S k = 1 << __lg(N); k; k >>= 1) {
      if (x + k <= N - 1 && data[x + k] < w) {
        w -= data[x + k];
        x += k;
      }
    }
    return x;
  }
};

/**
 * @brief 動的Binary Indexed Tree
 * @docs docs/data-structure/dynamic-binary-indexed-tree.md
 */
#line 4 "data-structure-2d/dynamic-binary-indexed-tree-2d.hpp"

template <typename T>
struct DynamicFenwickTree2D {
  using BIT = DynamicFenwickTree<int, T>;
  int N, M;
  vector<BIT*> bit;
  DynamicFenwickTree2D() = default;
  DynamicFenwickTree2D(int n, int m) : N(n + 1), M(m) {
    for (int _ = 0; _ < N; ++_) bit.push_back(new BIT(M));
  }

  void add(int i, int j, const T& x) {
    for (++i; i < N; i += i & -i) (*bit[i]).add(j, x);
  }

  // i = [0, n), j = [0, m)
  T sum(int n, int m) const {
    if (n < 0 || m < 0) return T();
    T ret = T();
    for (; n; n -= n & -n) ret += (*bit[n]).sum(m);
    return ret;
  }

  // i = [nl, nr), j = [ml, mr)
  T sum(int nl, int ml, int nr, int mr) const {
    T ret = T();
    while (nl != nr) {
      if (nl < nr) {
        ret += (*bit[nr]).sum(ml, mr);
        nr -= nr & -nr;
      } else {
        ret -= (*bit[nl]).sum(ml, mr);
        nl -= nl & -nl;
      }
    }
    return ret;
  }
};

/*
 * @brief 動的二次元Binary Indexed Tree
 */

#include <atcoder/modint>
using mint = atcoder::modint;
#include <atcoder/segtree>
int op(int a, int b) {
  return a + b;
}
int e() {
  return 0;
}

bool f(int x) {
  return x == 0;
}

void solve();
// DEAR MYSTERIES / TOMOO
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    cin >> t;
    rep(i, 0, t) solve();
}

void solve(){
  int N, M;
  cin >> N >> M;
  mint ::set_mod(M);
  vector<int> P(N), Q(N), R(N);
  rep(i, 0, N) cin >> P[i], P[i]--;
  rep(i, 0, N) cin >> Q[i], Q[i]--;
  rep(i, 0, N) cin >> R[i], R[i]--;
  reverse(all(P));
  reverse(all(Q));
  reverse(all(R));
  {
    vector<int> invP(N);
    rep(i, 0, N) invP[P[i]] = i;
    rep(i, 0, N) {
      P[i] = invP[P[i]];
      Q[i] = invP[Q[i]];
      R[i] = invP[R[i]];
    }
  }
  mint ans = 1;
  vector A = {Q, R};
  vector invA(2, vector<int>(N));
  rep(i, 0, 2) rep(j, 0, N) invA[i][A[i][j]] = j;
  atcoder::segtree<int, op, e> em(vector<int>(N, 1));
  vector seg(2, em);
  vector<int> use(N);
  DynamicFenwickTree2D<int> seg2(N, N);
  rep(i, 0, N) seg2.add(invA[0][i], invA[1][i], 1);
  // vec_out(A[0]);
  // vec_out(A[1]);
  for (int i = N - 1; i > 0; i--) {
    if (use[i]) continue;
    int pare = -1;
    int d = 0;
    rep(j, 0, 2) {
      int l = seg[j].max_right<f>(0);
      if (A[j][l] == i) {
        int r = seg[j].max_right<f>(l + 1);
        // cout << j << " " << l << " " << r;
        r = A[j][r];
        // cout << " " << r << endl;
        if (pare == -1) pare = r, d = (1 << j);
        else if (pare != r) pare = -2;
        else d = 3;
      }
    }
    // cout << ans.val() << " " << d << " " << pare << endl;
    if (pare == -2) {
      ans = 0;
      break;
    }
    if (pare == -1) {
      ans *= seg2.sum(invA[0][i], invA[1][i]);
    }
    else {
      if (d != 3) {
        d--;
        d = 1 - d;
        if (invA[d][pare] > invA[d][i]) {
          ans = 0;
        }
      }
    }
    rep(j, 0, 2) seg[j].set(invA[j][i], 0);
    seg2.add(invA[0][i], invA[1][i], -1);
  }
  cout << ans.val() << "\n";
}

/*
 * 3 つの順列は reverse する
 * 3 つの順列が与えられるので、
 * 良い木が何通りあるのか？
 * 良い木とは、P[0] を根とした時、
 * 任意の辺について、invP[pare] < invP[chil] が成り立つ
 * これが、P, Q, R 全てで成り立つということ
 * 木という条件を忘れて、
 * 任意の i について、P[i] は P[0], ... , P[i - 1] のいずれかと辺を結んでいるとする？
 * P[N - 1], ... , P[1] の順に葉を考える？
 * 根から考えるか？
 * P[0] - P[1] は必ず存在する
 * (a, b) = (P[0], P[1]) として、
 * a の方が先に出てくる 順列が存在した時、
 * その時の b の行き先は一意に存在するため、
 * b より前に出てくるものは b とは結ばれない
 * P[N - 1] が結ばれる頂点は、Q, R でも先に出ている
 * もしくは P[N - 1] が根でなければならない
 * ある辺について、P[0], Q[0], R[0] どれも外側
 * ある辺について、同じでないものがあったとき、
 * それは別向きのやつだけあれになっている
 * P0, a1, a2, ... , al, z
 * Q0, b1, ... , bk, z
 * R0, c1, ... , z
 * みたいな感じになっている
 * z = P0 のこともある
 * それ以外は全て同じ向きになる
 * 葉を見る。
 * もし、それが根になっていないならば、Q, R でもそれより前のものを取ることになる
 * ↑は長方形内にある点の位置になる
 * もし根になっているなら
 * それとつながっている辺は一意に定まる
 *
 *
 */