Cod sursă (job #307241)

#include <bits/stdc++.h>
#define B1 89
#define B2 97
#define MOD1 666013
#define MOD2 666019
#define INF 1000000000LL
#define MAXN 60000

struct Treap {
    Treap *left, *right;
    int prio;
    int sz;
    char val;
    int val1, val2;
    Treap(char _ch) {
        left = right = NULL;
        prio = rand();
        sz = 1;
        val = _ch;
        val1 = val2 = _ch;
    }
};
Treap *T = NULL;

Treap *insert(Treap *, int , char );
Treap *balance(Treap *);
Treap *rot_left(Treap *);
Treap *rot_right(Treap *);
inline void refresh(Treap *);

Treap *insert(Treap *nod, int pos, char ch) {
    if(nod == NULL) {
       nod = new Treap(ch);
       return nod;
    }
    if(nod -> left == NULL) {
       if(pos == 0)
         nod -> left = insert(nod -> left, pos, ch);
       else
         nod -> right = insert(nod -> right, pos - 1, ch);
    }
    else if(nod -> left -> sz >= pos)
       nod -> left = insert(nod -> left, pos, ch);
    else
       nod -> right = insert(nod -> right, pos - nod -> left -> sz - 1, ch);
    return balance(nod);
}

Treap *balance(Treap *nod) {
    if(nod -> left != NULL && nod -> left -> prio > nod -> prio)
       return rot_right(nod);
    if(nod -> right != NULL && nod -> right -> prio > nod -> prio)
       return rot_left(nod);
    refresh(nod);
    return nod;
}

Treap *rot_left(Treap *nod) {
   Treap *aux = nod -> right;
   nod -> right = aux -> left;
   aux -> left = nod;
   refresh(nod);
   refresh(aux);
   return aux;
}

Treap *rot_right(Treap *nod) {
   Treap *aux = nod -> left;
   nod -> left = aux -> right;
   aux -> right = nod;
   refresh(nod);
   refresh(aux);
   return aux;
}

std::pair <long long , long long> ans;

int pow1[MAXN + 1], pow2[MAXN + 1];

inline long long modulo(long long x, int mod) {
    if(x >= mod)
      x -= mod;
    return x;
}

void solve(Treap *nod, int l, int r, int b, int e) {
   if(nod == NULL)
     return ;
   if(l <= b && e <= r) {
      ans.first = (ans.first + 1LL * pow1[r - e] * nod -> val1) % MOD1;
      ans.second = (ans.second + 1LL * pow2[r - e] * nod -> val2) % MOD2;
      return ;
   }
   if(e < l || b > r)
      return ;
   int med = b;
   if(nod -> left != NULL)
     med += nod -> left -> sz;
   solve(nod -> left, l, r, b, med - 1);
   if(l <= med && med <= r) {
      ans.first = (ans.first + 1LL * pow1[r - med] * nod -> val) % MOD1;
      ans.second = (ans.second + 1LL * pow2[r - med] * nod -> val) % MOD2;
   }
   solve(nod -> right, l, r, med + 1, e);
}

inline void refresh(Treap *nod) {
    nod -> sz = 1;
    nod -> val1 = nod -> val2 = nod -> val;
    if(nod -> right != NULL) {
        nod -> val1 = (1LL * nod -> val1 * pow1[nod -> right -> sz]) % MOD1 + nod -> right -> val1;
        nod -> val2 = (1LL * nod -> val2 * pow2[nod -> right -> sz]) % MOD2 + nod -> right -> val2;
        nod -> val1 = modulo(nod -> val1, MOD1);
        nod -> val2 = modulo(nod -> val2, MOD2);
        nod -> sz += nod -> right -> sz;
    }
    if(nod -> left != NULL) {
        nod -> val1 = (1LL * nod -> left -> val1 * pow1[nod -> sz]) % MOD1 + nod -> val1;
        nod -> val2 = (1LL * nod -> left -> val2 * pow2[nod -> sz]) % MOD2 + nod -> val2;
        nod -> val1 = modulo(nod -> val1, MOD1);
        nod -> val2 = modulo(nod -> val2, MOD2);
        nod -> sz += nod -> left -> sz;
    }
}

std::string str;

inline char check(char ch) {
   if(ch >= 'A' && ch <= 'Z')
      return ch - 'A' + 1;
   return ch - 'a' + 27;
}

inline void prec() {
   pow1[0] = pow2[0] = 1;
   for(int i = 1; i <= MAXN; i++) {
       pow1[i] = pow1[i - 1] * B1;
       pow2[i] = pow2[i - 1] * B2;
       pow1[i] %= MOD1;
       pow2[i] %= MOD2;
   }
}

std::vector < std::pair <long long , int> > hashing;

int main() {
    std::ifstream fin("sir3.in");
    std::ofstream fout("sir3.out");
    int i, j, k, q, pos, a, b, ind;
    bool tip;
    char ch;
    std::ios::sync_with_stdio(false);
    srand(time(NULL));
    prec();
    fin >> str;
    for(i = 0; i < str.size(); i++)
       T = insert(T, i, check(str[i]));
    fin >> k;
    hashing.push_back(std::make_pair(0 , 0));
    for(i = 1; i <= k; i++) {
       str.clear();
       fin >> str;
       long long val1, val2;
       val1 = val2 = 0;
       for(j = 0; j < str.size(); j++) {
           val1 = val1 * B1 + check(str[j]);
           val2 = val2 * B2 + check(str[j]);
           val1 %= MOD1;
           val2 %= MOD2;
       }
       hashing.push_back(std::make_pair(1LL * val1 * INF + val2 , str.size()));
    }
    bool last = 0;
    fin >> q;
    while(q > 0) {
       q--;
       fin >> tip >> pos;
       if(tip == 0) {
          fin >> ch >> a >> b;
          if(last == 0)
            pos ^= a;
          else
            pos ^= b;
          T = insert(T, pos - 1, check(ch));
       }
       else {
          fin >> ind >> a >> b;
          if(last == 0)
            pos ^= a;
          else
            pos ^= b;
          ans.first = ans.second = 0;
          solve(T, pos - hashing[ind].second + 1, pos, 1, T -> sz);
          if(1LL * ans.first * INF + ans.second == hashing[ind].first)
            last = 1;
          else
            last = 0;
          fout << last << std::endl;
       }
    }
    fin.close();
    fout.close();
    return 0;
}