#1198054 (C++23(gcc16)) No.3782 Synchronized Subsequences

• 問題: No.3782 Synchronized Subsequences
• ユーザー: C
• 提出日時: 2026-11-11 01:47:47
• 言語: C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 109 ms / 3,000 ms
• コード長: 6,027 bytes
• コンパイル時間: 9,107 ms
• コンパイル使用メモリ: 393,840 KB
• 実行使用メモリ: 12,416 KB
• 最終ジャッジ日時: 2026-11-11 01:48:10
• 合計ジャッジ時間: 10,824 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

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

ソースコード

#include <bits/stdc++.h>
#include <atcoder/all>
#include <boost/polygon/point_data.hpp>
#include <boost/polygon/voronoi.hpp>
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(x) begin(x),end(x)
#define sz(x) (int)(x).size()
using namespace std;
using namespace atcoder;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
using vll=vector<ll>;
using vvll=vector<vll>;
using vi=vector<int>;
using vvi=vector<vi>;
using pll=pair<ll,ll>;
using pi=pair<int,int>;

// using mint=modint998244353;
using mint=modint1000000007;
// using mint2=static_modint<2>;

// using BoostPoint=boost::polygon::point_data<int>;
// using Voronoi=boost::polygon::voronoi_diagram<double>;

// using mint=LazyMontgomeryModInt<998244353>;
using vm=vector<mint>;
using vvm=vector<vm>;

#line 2 "data-structure/w-ary-tree.hpp"

namespace w_ary_tree_impl {
using u64 = uint64_t;
static constexpr unsigned int lgW = 6;
static constexpr unsigned int W = 1u << lgW;
static constexpr int inf = 1 << 30;
inline int ctz(u64 n) { return n ? __builtin_ctzll(n) : -1; }
inline int clz(u64 n) { return n ? 63 - __builtin_clzll(n) : -1; }

template <int LOG, class D = void>
struct w_ary_tree_node {
  u64 map;
  int mn, mx;
  static constexpr int shift = (LOG - 1) * lgW;
  array<w_ary_tree_node<LOG - 1>, W> chd;
  inline int mask(u64 key) const { return key & ((1 << shift) - 1); }

  w_ary_tree_node() : map(0), mn(inf), mx(-1) {}
  void insert(int key) {
    mn = std::min(mn, key), mx = std::max(mx, key);
    int pos = key >> shift;
    map |= 1ULL << pos;
    chd[pos].insert(mask(key));
  }
  void erase(int key) {
    int pos = key >> shift;
    chd[pos].erase(mask(key));
    if (chd[pos].map == 0) map &= ~(1ULL << pos);
    if (mn == key) {
      if (mx == key) {
        mn = inf, mx = -1;
      } else {
        int p = ctz(map);
        mn = (p << shift) + chd[p].min();
      }
    } else if (mx == key) {
      int p = clz(map);
      mx = (p << shift) + chd[p].max();
    }
  }
  bool contain(int key) const {
    int pos = key >> shift;
    return chd[pos].contain(mask(key));
  }
  inline int min() const { return mn == inf ? -1 : mn; }
  inline int max() const { return mx; }
  int find_next(int key) const {
    if (key <= min()) return min();
    int pos = key >> shift;
    if (((map >> pos) & 1) && mask(key) <= chd[pos].max()) {
      return (pos << shift) + chd[pos].find_next(mask(key));
    }
    int nxt = ctz(map & ~((1ULL << (pos + 1)) - 1));
    if (pos == 63 || nxt == -1) return -1;
    return (nxt << shift) + chd[nxt].min();
  }
  int find_prev(int key) const {
    if (max() < key) return max();
    int pos = key >> shift;
    if (((map >> pos) & 1) && chd[pos].min() < mask(key)) {
      return (pos << shift) + chd[pos].find_prev(mask(key));
    }
    int nxt = clz(map & ((1ULL << pos) - 1ULL));
    if (nxt == -1) return -1;
    return (nxt << shift) + chd[nxt].max();
  }
};

template <int LOG>
struct w_ary_tree_node<LOG, typename std::enable_if<LOG == 1>::type> {
  u64 map;
  w_ary_tree_node() : map(0) {}
  void insert(int key) { map |= 1ULL << key; }
  void erase(int key) { map &= ~(1ULL << key); }
  bool contain(int key) const { return (map >> key) & 1; }
  int min() const { return ctz(map); }
  int max() const { return clz(map); }
  int find_next(int key) const { return ctz(map & ~((1ULL << key) - 1)); }
  int find_prev(int key) const { return clz(map & ((1ULL << key) - 1)); }
};

}  // namespace w_ary_tree_impl

template <int LOG = 4>
using w_ary_tree = w_ary_tree_impl::w_ary_tree_node<LOG>;

/**
 * @brief 64-ary tree
 */

//online insertion-only prefix max (ならしO(1))
struct frontier{
	w_ary_tree<2>S;
	vi V;
	frontier(int n):V(n+1){}
	int query(int r){
		int p=S.find_prev(r);
		return p==-1?0:V[p];
	}
	void insert(int x,int v){
		if(v==0)return;
		int p=S.find_prev(x);
		if(p!=-1&&V[p]>=v)return;
		int s=S.find_next(x);
		while(s!=-1&&V[s]<=v){
			S.erase(s);
			s=S.find_next(x);
		}
		S.insert(x);
		V[x]=v;
	}
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	/**
	 * ならしO(N^2)
	 * 解説とほぼ同じです
	 * でもdynamic prefix maxの部分（普通segtreeを使いますが）は**挿入のみ**なので（van Emde Boas treeを使えば）ならし計算量O(QloglogQ)で処理できます（Qは挿入、クエリ回数）
	 * さらにここN<=1000ので、van Emde Boas treeより　64-ary tree（bit高速化）を使えばO(Q)に落とせます
	 */
	int T;
	cin>>T;
	while(T--){
		int N;
		cin>>N;
		vi P(N+1),Q(N+1);
		rep(i,1,N+1)cin>>P[i];
		rep(i,1,N+1)cin>>Q[i];
		vector<frontier>Cminus(N+1,frontier(N)),Cplus(N+1,frontier(N));
		vi l(N+1),h(N+1);
		int ans=0;
		/**
		 * dp[i,j] = 1 + max(max_{x<i;P_x<P_i;y<j;Q_y<Q_j}dp[x,y],max_{x<i;P_x>P_i;y<j;Q_y>Q_j}dp[x,y])
		 * max_{x<i;P_x<P_i;y<j;Q_y<Q_j}dp[x,y]に注目する
		 * max_{x<i;P_x<P_i;y<j;Q_y<Q_j}dp[x,y]　= max{y<j;Q_y<Q_j} (max_{x<i;P_x<P_i} dp[x,y])なので
		 * l[y]を　max_{x<i;P_x<P_i} dp[x,y]　にすれば
		 * max_{x<i;P_x<P_i;y<j;Q_y<Q_j}dp[x,y]　=  max{y<j;Q_y<Q_j} l[y]
		 * 
		 * つまり、max_{x<i;P_x<P_i} dp[x,y]　は一つの online insertion-only prefix max　（iを上昇順に処理すれば、x<iは確実なので、yを固定した時これは単なる max_{P_x<P_i} dp[x,y]）
		 * max{y<j;Q_y<Q_j} l[y] はもう一つの online insertion-only prefix max　（同様に、iを固定した時、jを上昇順に処理すれば、y<jは確実なので、これは単なる max{Q_y<Q_j} l[y]）
		 */
		rep(i,1,N+1){
			rep(y,1,N+1){
				//Cminus[y] = {(P[x],dp[x,y]) : x < i}
				l[y]=Cminus[y].query(P[i]);
				h[y]=Cplus[y].query(N+1-P[i]);
			}
			frontier Rminus(N),Rplus(N);
			rep(j,1,N+1){
				int dp=1+max(Rminus.query(Q[j]),Rplus.query(N+1-Q[j]));
				ans=max(ans,dp);
				//Rminus = {(Q_y,l[y]) : y < j}
				Rminus.insert(Q[j],l[j]);
				Rplus.insert(N+1-Q[j],h[j]);
				Cminus[j].insert(P[i],dp);
				Cplus[j].insert(N+1-P[i],dp);
			}
		}
		cout<<ans<<'\n';
	}
}