[ARC133] B - Dividing Subsequence

[Q] https://atcoder.jp/contests/arc133/tasks/arc133_b

1. P->Qへ、indexマッピングをする。
2. Pを 0~N-1 まで走査。セグ木する。
今見てるPが、どのQをとれるかを全部みる。これはindexがお尻にあるやつから確認。
セグの値には、とったQが、部分列の何要素目にあたるかをマッピング。
3. セグの最大値が解答。

N=4
P[]=3 1 4 2
Q[]=4 2 1 3

1. P->Q のマッピング
Q について、val->indexへのマッピングをする。
pos[4] = 0
pos[2] = 1
pos[1] = 2
pos[3] = 3

P について、Q への遷移先をマッピングする。
G[0] = {3} // P(3) -> Q(3)
G[1] = {0,1,2,3} // P(1) -> Q(1,2,3,4)
G[2] = {0} // P(4) -> Q(4)
G[3] = {0,1} // P(2) -> Q(2,4)

2. Pを走査。
seg[] = 0,0,0,0

1) G[0] = {3}
index3より前(index2以下)でとれる最大値を求める。
それが、これからindex3を採用する時点での部分列の個数。
seg[3] には、seg[0,3) + 1 が入る。
seg[0,3) = 0 なので、seg[3] = 1 // 0+1
seg[] = 0,0,0,1
              ~

2) G[1] = {0,1,2,3}
indexのおしりから処理していく。
seg[0,3) = 0なので、seg[3] = 1
seg[0,2) = 0なので、seg[2] = 1
seg[0,1) = 0 なので、seg[1] = 1
seg[0,0)について。Q[0]番目を採用したときに何個目か、は必ず1個目になるので、seg[0] = 1
seg[] = 1,1,1,1
        ~ ~ ~ ~

3) G[2] = {0}
seg[0,0)について。Q[0]番目を採用したときに何個目か、は必ず1個目になるので、seg[0] = 1
seg[] = 1,1,1,1
        ~

4) G[3] = {0,1}
indexのおしりから処理していく。
seg[0,1) = 1 なので、seg[1] = 2
seg[0,0) は、seg[0] = 1 を固定入れ。
seg[] = 1,2,1,1
          ~

最大値の 2 が解答。

実装

ll N;
ll P[200020];
ll Q[200020];
vector<ll> G[200020];
ll pos[200020];

int main() {
 cincout();

 cin >> N;
 RangeMax Z;
 Z.init(N + 1);
 Z.update(0, 0);
 rep(i, N) cin >> P[i];
 rep(i, N) {
   cin >> Q[i];
   pos[Q[i]] = i;
 }

 rep(i, N) {
   ll p = P[i];
   ll add = P[i];
   while (p <= N) {
     G[i].push_back(pos[p]);
     p += add;
   }
   sort(all(G[i]));
 }

 rep(i, N) {
   ll sz = G[i].size();
   for (ll j = sz - 1; j >= 0; --j) {
     ll k = G[i][j];
     if (k == 0) {
       Z.update(0, 1);
       continue;
     }
     ll high = Z.query(0, k);
     Z.update(k, high + 1);
   }
 }
 cout << Z.query(0, N) << endl;
}

https://atcoder.jp/contests/arc133/submissions/28699353