#include <bits/stdc++.h>
#define se second
#define fs first
#define mp make_pair
#define pb push_back
#define ll long long
#define ii pair<ll,ll>
#define ld long double
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
using namespace std;
mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }
const int N = 1e6 + 7;
const ll Mod = 1e9 + 9;
const int szBL = 916;
const ll INF = 1e9;
const int BASE = 31;
int n, Q;
string T;
ll pw[N], hs[30][N];
struct Segment_Tree {
int Range;
ll st[N << 2], lz[N << 2];
void init (int n) {
Range = n;
rep (i, 1, n << 2) lz[i] = -1;
}
void build (int id, int l, int r) {
if (l == r) {
st[id] = T[l - 1] - 'A';
return;
}
int mid = l + r >> 1;
build (id << 1, l, mid);
build (id << 1| 1, mid + 1, r);
st[id] = (st[id << 1] * pw[r - mid] % Mod + st[id << 1 | 1]) % Mod;
}
void down (int id, int l, int r) {
int mid = l + r >> 1;
if (lz[id] != -1) {
st[id << 1] = hs[lz[id]][mid - l + 1];
st[id << 1 | 1] = hs[lz[id]][r - mid];
lz[id << 1] = lz[id];
lz[id << 1 | 1] = lz[id];
}
lz[id] = -1;
}
void update (int id, int l, int r, int u, int v, int C) {
if (l > v || r < u) return;
if (l >= u && r <= v) {
st[id] = hs[C - 'A'][r - l + 1];
lz[id] = C - 'A';
return;
}
int mid = l + r >> 1;
down (id, l, r);
update (id << 1, l, mid, u, v, C);
update (id << 1 | 1, mid + 1, r, u, v, C);
st[id] = (st[id << 1] * pw[r - mid] % Mod + st[id << 1 | 1]) % Mod;
}
void update (int u, int v, int C) {
return update (1, 1, Range, u, v, C);
}
}ST;
void initHS () {
pw[0] = 1;
rep (i, 1, n * 2) pw[i] = pw[i - 1] * BASE;
vector<char> c = {'J', 'O', 'I'};
iter (id, c)
rep (i, 1, n)
hs[id - 'A'][i] = (hs[id - 'A'][i - 1] * BASE % Mod + id - 'A') % Mod;
}
ll getHS (string S) {
ll res = 0;
rep (i, 1, n) res = (res * BASE % Mod + S[i - 1] - 'A') % Mod;
return res;
}
void solution () {
cin >> n;
string A, B, C;
cin >> A >> B >> C;
vector<char> c = {'J', 'O', 'I'};
set<string> S = {A, B, C};
auto Merge = [] (string A, string B) {
static string res;
res.resize(SZ(A));
rep (i, 0, SZ(A) - 1)
if (A[i] == B[i]) res[i] = A[i];
else {
static set<char> c;
c = {'J', 'O', 'I'};
c.erase(A[i]);
c.erase(B[i]);
res[i] = *c.begin();
}
return res;
};
int prevsz = SZ(S);
while (1) {
static set<string> newStr;
newStr.clear();
iter (&id1, S)
iter( &id2, S) newStr.insert(Merge(id1, id2));
iter (&id, newStr) S.insert(id);
if (SZ(S) == prevsz) break;
else prevsz = SZ(S);
}
set<ll> vecHS;
initHS();
iter (&id, S) vecHS.insert(getHS(id));
cin >> Q;
cin >> T;
ST.init(n);
ST.build(1, 1, n);
if (vecHS.find(ST.st[1]) != vecHS.end()) cout <<"Yes\n";
else cout <<"No\n";
rep (i, 1, Q) {
int L, R;
char C;
cin >> L >> R >> C;
ST.update(L, R, C);
if (vecHS.find(ST.st[1]) != vecHS.end()) cout <<"Yes\n";
else cout <<"No\n";
}
}
#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
int main () {
// file("c");
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll num_Test = 1;
// cin >> num_Test;
while(num_Test--)
solution();
}
/*
18 3
2 5
6 21
13 19
9 17
14 17
19 20
2 16
2 10
9 14
19 20
14 16
1 3
17 19
14 21
18 19
4 7
5 12
1 13
*/
Compilation message
Main.cpp: In member function 'void Segment_Tree::build(int, int, int)':
Main.cpp:43:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
43 | int mid = l + r >> 1;
| ~~^~~
Main.cpp: In member function 'void Segment_Tree::down(int, int, int)':
Main.cpp:49:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
49 | int mid = l + r >> 1;
| ~~^~~
Main.cpp: In member function 'void Segment_Tree::update(int, int, int, int, int, int)':
Main.cpp:65:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
65 | int mid = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
4956 KB |
Output is correct |
| 2 |
Correct |
54 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
61 ms |
5088 KB |
Output is correct |
| 4 |
Incorrect |
45 ms |
5000 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
4956 KB |
Output is correct |
| 2 |
Correct |
54 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
61 ms |
5088 KB |
Output is correct |
| 4 |
Incorrect |
45 ms |
5000 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
4956 KB |
Output is correct |
| 2 |
Correct |
54 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
61 ms |
5088 KB |
Output is correct |
| 4 |
Incorrect |
45 ms |
5000 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
4956 KB |
Output is correct |
| 2 |
Correct |
54 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
61 ms |
5088 KB |
Output is correct |
| 4 |
Incorrect |
45 ms |
5000 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
