记录编号	367518	评测结果	AAAAAAAAAA
题目名称	[JSOI 2008]火星人prefix	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	5.486 s
提交时间	2017-01-30 23:47:21	内存使用	0.93 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#include <list>
#include <string>
#include <functional>
#include <ctime>
using namespace std;
typedef unsigned long long ULL;
const int P = 31;
const int MAXN  = 1e5+8;
ULL fac[MAXN];
struct node{
  node *ls, *rs;
  int size;
  int fix;
  ULL hash;
  char ch;
  node(char c):ch(c), size(1), fix(rand()){
    ls = rs = NULL;
  }
  #define SIZE(x) ((x)?(x)->size:0)
  #define HASH(x) ((x)?(x)->hash:0)
  void pushup(){
    size = 1 + SIZE(ls) + SIZE(rs);
    hash = (HASH(ls)*P + (ch-'a')) * fac[SIZE(rs)] + HASH(rs); 
  }
};
typedef pair<node*, node*> droot;
droot split(node *x, int k){
  if(!x)return droot(NULL, NULL);
  droot r;
  if(SIZE(x->ls) >= k){
    r = split(x->ls, k);
    x->ls = r.second;
    x->pushup();
    r.second = x;
  }else{
    r = split(x->rs, k-SIZE(x->ls)-1);
    x->rs = r.first;
    x->pushup();
    r.first = x;
  }
  return r;
}
node *merge(node *x, node *y){
  if(!x){y->pushup(); return y;}
  if(!y){x->pushup(); return x;}
  if(x->fix < y->fix){
    x->rs = merge(x->rs, y);
    x->pushup();
    return x;
  }else{
    y->ls = merge(x, y->ls);
    y->pushup();
    return y;   
  }
}
typedef node *pnode;
node *build(const char *s, int n)
{
  pnode *stk = new pnode[n];
  node *last;
  int tp = 0;
  for(int i = 0; i < n; i++){
    node *p = new node(s[i]);
    last = NULL;
    while(tp && stk[tp-1]->fix > p->fix){
      stk[tp-1]->pushup();
      last = stk[tp-1];
      stk[--tp] = NULL;
    }
    if(tp)stk[tp-1]->rs = p;
    p->ls = last;
    stk[tp++] = p;
  }
  while(tp)stk[--tp]->pushup();
  node *r = stk[0];
  delete []stk;
  return r;
}
node *root;
struct range{
  node *left, *middle, *right;
};
range get_range(int l, int r){
  droot p1 = split(root, l-1);
  droot p2 = split(p1.second, r-l+1);
  return (range){p1.first, p2.first, p2.second};
}
inline void merge_range(range r){
  root = merge(r.left, merge(r.middle, r.right));
}
ULL hashv(int l, int r){
  range p = get_range(l, r);
  ULL res = p.middle->hash;
  merge_range(p);
  return res;
}
void insert(int p, char c){
  node *d = new node(c);
  droot ps = split(root, p);
  merge_range((range){ps.first, d, ps.second});
}
void modify(int p, char c){
  range ran = get_range(p, p);
  ran.middle->ch = c;
  merge_range(ran);
}
int query(int x, int y){
  int l = 1, r = root->size-max(x, y)+1;
  int ans = 0;
  while(l <= r){
    int m = (l+r)>>1;
    if(hashv(x, x+m-1) == hashv(y, y+m-1))ans = m,l = m+1;
    else r = m-1;
  }
  return ans;
}
void pre(){
  fac[0] = 1;
  for(int i = 1; i < MAXN; i++)fac[i] = P*fac[i-1];
}
char str[100002];
int main(){
  freopen("bzoj_1014.in", "r", stdin);
  freopen("bzoj_1014.out", "w", stdout);
  srand(time(NULL));
  pre(); 
  scanf(" %s", str);
  root = build(str, strlen(str));
  int m;scanf("%d", &m);
  while(m--){
    char op;scanf(" %c", &op);
    if(op == 'Q'){
      int l, r;scanf("%d %d", &l, &r);
      printf("%d\n", query(l, r));
    }else if(op == 'R'){
      int p;scanf("%d", &p);
      char c;scanf(" %c", &c);
      modify(p, c);
    }else if(op == 'I'){
      int p;scanf("%d", &p);
      char c;scanf(" %c", &c);
      insert(p, c);
    }
  }
  return 0;
}