[JSOI2008]火星人 hash+splay

题目描述：

现在，火星人定义了一个函数 LCQ(x, y)LCQ(x,y)，表示：该字符串中第 xx 个字符开始的字串，与该字符串中第 yy 个字符开始的字串，两个字串的公共前缀的长度。比方说，LCQ(1, 7) = 5, LCQ(2, 10) = 1, LCQ(4, 7) = 0LCQ(1,7)=5,LCQ(2,10)=1,LCQ(4,7)=0
在研究 LCQLCQ 函数的过程中，火星人发现了这样的一个关联：如果把该字符串的所有后缀排好序，就可以很快地求出 LCQLCQ 函数的值；同样，如果求出了 LCQLCQ 函数的值，也可以很快地将该字符串的后缀排好序。

尽管火星人聪明地找到了求取 LCQLCQ 函数的快速算法，但不甘心认输的地球人又给火星人出了个难题：在求取 LCQLCQ 函数的同时，还可以改变字符串本身。具体地说，可以更改字符串中某一个字符的值，也可以在字符串中的某一个位置插入一个字符。地球人想考验一下，在如此复杂的问题中，火星人是否还能够做到很快地求取 LCQLCQ 函数的值。

题解：

一道哈希的合并+平衡树的问题。
我们知道一般来说，$hash[i]=hash[i-1]\times k+str[i]$，$k$ 为 26 或自己定的一个素数/进制
那么考虑我们知到$[1,a]$ 的哈希值和 $[a+2,b]$ 的哈希值，而且中间字母已知，我们怎样实现合并呢？
根据对哈希的定义，$hash[1,b]=hash[1,a]+str[a+1]\times p[a]+hash[a+2,b]\times p[a+1]$
我们就能够在 $O(1)$ 的时间复杂度将 2 个区间的哈希值进行合并。
剩下的事情就交给 $Splay$ 来维护区间信息了。

Code:

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cstring>

#include<string>

const int maxm=3000000;

const int maxn=3000000;

using namespace std;

void setIO(string a){

	freopen((a+".in").c_str(),"r",stdin);

}

void debug(){

	printf("ok\n");

}

char str[maxn];

unsigned int hash[maxm],p[maxm];

int n,root;

struct Splay_Tree{

	int ch[maxn][2],cnt_Tree,f[maxn],key[maxn],siz[maxn];

	#define lson ch[o][0]

	#define rson ch[o][1]

	int newnode(){return ++cnt_Tree;}

	int get(int x){return ch[f[x]][1]==x;}

    void pushup(int o){

    	if(!o) return ;

	    siz[o]=siz[lson]+siz[rson]+1;

	    hash[o]=hash[lson]+key[o]*p[siz[lson]]+hash[rson]*p[siz[lson]+1];

    }

    void buildSplay(int l,int r,int fa,int &o){

	    if(l>r) return;

	    int mid=(l+r)>>1;

	    o=newnode();

	    hash[o]=key[o]=str[mid]-'a';

	    f[o]=fa;

	    buildSplay(l,mid-1,o,ch[o][0]);

	    buildSplay(mid+1,r,o,ch[o][1]);

	    pushup(o);

    }

    void rotate(int x){

	    int old=f[x],oldf=f[old],which=get(x);

	    ch[old][which]=ch[x][which^1],f[ch[old][which]]=old;

	    ch[x][which^1]=old,f[old]=x;

	    f[x]=oldf;

	    if(oldf)

	    	ch[oldf][ch[oldf][1]==old]=x;

	    pushup(old),pushup(x);

	}

	void splay(int x,int &tar){

		int a=f[tar];

		for(int fa;(fa=f[x])!=a;rotate(x))

			if(f[fa]!=a) rotate(get(fa)==get(x)?fa:x);

		tar=x;

	}

	int findx(int pos,int o){                         //accurate position

		if(pos<=siz[ch[o][0]]) return findx(pos,ch[o][0]);

		else if(pos==siz[lson]+1) return o;

		else return findx(pos-siz[ch[o][0]]-1,ch[o][1]);

	}

	void insert(int pos,int val){

		int x=findx(pos,root);

		splay(x,root);

		int y=findx(pos+1,root);

		splay(y,ch[root][1]);

		int z=ch[ch[root][1]][0]=newnode();           //between

		f[z]=ch[root][1];

		hash[z]=key[z]=val;

		pushup(z),pushup(ch[root][1]);

		splay(z,root);

	}

	void update(int pos,int val){

		splay(findx(pos,root),root);

		key[root]=hash[root]=val;

		pushup(root);

	}

	unsigned int query(int pos,int length){

		int x=findx(pos-1,root);                     //origin

		splay(x,root);

		int y=findx(length+1,ch[root][1]);

		splay(y,ch[root][1]);                        //error!!!!

		int tmp=ch[root][1];

		return hash[ch[tmp][0]];

	}

}T;

void init(){

	scanf("%s",str+2);

	n=strlen(str+2);

	str[n+2]='a';

	str[1]='a';

	n+=2;

	p[0]=1;

	for(int i=1;i<maxn;++i) p[i]=p[i-1]*27;

}

int main(){

	//setIO("input");

	init();

	T.buildSplay(1,n,0,root);

	int m;

	scanf("%d",&m);

	while(m--){

		char opt[10];

		scanf("%s",opt);

		if(opt[0]=='Q'){

			int a,b;

			scanf("%d%d",&a,&b);

			if(a>b) swap(a,b);

			++a,++b;

			int l=1,r=n-b,ans=0;

			while(l<=r){

				int mid=(l+r)>>1;

				if(T.query(a,mid)==T.query(b,mid)) ans=mid,l=mid+1;

				else r=mid-1;

			}

			printf("%d\n",ans);

			continue;

		}

		char ss[10];

		int x,delta;

		scanf("%d",&x);

		scanf("%s",ss);

		delta=ss[0]-'a';

		if(opt[0]=='I') T.insert(x+1,delta),n+=1;			     //insert position: x+2 -> x+2

		if(opt[0]=='R') T.update(x+1,delta);                     //actual position: x+1

	}

	return 0;

}

巴特西

[JSOI2008]火星人 hash+splay

最新文章

热门文章