JZOJ 5497 塔（哈希）

发表于 |
字数统计: 1,127字 | 阅读时长 ≈ 5min

塔
-

问题描述

有一个塔,他的名字叫做粽粑,粽粑的每一层都有一个颜色 .
粽粑非常厉害,它在吸收天地精华之后会长高.粽粑的长高方式有两种:
1.在塔顶长出一层.
2.在塔底长出一层,即原来的第一层变成第二层,第二层变成第三层,以此类推,新长出来的是第一层.
粽粑有可能在某个时刻不是很开心,这个时候它会撤销它的前若干次长高.
你现在想知道粽粑长高的奥秘,于是找到了粽粑,发现它的入口上写着这么一句话:要进入粽粑,请找出一段最长的塔的区间,满足翻转后颜色不变.
粽粑会不断的长高（或撤销）,所以它每次长高（或撤销）后你都要回答.为了你的方便,粽粑一开始的高度为0。
这里写图片描述
q<=10^7

样例输入

7
101102100299199198298

样例输出

25

题意让维护一个串的最长回文子串长度，并且要支持修改和撤销，并且强制在线。
如果数据范围稍微小点，那么就是回文树裸题。但这题显然是故意要卡它。

注意到每次操作后，最长回文子串长度最多增加2，且一定包含操作的端点，那么可以用哈希来解决。

哈希的主要思想是记录从左到右的前缀哈希值，再记录从右到左的后缀哈希值，然后判断一个区间$[L,R]$是否回文的时候，只需要取出$[L,R]$的前缀哈希值和后缀哈希值比较一下即可。

至于撤销操作，只需要维护一个时间戳就行了，直接暴力撤销，复杂度是线性的。

代码实现的时候可以将在零点左边和右边的部分分开维护，分别记录一下$pow$递增和递减的哈希值，递减的用逆元处理。然后查询的时候再把左右两段拼接起来。具体可以参考代码。

复杂度$O(q)$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 10000005
#define ll long long
using namespace std;
const int mod=998244353,p=131;
int QM(int a,int b)
{
	int o=1;
	while(b)
	{
		if(b&1)o=1ll*o*a%mod;
		b>>=1;a=1ll*a*a%mod;
	}
	return o;
}
char s[3*N];
ll Ans;
int q,L,R,ans[N],T,ty[N];
int La[N],Lb[N],Ra[N],Rb[N],Pow[N],Inv[N];
bool JudgeL(int Le)
{
	if(L+R<Le)return 0;
	if(Le<=L)
	{
		int a=1ll*(La[L]-La[L-Le]+mod)*Inv[L-Le+1]%mod;
		int b=1ll*(Lb[L]-Lb[L-Le]+mod)*Pow[L]%mod;
		return a==b;
	}
	else
	{
		int a=1ll*La[L]*Pow[Le-L-1]%mod+1ll*Rb[Le-L]*Pow[Le-L]%mod;a%=mod;
		int b=1ll*Lb[L]*Pow[L]%mod+1ll*Ra[Le-L]*Pow[L-1]%mod;b%=mod;
		return a==b;
	}
}
bool JudgeR(int Le)
{
	if(L+R<Le)return 0;
	if(Le<=R)
	{
		int a=1ll*(Ra[R]-Ra[R-Le]+mod)*Inv[R-Le+1]%mod;
		int b=1ll*(Rb[R]-Rb[R-Le]+mod)*Pow[R]%mod;
		return a==b;
	}
	else
	{
		int a=1ll*Ra[R]*Pow[Le-R-1]%mod+1ll*Lb[Le-R]*Pow[Le-R]%mod;a%=mod;
		int b=1ll*Rb[R]*Pow[R]%mod+1ll*La[Le-R]*Pow[R-1]%mod;b%=mod;
		return a==b;
	}
}
void CalL()
{
	if(JudgeL(ans[T-1]+2))ans[T]=ans[T-1]+2;
	else if(JudgeL(ans[T-1]+1))ans[T]=ans[T-1]+1;
	else ans[T]=ans[T-1];
}
void CalR()
{
	if(JudgeR(ans[T-1]+2))ans[T]=ans[T-1]+2;
	else if(JudgeR(ans[T-1]+1))ans[T]=ans[T-1]+1;
	else ans[T]=ans[T-1];
}
int main()
{
	int i,j,k,num,Len;char a,b,c;
	scanf("%d\n",&q);
	Pow[0]=Inv[0]=1;Inv[1]=QM(p,mod-2);
	for(i=1;i<=q;i++)Pow[i]=1ll*Pow[i-1]*p%mod;
	for(i=2;i<=q;i++)Inv[i]=1ll*Inv[i-1]*Inv[1]%mod;
	gets(s);Len=q*3;
	for(i=0;i<Len;i+=3)
	{
		a=s[i];b=s[i+1];c=s[i+2];
		num=b-48;num=(num<<1)+(num<<3);
		num+=c-48;
		num+=ans[T];num%=100;
		if(a=='1')
		{
			L++;ty[++T]=1;
			La[L]=(La[L-1]+1ll*num*Pow[L])%mod;
			Lb[L]=(Lb[L-1]+1ll*num*Inv[L])%mod;
			CalL();
		}
		else if(a=='2')
		{
			R++;ty[++T]=2;
			Ra[R]=(Ra[R-1]+1ll*num*Pow[R])%mod;
			Rb[R]=(Rb[R-1]+1ll*num*Inv[R])%mod;
			CalR();
		}
		else while(num--)(ty[T--]==1)?(L--):(R--);
		Ans+=ans[T];
	}
	printf("%lld",Ans);
}