火星人prefix bzoj-1014 JSOI-2004

题目大意：给定一个字符串，支持三种操作：1.查询；两个后缀之间的$LCP$；2.单点修改；3.插入一个字符。

注释：$1\le n\le 10^5$，$1\le m\le 1.5\cdot 10^5$。

想法：

第一眼就是后缀数组，但是发现有单点插入操作果断$pass$。

一个序列支持单点插入肯定最少是个平衡树。

又发现$log^2n$好像能过，我们就对序列建立非旋转$Treap$然后维护子树$hash$值。

每一次查询的时候二分，然后撕出区间暴力验证即可。

时间复杂度$O(mlog^2n)$。

Code：

#include <bits/stdc++.h>

#define N 100010

using namespace std;

typedef unsigned int ull;

const ull base = 97 ;

int root,cnt; char s[N];

ull B[1000010];

#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)

char buf[100000],*p1,*p2;

inline int rd()

{

	register int x=0;register char c=nc();

	while(c<'0'||c>'9')c=nc();

	while(c>='0'&&c<='9')x=((x+(x<<2))<<1)+(c^48),c=nc();

	return x;

}

struct Node

{

	int ls,rs,size,key;

	ull sum,val;

}a[N<<1];

struct par {int x,y;};

inline void pushup(int x)

{

	int ls=a[x].ls,rs=a[x].rs;

	a[x].sum=a[x].val; a[x].size=1;

	if(ls) a[x].sum-=a[x].val,a[x].sum+=a[ls].sum+a[x].val*B[a[ls].size],a[x].size+=a[ls].size;

	if(rs) a[x].sum+=a[rs].sum*B[a[ls].size+1],a[x].size+=a[rs].size;

}

int merge(int x,int y)

{

	if(!x||!y) return x|y;

	if(a[x].key>a[y].key)

	{

		a[x].rs=merge(a[x].rs,y); pushup(x);

		return x;

	}

	else

	{

		a[y].ls=merge(x,a[y].ls); pushup(y);

		return y;

	}

}

par split(int x,int k)

{

	if(!k) return (par){0,x};

	int ls=a[x].ls,rs=a[x].rs;

	if(k==a[ls].size)

	{

		a[x].ls=0; pushup(x);

		return (par){ls,x};

	}

	else if(k==a[ls].size+1)

	{

		a[x].rs=0; pushup(x);

		return (par){x,rs};

	}

	else if(k<a[ls].size)

	{

		par t=split(ls,k);

		a[x].ls=t.y; pushup(x);

		return (par){t.x,x};

	}

	else

	{

		par t=split(rs,k-a[ls].size-1);

		a[x].rs=t.x; pushup(x);

		return (par){x,t.y};

	}

}

inline int newnode(ull val)

{

	int x=++cnt;

	a[x].ls=a[x].rs=0; a[x].size=1;

	a[x].sum=a[x].val=val; a[x].key=rand()*rand();

	return x;

}

void insert(int x,ull val)

{

	par t=split(root,x);

	root=merge(t.x,merge(newnode(val),t.y));

}

ull query(int x,int k)

{

	par t1=split(root,x-1),t2=split(t1.y,k);

	ull re=a[t2.x].sum;

	root=merge(t1.x,merge(t2.x,t2.y));

	return re;

}

void update(int x,ull y)

{

	par t1=split(root,x-1),t2=split(t1.y,1);

	root=merge(t1.x,merge(newnode(y),t2.y));

}

void output(int x)

{

	int ls=a[x].ls,rs=a[x].rs;

	if(ls) output(ls);

	printf("%lld ",a[x].val);

	if(rs) output(rs);

}

int build(int l,int r)

{

	if(l==r) return newnode(s[l]-'a'+1);

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

	return merge(build(l,mid),build(mid+1,r));

}

int main()

{

	srand(20021214);

	B[0]=1;

	for(int i=1;i<=1000000;i++) B[i]=B[i-1]*base;

	scanf("%s",s+1); int n=strlen(s+1);

	root=build(1,n);

	int m=rd(); while(m--)

	{

		char opt=nc(); while(opt!='Q'&&opt!='R'&&opt!='I')opt=nc(); int x=rd();

		if(opt=='Q')

		{

			int y=rd();

			int r=min(n-x+1,n-y+1)+1,l=0;

			// printf("%d %d\n",x,y);

			while(l<r)

			{

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

				// printf("%d %lld %lld\n",mid,query(x,mid),query(y,mid));

				if(query(x,mid)==query(y,mid)) l=mid+1;

				else r=mid;

			}

			printf("%d\n",l-1);

			// printf("djhdjhfjhfgjuhdfgiodfg=%d\n",query(x,5)==query(y,5));

			// r--;

			// int d,p=0;

			// for(d=1;d<=r&&query(x,d)==query(y,d);d<<=1) ;

			// for(d>>=1;d;d>>=1) if(p+d<=r&&query(x,p+d)==query(y,p+d)) p+=d;

			// // printf("djhdjhfjhfgjuhdfgiodfg=%d\n",query(x,5)==query(y,5));

			// printf("%d\n",p);

		}

		else if(opt=='R')

		{

			char d=nc();while(d<'a'&&d>'z')d=nc(); ull val=d-'a'+1;

			update(x,val);

		}

		else

		{

			n++;

			char d=nc();while(d<'a'&&d>'z')d=nc(); ull val=d-'a'+1;

			insert(x,val);

		}

	}

	return 0;

}

小结：卧槽这题卡常，用特判+读入优化+非旋转$Treap$的$O(n)$建树才卡过去。

巴特西

[bzoj1014][JSOI2008]火星人prefix_非旋转Treap_hash_二分

火星人prefix bzoj-1014 JSOI-2004

最新文章

热门文章