P7803 [JOI Open 2021] 杂交 / Crossing 题解

mo_mo_yu0_0 · 2026-10-26 15:03:48 · 个人记录

说一下题解区没有的维护。

前面所有题解的维护都是哈希线段树，实际上有不需要哈希的做法。

对于每个字符串，维护区间内有几个是一样的。

每次区间修改，比如说是 J，我们只需要前缀和维护字符串区间内 J 的数量。由此维护三种即可。

#include<bits/stdc++.h>
using namespace std;

namespace Firefly{

    int n;
    const int N=2e5+10;
    set<string>st;
    set<string>st2;
    string p[13];
    int tot;

    int sum[13][N][3];
    int qsum(int id,int l,int r,int opt){
        return sum[id][r][opt]-sum[id][l-1][opt];
    }

    namespace Segment{
        int sumseg[11][N<<2];
        int tag[N<<2];
        #define ls (k<<1)
        #define rs (k<<1|1)
        #define mid ((l+r)>>1)
        void pushup(int k){
            for(int i=1;i<=tot;i++)sumseg[i][k]=sumseg[i][ls]+sumseg[i][rs];
        }
        void changenode(int k,int l,int r,int v){
            tag[k]=v;
            for(int i=1;i<=tot;i++)sumseg[i][k]=qsum(i,l,r,v);
        }
        void pushdown(int k,int l,int r){
            if(tag[k]==-1)return;
            changenode(ls,l,mid,tag[k]);
            changenode(rs,mid+1,r,tag[k]);
            tag[k]=-1;
        }
        void change(int k,int l,int r,int x,int y,int v){
            if(l>y||r<x)return;
            if(l>=x&&r<=y)return changenode(k,l,r,v);
            pushdown(k,l,r);
            change(ls,l,mid,x,y,v);
            change(rs,mid+1,r,x,y,v);
            pushup(k);
        }
        bool query(){
            for(int i=1;i<=tot;i++)
            if(sumseg[i][1]==n)return true;
            return false;
        }
    }using namespace Segment;

    string C(string x,string y){
        string ret;
        for(int i=0;i<(int)x.length();i++)
        if(x[i]==y[i])ret+=x[i];
        else if(x[i]!='J'&&y[i]!='J')ret+='J';
        else if(x[i]!='O'&&y[i]!='O')ret+='O';
        else ret+='I';
        return ret; 
    }

    void main(){
        memset(tag,-1,sizeof tag);
        cin>>n;
        string a,b,c;
        cin>>a>>b>>c;
        st.insert(a),st.insert(b),st.insert(c);
        while((int)st.size()!=(int)st2.size()){
            st2.clear();
            for(string x:st)
            for(string y:st)
            st2.insert(C(x,y));
            swap(st,st2);
        }
        for(string r:st){
            ++tot;
            for(int i=1;i<=n;i++){
                sum[tot][i][0]=sum[tot][i-1][0];
                sum[tot][i][1]=sum[tot][i-1][1];
                sum[tot][i][2]=sum[tot][i-1][2];
                if(r[i-1]=='J')sum[tot][i][0]++;
                if(r[i-1]=='O')sum[tot][i][1]++;
                if(r[i-1]=='I')sum[tot][i][2]++;
            }
        }
        int q;cin>>q;
        string t;cin>>t;
        for(int i=1;i<=n;i++){
            int tmp;
            if(t[i-1]=='J')tmp=0;
            else if(t[i-1]=='O')tmp=1;
            else tmp=2;
            change(1,1,n,i,i,tmp);
        }
        cout<<(query()?"Yes\n":"No\n");
        while(q--){
            int l,r;
            char c;
            cin>>l>>r>>c;
            int tmp;
            if(c=='J')tmp=0;
            else if(c=='O')tmp=1;
            else tmp=2;
            change(1,1,n,l,r,tmp);
            cout<<(query()?"Yes\n":"No\n");
        }
    }
}
signed main(){
    freopen("crossing.in","r",stdin);
    freopen("crossing.out","w",stdout); 
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    Firefly::main();
    return 0;
}