This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9+7;
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rep(i,x) for(ll i=0;i<x;i++)
#define faster ios::sync_with_stdio(false);cin.tie(nullptr)
template <typename T>
struct RMQ{
const T INF = 0;
ll N;
vector<T> dat,lazy;
RMQ(ll N_,vector<ll> &rui):N(),dat(N_*4,INF),lazy(N_*4,INF){
ll x=1;
while(N_>x) x*=2;
N=x;
}
void eval(ll k,ll l,ll r,vector<ll> &rui){
if(lazy[k]==-1) return;
if(k<N-1){
lazy[k*2+1]=lazy[k];
lazy[k*2+2]=lazy[k];
}
dat[k]=lazy[k]*((rui[r-l]-1+mod*((rui[r-l]+1)%2))/2);
dat[k]%=mod;
lazy[k]=-1;
}
void update(ll a,ll b,T x,ll k,ll l,ll r,vector<ll> &rui){
eval(k,l,r,rui);
if(a<=l&&r<=b){
lazy[k]=x;
eval(k,l,r,rui);
}else if(a<r&&l<b){
update(a,b,x,k*2+1,l,(l+r)/2,rui);
update(a,b,x,k*2+2,(l+r)/2,r,rui);
dat[k]=dat[k*2+1]+dat[k*2+2]*rui[(l+r)/2-l];
dat[k]%=mod;
}
}
void update(ll a,ll b,T x,vector<ll> &rui){update(a,b,x,0,0,N,rui);}
T query_sub(ll a,ll b,ll k,ll l,ll r,vector<ll> &rui){
eval(k,l,r,rui);
if(r<=a||b<=l){
return INF;
}else if(a<=l&&r<=b){
return dat[k];
}else{
T vl=query_sub(a,b,k*2+1,l,(l+r)/2,rui);
T vr=query_sub(a,b,k*2+2,(l+r)/2,r,rui);
return (vl+vr*rui[(l+r)/2-l])%mod;
}
}
T query(ll a,ll b,vector<ll> &rui){return query_sub(a,b,0,0,N,rui);}
};
int main(){
ll N;
cin >> N;
vector<ll> rui(800000);
rui[0]=1;
for(ll i=0;i<800000-1;i++) rui[i+1]=(rui[i]*3)%mod;
vector<vector<ll>> S(N,vector<ll>(3,-1));
rep(i,3){
rep(j,N){
char c;
cin >> c;
if(c=='J') S[j][i]=0;
if(c=='O') S[j][i]=1;
if(c=='I') S[j][i]=2;
}
}
set<ll> ans;
rep(i,27){
if(i==0) continue;
vector<ll> cnt(N,0);
ll i0=i%3;
ll i1=(i%9)/3;
ll i2=i/9;
if((i0+i1+i2)%3!=1) continue;
rep(j,N) cnt[j]+=S[j][0]*i0;
rep(j,N) cnt[j]+=S[j][1]*i1;
rep(j,N) cnt[j]+=S[j][2]*i2;
rep(j,N) cnt[j]%=3;
ll ANS=0;
rep(j,N) ANS=(ANS+cnt[j]*rui[j])%mod;
ans.insert(ANS);
}
ll Q;
cin >> Q;
ll N_=1;
while(N>N_) N_*=2;
RMQ<ll> T(N_,rui);
rep(i,N){
char c;
cin >> c;
if(c=='J') T.update(i,i+1,0,rui);
if(c=='O') T.update(i,i+1,1,rui);
if(c=='I') T.update(i,i+1,2,rui);
}
rep(i,Q+1){
ll x=T.query(0,N_,rui);
if(ans.find(x)!=ans.end()){
cout << "Yes" << '\n';
}
else cout << "No" << '\n';
if(i==Q) break;
ll l,r;
char c;
cin >> l >> r >> c;
l--;
ll C=-1;
if(c=='J') C=0;
if(c=='O') C=1;
if(c=='I') C=2;
T.update(l,r,C,rui);
}
}
# | 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... |