题目大意:定义LCQ为从x,y分别开始,有多长完全一样。维护数据结构,给出xy,求出LCQ。此外还有修改和插入字符。
思路:LCQ一定是Hash+二分,那么插入和修改呢,当然就是用Splay维护了。Splay上的每个节点存当前位置的字符,和它和整个子树的Hash值,重要是PushUp函数。除了维护子树大小,还需要维护Hash值。
与正常计算Hash值的方法一样,更新的根节点的Hash值可以表示为 Hash = ls->Hash + 27 ^ ls->size * Hash(root) + 27 ^ (ls->size + 1) * rs->Hash
详见代码。
(ps:这个题unsinged int也能卡过,而且快不少,我已经刷到第二篇了w)
CODE;
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 100010
using namespace std;
unsigned long long power[MAX];
struct Complex{
char c;
int size;
unsigned long long hash;
Complex *son[2],*father;
void Combine(Complex *a,bool dir) {
son[dir] = a;
a->father = this;
}
bool Check() {
return father->son[1] == this;
}
void PushUp() {
size = son[0]->size + son[1]->size + 1;
hash = son[0]->hash + (c - 'a' + 1) * power[son[0]->size] + son[1]->hash * power[son[0]->size + 1];
}
}*nil = new Complex,*root;
char s[MAX];
int asks;
void Pretreatment();
Complex *BuildTree(int l,int r);
Complex *NewComplex(char _);
Complex *Kth(Complex *a,int k);
inline void Rotate(Complex *a,bool dir);
inline void Splay(Complex *a,Complex *aim);
inline void SplaySeg(int x,int y);
int main()
{
Pretreatment();
scanf("%s",s + 1);
int length = (int)strlen(s + 1);
root = BuildTree(0,length + 1);
root->father = nil;
cin >> asks;
for(int x,y,i = 1;i <= asks; ++i) {
scanf("%s",s);
if(s[0] == 'Q') {
scanf("%d%d",&x,&y);
if(x > y) swap(x,y);
int l = 0,r = root->size - 2 - y + 1,ans = 0;
while(l <= r) {
int mid = (l + r) >> 1;
SplaySeg(x,x + mid - 1);
unsigned long long hash1 = root->son[1]->son[0]->hash;
SplaySeg(y,y + mid - 1);
unsigned long long hash2 = root->son[1]->son[0]->hash;
if(hash1 == hash2)
ans = mid,l = mid + 1;
else r = mid - 1;
}
printf("%d\n",ans);
}
else if(s[0] == 'R') {
scanf("%d%s",&x,s);
Splay(Kth(root,x + 1),nil);
root->c = s[0];
root->PushUp();
}
else {
scanf("%d%s",&x,s);
Splay(Kth(root,x + 1),nil);
Splay(Kth(root,x + 2),root);
root->son[1]->Combine(NewComplex(s[0]),false);
root->son[1]->PushUp();
root->PushUp();
}
}
return 0;
}
void Pretreatment()
{
nil->son[0] = nil->son[1] = nil->father = nil;
nil->hash = 0;
power[0] = 1;
for(int i = 1;i < MAX; ++i)
power[i] = power[i - 1] * 27;
}
Complex *BuildTree(int l,int r)
{
if(l > r) return nil;
int mid = (l + r) >> 1;
Complex *re = NewComplex(s[mid]);
re->Combine(BuildTree(l,mid - 1),false);
re->Combine(BuildTree(mid + 1,r),true);
re->PushUp();
return re;
}
Complex *NewComplex(char _)
{
Complex *re = new Complex();
re->c = _;
re->son[0] = re->son[1] = nil;
re->hash = _ - 'a' + 1;
re->size = 1;
return re;
}
Complex *Kth(Complex *a,int k)
{
if(k <= a->son[0]->size) return Kth(a->son[0],k);
k -= a->son[0]->size;
if(k == 1) return a;
return Kth(a->son[1],k - 1);
}
inline void Rotate(Complex *a,bool dir)
{
Complex *f = a->father;
f->son[!dir] = a->son[dir];
f->son[!dir]->father = f;
a->son[dir] = f;
a->father = f->father;
f->father->son[f->Check()] = a;
f->father = a;
f->PushUp();
if(root == f) root = a;
}
inline void Splay(Complex *a,Complex *aim)
{
while(a->father != aim) {
if(a->father->father == aim)
Rotate(a,!a->Check());
else if(!a->father->Check()) {
if(!a->Check())
Rotate(a->father,true),Rotate(a,true);
else Rotate(a,false),Rotate(a,true);
}
else {
if(a->Check())
Rotate(a->father,false),Rotate(a,false);
else Rotate(a,true),Rotate(a,false);
}
}
a->PushUp();
}
inline void SplaySeg(int x,int y)
{
x++,y++;
Splay(Kth(root,x - 1),nil);
Splay(Kth(root,y + 1),root);
}