#include <bits/stdc++.h>
#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define pp pair<ll, ll>
using namespace std;
vi inp(string a){
vi A(a.size());
for(int i = 0; i < a.size(); i++){
if(a[i] == 'J'){
A[i] = 0;
}else if(a[i] == 'O'){
A[i] = 1;
}else if(a[i] == 'I'){
A[i] = 2;
}
}
return A;
}
vi add(vi a, vi b, vi c, vi d){
ll n = a.size();
vi ans(n);
for(int i = 0; i < n; i++){
ans[i] = (a[i] + b[i] + c[i] + d[i]) % 3;
}
return ans;
}
vi Itree, lazy;
vi ex, allOne;
ll mod = 1000000007;
ll p = 137;
ll inv = 1;
ll modpow(ll a, ll b, ll md){
if(b == 0) return 1;
if(b == 1) return a;
ll ans = modpow(a, b / 2, md);
if(b % 2 == 0){
return ans * ans % md;
} else{
return (((ans * ans) % md) * a) % md;
}
}
void init(ll n){
ex.resize(n, 1);
allOne.resize(n, 1);
for(int i = 1; i < n; i++){
ex[i] = (ex[i - 1] * p) % mod;
allOne[i] - allOne[i - 1] + ex[i];
allOne[i] %= mod;
}
inv = modpow(p - 1, mod - 2, mod);
while(n & (n - 1)) n++;
Itree.resize(2*n, 0);
lazy.resize(2*n, -1);
}
void setSum(ll u, ll a, ll b, ll val){
Itree[u] = (val * ex[a] % mod) * allOne[b - a - 1] % mod;
}
void lazyUpdate(ll u, ll a, ll b){
if(lazy[u] == -1) return;
setSum(u, a, b, lazy[u]);
if(2*u < Itree.size()){
lazy[2*u] = lazy[u];
lazy[2*u + 1] = lazy[u];
}
lazy[u] = -1;
}
void setRange2(ll u, ll l, ll r, ll a, ll b, ll val){
lazyUpdate(u, a, b);
if(l == a && r == b){
lazy[u] = val;
lazyUpdate(u, a, b);
return;
}
ll s = (a + b) / 2;
if(s >= r){
setRange2(2*u, l, r, a, s, val);
}else if(s <= l){
setRange2(2*u + 1, l, r, s, b, val);
}else{
setRange2(2*u, l, s, a, s, val);
setRange2(2*u + 1, s, r, s, b, val);
}
lazyUpdate(2*u, a, s);
lazyUpdate(2*u + 1, s, b);
Itree[u] = Itree[2*u] + Itree[2*u + 1] % mod;
}
void setRange(ll l, ll r, ll val){
setRange2(1, l, r, 0, Itree.size() / 2, val);
}
ll countHash(vi A){
ll ans = 0;
for(int i = 0; i < A.size(); i++){
ans += A[i] * ex[i];
ans %= mod;
}
return ans;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
ll n;
cin >> n;
string a, b, c;
cin >> a >> b >> c;
vi A = inp(a), B = inp(b), C = inp(c);
vvi poss = {A, B, C, add(A, A, B, B), add(A, A, C, C), add(B, B, C, C), add(A, B, C, A), add(A, B, C, B), add(A, B, C, C)};
init(n);
set<ll> hash;
for(int i = 0; i < poss.size(); i++){
hash.insert(countHash(poss[i]));
}
ll q;
cin >> q;
string t;
cin >> t;
vi T = inp(t);
/*bool ok = false;
for(int i = 0; i < poss.size(); i++){
bool akt = true;
for(int j = 0; j < poss[i].size(); j++){
if(poss[i][j] != T[j]){
akt = false;
}
}
if(akt) ok = true;
}
if(ok) {
cout << "Yes" << '\n';
}else{
cout << "No" << '\n';
}*/
for(int i = 0; i < n; i++){
setRange(i, i + 1, T[i]);
}
if(hash.count(Itree[1])){
cout << "Yes" << '\n';
}else{
cout << "No" << '\n';
}
while(q--){
ll x, y, z;
char ch;
cin >> x >> y >> ch;
if(ch == 'J'){
z = 0;
}else if(ch == 'O'){
z = 1;
}else if(ch == 'I'){
z = 2;
}
/*for(int i = x - 1; i < y; i++){
T[i] = z;
}
bool ok = false;
for(int i = 0; i < poss.size(); i++){
bool akt = true;
for(int j = 0; j < poss[i].size(); j++){
if(poss[i][j] != T[j]){
akt = false;
}
}
if(akt) ok = true;
}
if(ok) {
cout << "Yes" << '\n';
}else{
cout << "No" << '\n';
}*/
setRange(x - 1, y, z);
if(hash.count(Itree[1])){
cout << "Yes" << '\n';
}else{
cout << "No" << '\n';
}
cout << endl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |