問題

E – Prefix Equality

プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

atcoder.jp

記録

• 2022/7/26 解法わからず。

解法

• \(A = (12, 19, 22, 19, 23) \) を登場順に \((1, 2, 3, 2, 4) \) に変換する。
• \(A\) について何種類の数があるかを順番に数える（1）。
• \(B\) を \(A\) の変換ルールに基づいて変換する。
• \(B\) について何種類の数があるかを順番に数える（2）。
• \(B\) について最大値を順番に管理する（3）。
• （1）,（2）,（3）が同じならYes。

コード例

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<ll, ll>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// using mint = modint998244353;
// using mint = modint1000000007;
// const int mod = 1000000007;
// const ll INF = 1LL << 62;
const int INF = 1001001001;

int main() {
  int N;
  cin >> N;
  
  vector<int> a(N);
  vector<int> cntA(N);
  int cnt = 1;
  map<int, int> mp;
  rep(i, N) {
    int A;
    cin >> A;
    if (mp[A] != 0) {
      a[i] = mp[A];
      cntA[i] = cnt - 1;
    } else {
      mp[A] = cnt;
      a[i] = cnt;
      cntA[i] = cnt;
      cnt++;
    }
  }

  vector<int> b(N);
  vector<int> cntB(N);
  vector<int> maxB(N);
  set<int> stB;
  int mxB = 0;
  rep(i, N) {
    int B;
    cin >> B;
    if (mp[B] == 0) {
      b[i] = INF;
    } else {
      b[i] = mp[B];
    }
    stB.insert(b[i]);
    cntB[i] = stB.size();
    mxB = max(mxB, b[i]);
    maxB[i] = mxB;
  }
  
  int Q;
  cin >> Q;
  rep(i, Q) {
    int x, y;
    cin >> x >> y;
    x--;
    y--;
    int cA = cntA[x];
    int cB = cntB[y];
    int mB = maxB[y];
    if (cA == cB && cB == mB) {
      cout << "Yes" << endl;
    } else {
      cout << "No" << endl;
    }
  }
  return 0;
}