一転してこちらはまぁまぁ手間取ってる。
https://codeforces.com/contest/1477/problem/B
問題
01で構成される文字列S,Fが与えられる。
以下のクエリが順次与えられる。
この時、全クエリの条件を満たせるか判定せよ。
- 区間[L,R]が与えられる。この時点で、S[L...R]はすべて同じ値である。そうでない場合、条件を満たせない。
- その後、区間のうち半分未満の要素を01任意に置き換える。
最終的にSをFにできるか判定せよ。
解法
逆にFからSに巻き戻していくことを考える。
- クエリの実行前に、区間内の01の登場数が等しいときは不可。
- そうでない場合、クエリの実行前は、区間内の01多数派の方に合わせる。
最終的にFからSに巻き戻れば条件を満たす。
上記2つの処理を高速に処理できるデータ構造が欲しい。
以下のコードでは、0/1ではなく1/-1を格納し、区間乗算・区間加算・区間総和を求めるSegTreeを使い上記2処理を行った。
int T,N,Q; string S,F; int L[202020],R[202020]; template<class V,int NV> class SegTree_MulAdd { public: vector<V> sum,mul,add; // sum stores val after muladd SegTree_MulAdd(){sum.resize(NV*2,0); mul.resize(NV*2,1); add.resize(NV*2,0);}; V getval(int x,int y,int l=0,int r=NV,int k=1) { if(r<=x || y<=l) return 0; if(x<=l && r<=y) return sum[k]; x=max(x,l); y=min(y,r); V ret=getval(x,y,l,(l+r)/2,k*2)+getval(x,y,(l+r)/2,r,k*2+1); return ret*mul[k]+add[k]*(y-x); } void propagate(int k,int s) { mul[k*2]*=mul[k]; add[k*2]*=mul[k]; sum[k*2]*=mul[k]; add[k*2]+=add[k]; sum[k*2]+=add[k]*s/2; mul[k*2+1]*=mul[k]; add[k*2+1]*=mul[k]; sum[k*2+1]*=mul[k]; add[k*2+1]+=add[k]; sum[k*2+1]+=add[k]*s/2; mul[k]=1; add[k]=0; } void domul(int x,int y,V v,int l=0,int r=NV,int k=1) { if(l>=r) return; if(x<=l && r<=y) { mul[k]*=v; add[k]*=v; sum[k]*=v; } else if(l < y && x < r) { propagate(k,r-l); domul(x,y,v,l,(l+r)/2,k*2); domul(x,y,v,(l+r)/2,r,k*2+1); sum[k]=sum[k*2]+sum[k*2+1]; } } void doadd(int x,int y,V v,int l=0,int r=NV,int k=1) { if(l>=r) return; if(x<=l && r<=y) { add[k]+=v; sum[k]+=(r-l)*v; } else if(l < y && x < r) { propagate(k,r-l); doadd(x,y,v/mul[k],l,(l+r)/2,k*2); doadd(x,y,v/mul[k],(l+r)/2,r,k*2+1); sum[k]=sum[k*2]+sum[k*2+1]; } } }; SegTree_MulAdd<int, 1<<18> st; void solve() { int i,j,k,l,r,x,y; string s; cin>>T; while(T--) { cin>>N>>Q>>S>>F; st.domul(0,N+1,0); FOR(i,N) { if(F[i]=='1') st.doadd(i,i+1,1); else st.doadd(i,i+1,-1); } FOR(i,Q) { cin>>L[i]>>R[i]; L[i]--; } for(i=Q-1;i>=0;i--) { int num=st.getval(L[i],R[i]); if(num==0) { break; } else if(num<0) { // go 0 st.domul(L[i],R[i],0); st.doadd(L[i],R[i],-1); } else { // go 1 st.domul(L[i],R[i],0); st.doadd(L[i],R[i],1); } } int ok=1; if(i!=-1) ok=0; FOR(i,N) { x=st.getval(i,i+1); if((x==1)!=(S[i]=='1')) ok=0; } if(ok) cout<<"YES"<<endl; else cout<<"NO"<<endl; } }
まとめ
今覚え場、段々同じ値が増えていくので、ABC256のexみたいに、mapでやってもよかったな。