予鈴

アウトプットとメモ書きの中間みたいな記事がたくさん出ます。

E - Prefix Equality

11月一度もブログ投稿してないけど、問題自他はこまめに解いてました。
思い出すシリーズです。

問題

長さ Nの2つの数列 A,Bが与えられる。
Q個のクエリに答えよ。

 query_i : A の先頭 x_i個の値の集合とB の先頭 y_i個の値の集合が等しいかどうかを答えよ
atcoder.jp

解法

  • クエリにオンラインで答える必要は無いので、まずはクエリの内容を x_iの昇順に並び替える。これによって、 Aの状態をクエリごとに求めずにすむ。
  • さて、ここからクエリに答える具体的な方法を考察してみる。まずは簡単なところから考えよう。それぞれの値の集合をS_{A_{x_i}},  S_{B_{y_i}}とする。もし値の集合が等しいのであれば、明らかにsize(S_{A_{x_i}}) == size(S_{B_{y_i}})が成り立つ。
  • もちろんすべてのクエリに対して集合を計算するのは間に合わないので、累積和を用いて、 B_i番目の要素までの集合のサイズを前計算しておけば良い
  • さて、ここからが重要になる。集合のサイズが等しくても、集合の要素が等しいことにはならない。もう1つ条件を加えて、集合の要素も判定できるように工夫する。考えるべき点は、 S_{A_{x_i}}内の要素が、 B 内でどこでは初めて現れるかがである。
  • 具体例を用いる。 x_i, y_iというクエリにおいて、S_{A_{x_i}}の要素がすべて B_{y_i}までに現れていれば良い。余計なのもが含まれてはならないが、これは先述した集合のサイズの比較で判別できる。
  • ここまで考察できれば、答えは近い。Aの集合の要素が B_{y_i}までに現れているかどうかの判定は、 S_{A_{x_i}}に含まれている要素のうち、Bの中で最も後ろに含まれている添字を更新して管理すればよい。
  • 言い換えると、集合のサイズが等しい かつ Aの集合の要素の中でB中に最も後に現れる添字を管理することで、集合の要素を判定することができる
  • 文字にすると微妙なので具体例も載せよう。 S_{A_{x_i}} =  {1,2,3,4} の時,  B =  2,2,1,4,3,3 とすれば、5番目の添字を覚えて置けば良い。

提出コード

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>

using namespace std;
using Int = long long;

int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    cin >> N ;
    
    vector<int>A(N), B(N);
    
    for(auto& a : A)
        cin >> a;
    
    for(auto& b : B)
        cin >> b;
    
    vector<tuple<int,int,int>>query;
    
    int Q; cin >> Q;
    
    for(int i = 0; i < Q; ++i)
    {
        int x, y;
        cin >> x >> y;
        query.emplace_back(--x,--y, i);
    }
    
    sort(begin(query),end(query));
    
    vector<bool>ans(Q, false);
    
    int cx = 0;
    set<int>S, Sb;
    
    vector<int>bSetSizeCnt(N, 0);
    map<int,int>bKeyIdx;
    
    for(int i = 0; i < N; ++i)
    {
        // 各要素で最初に現れる位置を記録する
        if(bKeyIdx.find(B[i]) == bKeyIdx.end())
            bKeyIdx[B[i]] = i;
         // Bの集合のサイズを記録する 
        if(i)
            bSetSizeCnt[i] += bSetSizeCnt[i - 1];
        
        if(Sb.find(B[i]) == Sb.end())
        {
            bSetSizeCnt[i] += 1;
        }
        
        Sb.insert(B[i]);      
    }
  
    int aIdxMaxi = -1;
    for(const auto&[ x, y, i] : query)
    {
        while(cx <= x && cx < N)
        {
            S.insert(A[cx]);
            // Aにだけある場合はこれ以降すべてのクエリがNo
            if(bKeyIdx.find(A[cx]) == bKeyIdx.end())
                aIdxMaxi = N + 1;
    
            aIdxMaxi = max(aIdxMaxi, bKeyIdx[A[cx]]);
            ++cx;
        }
        if(S.size() == bSetSizeCnt[y])
        {
            if(aIdxMaxi <= y)
                ans[i] = true;
        }
    }
    
    for(const auto b : ans)
        cout << ( b ? "Yes\n" : "No\n");
    
}