[CF827C] DNA Evolution - 线段树

Description

给定只含 ACTG 的字符串 S，有两种操作，要么修改某个字符，要么询问在一个区间内，与询问串的循环重复匹配的字符个数。询问串长度不超过 10。

Solution

设 \(Seg[i][j][k]\) 表示用于维护下标对 \(i\) 取模，余数为 \(j\)，字符 \(k\) 的出现的动态开点线段树

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

#define int long long
const int N = 1000005;

struct Node
{
    int ch[2];
    int val;
} node[N*10];

int ind;

int Newnode()
{
    return ++ind;
}

struct SegmentTree
{
    int root;

    SegmentTree()
    {
        root=Newnode();
    }

    void modify(int p,int l,int r,int pos,int key)
    {
        node[p].val+=key;
        if(l!=r)
        {
            if(pos<=(l+r)/2)
            {
                if(node[p].ch[0]==0) node[p].ch[0]=Newnode();
                modify(node[p].ch[0],l,(l+r)/2,pos,key);
            }
            else
            {
                if(node[p].ch[1]==0) node[p].ch[1]=Newnode();
                modify(node[p].ch[1],(l+r)/2+1,r,pos,key);
            }
        }
    }

    void modify(int l,int r,int pos,int key)
    {
        modify(root,l,r,pos,key);
    }

    int query(int p,int l,int r,int ql,int qr)
    {
        //cout<<"query "<<l<<" "<<r<<" ... "<<p<<endl;
        if(!p || l>qr || r<ql) return 0;
        if(l>=ql&&r<=qr) return node[p].val;
        return query(node[p].ch[0],l,(l+r)/2,ql,qr) + query(node[p].ch[1],(l+r)/2+1,r,ql,qr);
    }

    int query(int l,int r,int ql,int qr)
    {
        return query(root,l,r,ql,qr);
    }
} seg[12][12][5];

int s[N],n,m;

signed main()
{
    ios::sync_with_stdio(false);

    string tmp;
    cin>>tmp;
    for(int i=1;i<=tmp.length();i++)
    {
        if(tmp[i-1]==‘A‘) s[i]=1;
        if(tmp[i-1]==‘T‘) s[i]=2;
        if(tmp[i-1]==‘G‘) s[i]=3;
        if(tmp[i-1]==‘C‘) s[i]=4;
    }

    n=tmp.length();

    for(int len=1;len<=10;len++)
    {
        for(int i=1;i<=n;i++)
        {
            //cout<<":: "<<len<<" "<<i%len<<" "<<s[i]<<" "<<i<<endl;
            seg[len][i%len][s[i]].modify(1,n,i,1);
        }
    }

    //cout<<"III"<<ind<<endl;

    cin>>m;

    for(int t=1;t<=m;t++)
    {
        int t1,t2,t3;
        cin>>t1>>t2;
        char ch;
        if(t1==1) cin>>ch;
        if(t1==2) cin>>t3>>tmp;

        if(t1==1)
        {
            int tar=0;
            if(ch==‘A‘) tar=1;
            if(ch==‘T‘) tar=2;
            if(ch==‘G‘) tar=3;
            if(ch==‘C‘) tar=4;
            for(int len=1;len<=10;len++)
            {
                seg[len][t2%len][s[t2]].modify(1,n,t2,-1);
                seg[len][t2%len][tar].modify(1,n,t2,+1);
            }
            s[t2]=tar;
        }
        else
        {
            int qs[15]={};
            int l=tmp.length();
            for(int i=1;i<=l;i++)
            {
                if(tmp[i-1]==‘A‘) qs[i]=1;
                if(tmp[i-1]==‘T‘) qs[i]=2;
                if(tmp[i-1]==‘G‘) qs[i]=3;
                if(tmp[i-1]==‘C‘) qs[i]=4;
            }
            int ans=0;
            for(int i=1;i<=l;i++)
            {
                //cout<<".... "<<l<<" "<<(i+t2-1)%l<<" "<<qs[i]<<" "<<t2<<" "<<t3<<endl;
                ans+=seg[l][(i+t2-1)%l][qs[i]].query(1,n,t2,t3);
                //cout<<ans<<","<<endl;
            }
            cout<<ans<<endl;
        }
    }
}

[CF827C] DNA Evolution - 线段树

原文：https://www.cnblogs.com/mollnn/p/13627702.html