segment tree string with hashing

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pll;
typedef pair<ll,pair<ll,ll>>plll;
#define fastread() (ios_base:: sync_with_stdio(false),cin.tie(NULL));
#define vll(v) v.begin(),v.end()

#define F first
#define S second

#define pb push_back
#define eb emplace_back

const int Max = 1e5 + 10;
const int Mod = 1e9 + 7;
const double PI  =3.141592653589793238463;


#define P1 37
#define P2 29
#define MOD1 1000000007
#define MOD2 132021913

ll in1[Max],in2[Max];

typedef struct
{

    ll hash1,hash2,len;

} Node;

void make_power()
{
    ll i,power1=1,power2=1;
    for(i=0; i<Max-4; i++)
        {
            in1[i]=power1;
            in2[i]=power2;
             power1 = (power1 * P1)%MOD1;
             power2 = (power2 * P2)%MOD2;

        }

       // cout<<in1[0]<<endl;
}

Node Merge(Node a,Node b)
{
    Node res;
    res.hash1=(a.hash1+(in1[a.len]*b.hash1)%MOD1)%MOD1;

    res.hash2=(a.hash2+(in2[a.len]*b.hash2)%MOD2)%MOD2;
    res.len=a.len+b.len;
    return res;
}

struct segtree
{

    Node tree[Max*4];
    string str;

    void build(ll node,ll b,ll e)
    {
        if (b == e)
        {
            tree[node].hash1 = (str[b-1]*P1)%MOD1;
            tree[node].hash2 = (str[b-1]*P2)%MOD2;
            tree[node].len=1;
            return;
        }
        int Left = node * 2;
        int Right = node * 2 + 1;
        int mid = (b + e) / 2;


        build(Left, b, mid);
        build(Right, mid + 1, e);
        tree[node] = Merge(tree[Left],tree[Right]);
    }

    void update(ll node, ll b, ll e, ll i, pll newvalue)
    {
        if (i > e || i < b)
            return;
        if (b >= i && e <= i)
        {
            tree[node].hash1 = (newvalue.F*P1)%MOD1;
            tree[node].hash2 = (newvalue.F*P2)%MOD2;
            tree[node].len=newvalue.S;

            return;
        }
        int Left = node * 2;
        int Right = node * 2 + 1;
        int mid = (b + e) / 2;
        update(Left, b, mid, i, newvalue);
        update(Right, mid + 1, e, i, newvalue);
        tree[node] = Merge(tree[Left], tree[Right]);
    }

    Node query(ll node,ll l,ll r,ll i,ll j)
    {

        if (r < i || l > j) return {0,0,0};

        if (i <= l && r <= j)
        {
            return tree[node];
        }
        ll mid = (l+r)/2;
        return Merge(query(node << 1, l, mid,i,j), query(node << 1 | 1, mid + 1, r,i,j));
    }

    ll FindPos(ll node,ll l,ll r,ll pos)
    {
        if(l==r)return l;

        ll mid=(l+r)/2;

        if(tree[node*2].len>=pos)
            return FindPos(node*2,l,mid,pos);

        else return FindPos( (node*2)+1,mid+1,r,pos-tree[node*2].len);
    }



} shoja,ulta;

int main()
{

    fastread();

    ll i,j,n,m,p,a,sum=0,k,t,b,c,d,cnt=0,q,l,r,ans=0;

    bool flag=false;

    string str;

    make_power();

    cin>>str;

    shoja.str=str;

    reverse(vll(str));
    ulta.str=str;

    cin>>q;

    n=str.size();

    shoja.build(1,1,n);
    ulta.build(1,1,n);


    string test,ch;

    ll len=n;

   // cout<<shoja.tree[1].len<<" "<<ulta.tree[1].len<<endl;

    while(q--)
    {
        cin>>test;

        if(test=="C")
        {
            cin>>l>>r;

            ll x=shoja.FindPos(1,1,n,l);
            ll y=shoja.FindPos(1,1,n,r);


            ll xx=ulta.FindPos(1,1,n,len-r+1);
            ll yy=ulta.FindPos(1,1,n,len-l+1);

            Node ans1=shoja.query(1,1,n,x,y);


            Node ans2=ulta.query(1,1,n,xx,yy);

            if(ans1.hash1==ans2.hash1 && ans1.hash2==ans2.hash2)
                cout<<"Yes!"<<endl;

            else cout<<"No!"<<endl;
        }
        else if(test=="D")
        {
            cin>>l;

              pll newvalue={0,0};

            ll x=shoja.FindPos(1,1,n,l);
            ll y=ulta.FindPos(1,1,n,len-l+1);

            shoja.update(1,1,n,x,newvalue);
            ulta.update(1,1,n,y,newvalue);

            len--;
        }
        else
        {
            cin>>l>>ch;

            pll newvalue={ch[0],1};

            ll x=shoja.FindPos(1,1,n,l);
            ll y=ulta.FindPos(1,1,n,len-l+1);

            shoja.update(1,1,n,x,newvalue);
            ulta.update(1,1,n,y,newvalue);
        }
    }











}