Cod sursă (job #618375)

#include <iostream>
#include <fstream>
#include <ctime>
#include <cstdlib>
#include <climits>
using namespace std;
const int cuvmax=800005;
const long long mod1=1000*1000*1000+7;
const long long mod2=1000*1000*1000+9;
const long long base=30;
string s,A;
struct Treap
{
    long long m1,m2,v;
    int val;
    int pr,w;
    Treap *ls,*rs;
    Treap(){};
    Treap(int value,int priority,Treap* a,Treap* b)
    {
        this->val=value;
        this->pr=priority;
        this->ls=a;this->rs=b;
        this->w=this->m1=this->m2=this->v=0;
    }
}*R,*nil;
struct hasher
{
    long long m11,m22;
}h[cuvmax],p[60000+5],a,ans;
int len[cuvmax];
int n,m,prio,answer,H,cost,i,j,a1,b1,tip,ind;
int x,ret;
long long M,poz;
char ch;
void compute(Treap* &nod)
{
    nod->w=nod->ls->w+nod->rs->w+1;
    nod->m1=1LL*(((((((nod->ls->m1)*base+nod->v))%mod1)*p[nod->rs->w].m11)%mod1+nod->rs->m1)%mod1);
    nod->m2=1LL*(((((((nod->ls->m2)*base+nod->v))%mod2)*p[nod->rs->w].m22)%mod2+nod->rs->m2)%mod2);
}
void rot1(Treap* &nod)
{
    Treap *T=nod->ls;
    nod->ls=T->rs;T->rs=nod;
    nod=T;
}
void rot2(Treap* &nod)
{
    Treap *T=nod->rs;
    nod->rs=T->ls;T->ls=nod;
    nod=T;
}
void balance(Treap* &nod)
{
    if(nod->ls->pr>nod->pr)
        rot1(nod);
    if(nod->rs->pr>nod->pr)
        rot2(nod);
    if(nod->ls!=nil)compute(nod->ls);
    if(nod->rs!=nil)compute(nod->rs);
}
void ins(Treap* &nod)
{
    if(nod==nil)
    {
        nod=new Treap(x,prio,nil,nil);
        nod->v=nod->m1=nod->m2=H;nod->w=1;
        return;
    }
    if(x<nod->val) ins(nod->ls);
    else ins(nod->rs);
    balance(nod);
    compute(nod);
}
void query(Treap* nod)
{
    if(cost+nod->ls->w<=poz)
    {
        a.m11=1LL*((a.m11*p[nod->ls->w].m11)%mod1+nod->ls->m1)%mod1;
        a.m22=1LL*((a.m22*p[nod->ls->w].m22)%mod2+nod->ls->m2)%mod2;
        cost+=nod->ls->w;
        if(cost+1<=poz)
        {
            a.m11=1LL*(a.m11*base+nod->v)%mod1;
            a.m22=1LL*(a.m22*base+nod->v)%mod2;
            cost++;
            if(cost==poz) return;
            query(nod->rs);
        }
    }
    else
    {
        query(nod->ls);
    }
}
void in(Treap* &nod)
{
    if(nod!=nil)
        in(nod->rs);
    else
    {
        nod=new Treap(x,prio,nil,nil);
        nod->v=nod->m1=nod->m2=H;nod->w=1;
        return;
    }
    balance(nod);
    compute(nod);
}
void in2(Treap* &nod)
{
    if(nod->rs!=nil)
        in2(nod->rs);
    else
    {
        in(nod->ls);
    }
    balance(nod);
    compute(nod);
}
void find_kth(Treap* &nod)
{
     if(cost+nod->ls->w<=poz)
    {
        cost+=nod->ls->w;
        if(cost==poz)
        {
            in2(nod->ls);
            balance(nod);
            compute(nod);
            return;
        }
        if(cost+1<=poz)
        {
            cost++;
            if(cost==poz)
            {
                in(nod->ls);
                balance(nod);
                compute(nod);
                return;
            }
            find_kth(nod->rs);
        }
    }
    else
    {
        find_kth(nod->ls);
    }
    balance(nod);
    compute(nod);
    return;
}
int main()
{
    ifstream f("sir8.in");
    ofstream g("sir8.out");
    f>>s;
    f>>n;
    R=nil=new Treap(0,0,NULL,NULL);
    srand(time(NULL));
    for(i=1;i<=n;i++)
    {
        f>>A;len[i]=A.size();
        for(j=0;j<A.size();j++)
        {
            H=A[j]-'a'+1;
            h[i].m11=1LL*(h[i].m11*base+H)%mod1;
            h[i].m22=1LL*(h[i].m22*base+H)%mod2;
        }
    }
    p[0].m11=p[0].m22=1;
    for(i=1;i<=60000;i++)
    {
        p[i].m11=(1LL*(p[i-1].m11*base))%mod1;
        p[i].m22=(1LL*(p[i-1].m22*base))%mod2;
    }
     f>>m;M=1000*1000*1000;
     for(i=1;i<=s.size();i++)
    {
        poz=i;
        x=1LL*(poz);H=s[i-1]-'a'+1;
        prio=rand()+1;
        ins(R);
    }
    answer=0;
    for(i=1;i<=m;i++)
    {
        f>>tip;
        if(tip==0)
        {
            f>>poz>>ch>>a1>>b1;
            if(!answer) poz^=a1;
            else poz^=b1;
            cost=0;x=0;
            prio=rand()+1;H=ch-'a'+1;
            if(R->w<poz) in(R);
            else find_kth(R);
        }
        else
        {
            f>>poz>>ind>>a1>>b1;
            if(!answer) poz^=a1;
            else poz^=b1;
            ans.m11=ans.m22=0;
            a.m11=a.m22=0;cost=0;
            query(R);
            ans=a;
            poz-=len[ind];a.m11=a.m22=0;cost=0;
            if(poz>0)query(R);
            ans.m11-=((1LL*a.m11*p[len[ind]].m11)%mod1);if(ans.m11<0) ans.m11+=mod1;
            ans.m22-=((1LL*a.m22*p[len[ind]].m22)%mod2);if(ans.m22<0) ans.m22+=mod2;
            if(ans.m11==h[ind].m11&&ans.m22==h[ind].m22) answer=1;
            else answer=0;
            g<<answer<<'\n';
        }
    }
    return 0;
}