用splay维护序列, 二分+hash来判断LCQ..

#include
     
      using namespace std;typedef unsigned long long ull;const int maxn = 100009;const int P = 1000173169;ull K[maxn];int N;char S[maxn];struct Node {	Node *ch[2], *p;	int s, v;	ull h;	inline void setc(Node* c, int d) {		ch[d] = c;		c->p = this;	}	inline int d() {		return this == p->ch[1];	}	inline void upd() {		s = ch[0]->s + ch[1]->s + 1;		h = ull(v) * K[ch[1]->s] + ull(ch[0]->h) * K[ch[1]->s + 1] + ch[1]->h;	}} pool[maxn], *null, *root, *pt = pool;Node* newNode(int _v) {	Node* t = pt++;	t->ch[0] = t->ch[1] = t->p = null;	t->v = t->h = _v; t->s = 1;	return t;}void rot(Node* t) {	Node* p = t->p;	int d = t->d();	p->p->setc(t, p->d());	p->setc(t->ch[d ^ 1], d);	t->setc(p, d ^ 1);	p->upd();	if(p == root)	    root = t;}void splay(Node* t, Node* f = null) {	for(Node* p = t->p; p != f; p = t->p) {		if(p->p != f)		    p->d() != t->d() ? rot(t) : rot(p);		rot(t);	}	t->upd();}Node* select(int k) {	for(Node* t = root; ;) {		int s = t->ch[0]->s;		if(k == s)		    return t;		if(k > s)		    k -= s + 1, t = t->ch[1];		else		    t = t->ch[0];	}}Node* range(int l, int r) {	l--; r++;	Node *L = select(l), *R = select(r);	splay(L); splay(R, L);	return R->ch[0];}//[l, r)Node* build(int l, int r) {	if(l >= r) return null;	int m = (l + r) >> 1;	Node* t = newNode(S[m]);	t->setc(build(l, m), 0);	t->setc(build(m + 1, r), 1);	t->upd();	return t;}void init() {	null = pt++;	null->s = null->v = null->h = 0;	null->setc(null, 0);	null->setc(null, 1);	root = null;		K[0] = 1;	for(int i = 1; i < maxn; i++)	    K[i] = K[i - 1] * P;}int LCQ(int x, int y) {	if(x == y) return N - x + 1;	if(x > y) swap(x, y);	int L = 0, R = N - y + 1, ans;	while(L <= R) {		int m = (L + R) >> 1;		ull h = range(x, x + m - 1)->h;		if(range(y, y + m - 1)->h == h)		    ans = m, L = m + 1;		else		    R = m - 1;	}	return ans;}int main() {	freopen("test.in", "r", stdin);		init();	scanf("%s", S + 1); N = strlen(S + 1);	root = build(0, N + 2);		int m; scanf("%d", &m);	while(m--) {		char op; scanf(" %c", &op);		if(op == 'Q') {			int x, y; scanf("%d%d", &x, &y);			printf("%d\n", LCQ(x, y));		} else if(op == 'R') {			int x; scanf("%d", &x);			char c; scanf(" %c", &c);			Node* t = range(x, x);			t->v = c; t->upd();			t->p->upd(); root->upd();		} else {			N++;			int x; scanf("%d", &x);			char c; scanf(" %c", &c);			Node *L = select(x), *R = select(x + 1);			splay(L); splay(R, L);			R->setc(newNode(c), 0);			R->upd(); L->upd();		}	}		return 0;}
     

　　

1014: [JSOI2008]火星人prefix

Time Limit: 10 Sec  Memory Limit: 162 MB

Submit: 4228  Solved: 1295

[][][]

Description

火星人最近研究了一种操作：求一个字串两个后缀的公共前缀。比方说，有这样一个字符串：madamimadam，我们将这个字符串的各个字符予以标号：序号： 1 2 3 4 5 6 7 8 9 10 11 字符 m a d a m i m a d a m 现在，火星人定义了一个函数LCQ(x, y)，表示：该字符串中第x个字符开始的字串，与该字符串中第y个字符开始的字串，两个字串的公共前缀的长度。比方说，LCQ(1, 7) = 5, LCQ(2, 10) = 1, LCQ(4, 7) = 0 在研究LCQ函数的过程中，火星人发现了这样的一个关联：如果把该字符串的所有后缀排好序，就可以很快地求出LCQ函数的值；同样，如果求出了LCQ函数的值，也可以很快地将该字符串的后缀排好序。 尽管火星人聪明地找到了求取LCQ函数的快速算法，但不甘心认输的地球人又给火星人出了个难题：在求取LCQ函数的同时，还可以改变字符串本身。具体地说，可以更改字符串中某一个字符的值，也可以在字符串中的某一个位置插入一个字符。地球人想考验一下，在如此复杂的问题中，火星人是否还能够做到很快地求取LCQ函数的值。

Input

第一行给出初始的字符串。第二行是一个非负整数M，表示操作的个数。接下来的M行，每行描述一个操作。操作有3种，如下所示： 1、 询问。语法：Q x y，x, y均为正整数。功能：计算LCQ(x, y) 限制：1 <= x, y <= 当前字符串长度。 2、 修改。语法：R x d，x是正整数，d是字符。功能：将字符串中第x个数修改为字符d。限制：x不超过当前字符串长度。 3、 插入：语法：I x d，x是非负整数，d是字符。功能：在字符串第x个字符之后插入字符d，如果x = 0，则在字符串开头插入。限制：x不超过当前字符串长度。

Output

对于输入文件中每一个询问操作，你都应该输出对应的答案。一个答案一行。

Sample Input

madamimadam

7

Q 1 7

Q 4 8

Q 10 11

R 3 a

Q 1 7

I 10 a

Q 2 11

Sample Output

5

1

0

2

1

HINT

 

数据规模：

对于100%的数据，满足：

1、 所有字符串自始至终都只有小写字母构成。

2、 M <= 150,000

3、 字符串长度L自始至终都满足L <= 100,000

4、 询问操作的个数不超过10,000个。

对于第1，2个数据，字符串长度自始至终都不超过1,000

对于第3，4，5个数据，没有插入操作。

 

 

Source