E - Prefix Equality
11月一度もブログ投稿してないけど、問題自他はこまめに解いてました。
思い出すシリーズです。
解法
- クエリにオンラインで答える必要は無いので、まずはクエリの内容をの昇順に並び替える。これによって、の状態をクエリごとに求めずにすむ。
- さて、ここからクエリに答える具体的な方法を考察してみる。まずは簡単なところから考えよう。それぞれの値の集合を, とする。もし値の集合が等しいのであれば、明らかにが成り立つ。
- もちろんすべてのクエリに対して集合を計算するのは間に合わないので、累積和を用いて、番目の要素までの集合のサイズを前計算しておけば良い
- さて、ここからが重要になる。集合のサイズが等しくても、集合の要素が等しいことにはならない。もう1つ条件を加えて、集合の要素も判定できるように工夫する。考えるべき点は、内の要素が、 内でどこでは初めて現れるかがである。
- 具体例を用いる。というクエリにおいて、の要素がすべてまでに現れていれば良い。余計なのもが含まれてはならないが、これは先述した集合のサイズの比較で判別できる。
- ここまで考察できれば、答えは近い。Aの集合の要素がまでに現れているかどうかの判定は、に含まれている要素のうち、の中で最も後ろに含まれている添字を更新して管理すればよい。
- 言い換えると、集合のサイズが等しい かつ Aの集合の要素の中でB中に最も後に現れる添字を管理することで、集合の要素を判定することができる
- 文字にすると微妙なので具体例も載せよう。 = の時, = とすれば、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"); }