#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
int u = uniform_int_distribution<int>(x, y)(rng);
return u;
}
int bm(int b, int p) { // bigmod
if(p==0) return 1;
int r = bm(b, p/2);
if(p&1) return (((r*r) % MOD) * b) % MOD;
return (r*r) % MOD;
}
string gene(string a, string b) {
string c;
for(int i=0; i<a.size(); i++) {
if(a[i] == b[i]) c += a[i];
else {
string t = "JOI";
for(int j=0; j<3; j++) {
if(a[i] != t[j] && b[i] != t[j]) c += t[j];
}
}
}
return c;
}
struct segtree_rurq {
// Range update range query, standard form 4 (assignment/sum)
struct node {
int upd = 0;
int ans = 0;
bool exist = 0;
};
vector<node> a;
int mod = 0;
//To be remained unchanged
void u(int l, int r, int constl, int constr, int idx, int val) {
if(l <= constl && constr <= r) {
a[idx].upd = val;
a[idx].ans = val * (constr-constl+1);
a[idx].exist = 1;
if(mod) {
a[idx].upd %= mod;
a[idx].ans %= mod;
}
return;
}
int mid = (constl+constr) >> 1;
//Lazy propagation
if(a[idx].exist == 1) {
a[2*idx+1].upd = a[idx].upd;
a[2*idx+2].upd = a[idx].upd;
a[idx].upd = 0;
a[2*idx+1].exist = 1;
a[2*idx+2].exist = 1;
a[idx].exist = 0;
a[2*idx+1].ans = a[2*idx+1].upd * (mid-constl + 1);
a[2*idx+2].ans = a[2*idx+2].upd * (constr-mid);
a[idx].ans = a[2*idx+1].ans + a[2*idx+2].ans;
}
if(mid<l || r<constl) u(l, r, mid+1, constr, 2*idx+2, val);
else if(constr<l || r<mid+1) u(l, r, constl, mid, 2*idx+1, val);
else {
u(l, r, constl, mid, 2*idx+1, val);
u(l, r, mid+1, constr, 2*idx+2, val);
}
a[idx].ans = a[2*idx+1].ans + a[2*idx+2].ans;
if(mod) a[idx].ans %= mod;
}
int qu(int l, int r, int constl, int constr, int idx) {
if(l <= constl && constr <= r) return a[idx].ans;
int mid = (constl+constr) >> 1;
int ret;
if(a[idx].exist == 1) {
a[2*idx+1].upd = a[idx].upd;
a[2*idx+2].upd = a[idx].upd;
a[idx].upd = 0;
a[2*idx+1].exist = 1;
a[2*idx+2].exist = 1;
a[idx].exist = 0;
a[2*idx+1].ans = a[2*idx+1].upd * (mid-constl + 1);
a[2*idx+2].ans = a[2*idx+2].upd * (constr-mid);
a[idx].ans = a[2*idx+1].ans + a[2*idx+2].ans;
}
if(mid<l || r<constl) {
ret = qu(l, r, mid+1, constr, 2*idx+2);
}
else if(constr<l || r<mid+1) {
ret = qu(l, r, constl, mid, 2*idx+1);
}
else {
ret = qu(l, r, constl, mid, 2*idx+1) + qu(l, r, mid+1, constr, 2*idx+2);
}
if(mod) ret %= mod;
return ret;
}
int sz;
public:
void set_mod(int x) {
mod = x;
}
void update(int l, int r, int v) {
u(l, r, 0, sz, 0, v);
}
int query(int l, int r) {
return qu(l, r, 0, sz, 0);
}
void resize(int k) {
sz = k;
a.resize(4*k + 10);
}
};
int code(char c) {
return (c == 'O' ? 1 : (c == 'I' ? 2 : 0));
}
void solve(int tc) {
int N;
cin >> N;
string s[9];
string word = "JOI";
for(int i=0; i<3; i++) {
cin >> s[i];
for(int j=0; j<N; j++) s[i] += word[rnd(0, 2)];
}
s[3] = gene(s[0], s[1]);
s[4] = gene(s[0], s[2]);
s[5] = gene(s[1], s[2]);
s[6] = gene(s[2], s[3]);
s[7] = gene(s[1], s[4]);
s[8] = gene(s[0], s[5]);
segtree_rurq st[9][3][3];
int dist[9] = {};
int Q = 200000;
cin >> Q;
string t0;
for(int j=0; j<N; j++) t0 += word[rnd(0, 2)];
cin >> t0;
for(int i=0; i<9; i++) {
for(int j=0; j<N; j++) {
if(t0[j] != s[i][j]) dist[i]++;
}
}
vector<int> lis[9][3];
for(int i=0; i<9; i++) {
for(int j=0; j<N; j++) {
lis[i][code(s[i][j])].push_back(j+1);
}
}
for(int i=0; i<9; i++) {
for(int j=0; j<3; j++) {
for(int k=0; k<3; k++) {
if(lis[i][j].empty()) continue;
st[i][j][k].resize(lis[i][j].size());
for(int l=0; l<lis[i][j].size(); l++) {
if(t0[lis[i][j][l] - 1] == word[k]) {
st[i][j][k].update(l+1, l+1, 1);
}
}
}
}
}
for(int i=0; i<=Q; i++) {
if(i > 0) {
int l, r;
l = rnd(1, N), r = rnd(1, N);
if(l > r) swap(l, r);
cin >> l >> r;
char c;
c = word[rnd(0, 2)];
cin >> c;
int d = (N <= 100 ? 9 : 1);
int L[d][3], R[d][3];
for(int j=0; j<d; j++) {
for(int k=0; k<3; k++) {
if(lis[j][k].empty()) {
L[j][k] = R[j][k] = -1;
continue;
}
int lb = 0, rb = lis[j][k].size() - 1;
while(lb < rb) {
int mid = (lb+rb) >> 1;
if(lis[j][k][mid] >= l) rb = mid;
else lb = mid+1;
}
L[j][k] = (lis[j][k][lb] >= l && lis[j][k][lb] <= r ? lb + 1 : -1);
lb = 0, rb = lis[j][k].size() - 1;
while(lb < rb) {
int mid = (lb+rb+1) >> 1;
if(lis[j][k][mid] <= r) lb = mid;
else rb = mid-1;
}
R[j][k] = (lis[j][k][lb] >= l && lis[j][k][lb] <= r ? lb + 1 : -1);
}
}
for(int j=0; j<d; j++) {
for(int k=0; k<3; k++) {
if(L[j][k] == -1 || R[j][k] == -1) continue;
for(int m=0; m<3; m++) {
st[j][k][m].update(L[j][k], R[j][k], 0);
}
st[j][k][code(c)].update(L[j][k], R[j][k], 1);
}
dist[j] = 0;
for(int k=0; k<3; k++) {
if(lis[j][k].empty()) continue;
for(int m=0; m<3; m++) {
if(k != m) dist[j] += st[j][k][m].query(1, lis[j][k].size());
}
}
}
}
bool ret = 0;
for(int j=0; j<d; j++) {
ret |= (dist[j] == 0);
}
cout << (ret ? "Yes\n" : "No\n");
}
}
int32_t main(){
ios::sync_with_stdio(0); cin.tie(0);
int t = 1; //cin >> t;
for(int i=1; i<=t; i++) {
solve(i);
}
}
Compilation message
Main.cpp: In function 'std::string gene(std::string, std::string)':
Main.cpp:20:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for(int i=0; i<a.size(); i++) {
| ~^~~~~~~~~
Main.cpp: In function 'void solve(int)':
Main.cpp:161:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
161 | for(int l=0; l<lis[i][j].size(); l++) {
| ~^~~~~~~~~~~~~~~~~
Main.cpp:221:24: error: 'd' was not declared in this scope
221 | for(int j=0; j<d; j++) {
| ^
