Official
D - LOWER Editorial by MMNMM
全体に対する操作を別に考え、個別の文字に対する操作を管理するときに同時に「最後に変更されたのはいつか」を管理することでこの問題を解くことができます。
全体に対する操作も「最後の操作がいつか」と「最後の操作が何か」を持っていれば十分です。
最終的に、個別の最終変更が全体の最終変更より後の場合はそのまま、そうでないなら全体の最後の操作を適用したものを出力すればよいです。
計算量は \(O(N+Q)\) 時間です。 実装例は以下のようになります。
#include <string>
#include <iostream>
#include <vector>
#include <utility>
#include <optional>
int main() {
using namespace std;
int N;
string S;
cin >> N >> S;
vector<pair<int, char>> status(N); // 個別の操作 (最終変更時間, 現在の文字)
for (int i = 0; i < N; ++i)
status[i] = {0, S[i]}; // はじめは時刻 0
int Q;
cin >> Q;
optional<pair<int, int>> fill = nullopt; // 全体に対する操作 (最終変更時間, 最後の変更のタイプ)
for (int i = 0; i < Q; ++i) { // 時刻 i の操作
int t, x;
char c;
cin >> t >> x >> c;
if (t == 1) // 個別の操作
status[x - 1] = {i, c};
else // 全体の操作
fill = {i, t};
}
for (const auto&[time, c] : status)
if (!fill || time >= fill->first) // 全体に対する操作がないか、最終更新時間がそれより後なら
cout << c; // そのまま出力
else if (fill->second == 2) // そうでなければ全体操作の種類に応じて
cout << static_cast<char>(tolower(c)); // 小文字に
else
cout << static_cast<char>(toupper(c)); // 大文字に
cout << endl;
return 0;
}
posted:
last update: