字符串游戏[bzoj2690]

发表于 分类于

题意

给定 $N$ 个仅有 小写字母组成的字符串 $a_ i$,每个字符串都有一个权值 $v_i$ ,有 $M$ 次操作，操作分三种：

  • Cv x v’:把第x个字符串的权值修改为v’

  • Cs x a’:把第x个字符串修改成a’

  • Q:求出当前的最大权字符串集合，使得这个集合中的字符串经过重新排列后满足除最后一个字符串外，前一个字符串是后一个的前缀(两个字符串相同也是前缀关系，也可以一个字符串都不选)

前50%的数据可以接受离线算法，后50%的数据要求在线算法。

$N\le 50000,M\le 10^5$ ，字符串总长 $\le 10^6$。

题解

将这些字符串建成Trie，只考虑权值大于 $0$ 的串，在字符串结尾出放上它的权值。那么答案就是Trie树上某个点到根节点的权值和的最大值。

当可以离线的时候，先把Trie建出来，然后维护每个节点的答案。修改一个字符串权值相当于子树加，修改字符串看成改点权就好了。

当要在线的时候，我们用Treap动态维护dfs序，记录当前的dfs序以及子树大小，考虑加一个字符串后的几种情况就好了。

一道复习Treap和Trie的好题~

程序

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())
const int N=2000010;
namespace Treap{
	int ch[N][2],fa[N],siz[N],rnd[N],rt,tot;
	ll val[N],mx[N],tag[N];
	int tid[N],id[N],len[N];
	inline void pushtag(int u,ll x)
	{
		if(u) tag[u]+=x,val[u]+=x,mx[u]+=x;
	}
	inline void pushid(int u,int s)
	{
		if(u) tid[u]+=s,id[u]+=s;
	}
	inline void pushdown(int u)
	{
		if(!u) return;
		if(tag[u])
		{
			pushtag(ch[u][0],tag[u]);
			pushtag(ch[u][1],tag[u]);
			tag[u]=0;
		}
		if(tid[u])
		{
			pushid(ch[u][0],tid[u]);
			pushid(ch[u][1],tid[u]);
			tid[u]=0;
		}
	}
	inline void pushup(int u)
	{
		siz[u]=siz[ch[u][0]]+siz[ch[u][1]]+1;
		mx[u]=max(val[u],max(mx[ch[u][0]],mx[ch[u][1]]));
		if(ch[u][0]) fa[ch[u][0]]=u;
		if(ch[u][1]) fa[ch[u][1]]=u;
	}
	void push(int u)
	{
		if(fa[u]) push(fa[u]);
		pushdown(u);
	}
	void split_siz(int u,int k,int &x,int &y)
	{
		if(!u) return (void)(x=y=0);
		pushdown(u);
		if(siz[ch[u][0]]>=k) y=u,split_siz(ch[u][0],k,x,ch[y][0]);
		else x=u,split_siz(ch[u][1],k-siz[ch[u][0]]-1,ch[x][1],y);
		pushup(u);
	}
	int merge(int x,int y)
	{
		if(!x||!y) {return x|y;}
		if(rnd[x]<rnd[y])
		{
			pushdown(x); ch[x][1]=merge(ch[x][1],y);
			pushup(x); return x;
		}
		else
		{
			pushdown(y); ch[y][0]=merge(x,ch[y][0]);
			pushup(y); return y;
		}
	}
	inline int Rank(int x)
	{
		push(x);
		int s=siz[ch[x][0]]+1;
		for(;x;x=fa[x])
			if(ch[fa[x]][1]==x)
				s+=siz[ch[fa[x]][0]]+1;
		return s;
	}
	void init()
	{
		tot=rt=1;
		rnd[1]=rand(); siz[1]=1; len[1]=id[1]=1;
	}
}
using namespace Treap;

int ne[N][26];
inline int work(char *s,int j,int n,int u,int sum)
{
	int x,y,z,c;
	push(u);
	split_siz(rt,id[u]-1,x,y);
	split_siz(y,len[u],y,z);
	int now=id[u]+len[u]-1;
	ff(i,j,n)
	{
		now++;
		c=s[i]-'a';
		ne[u][c]=++tot;
		u=ne[u][c];
		rnd[u]=rand(); mx[u]=val[u]=sum;
		siz[u]=1; ch[u][0]=ch[u][1]=0;
		id[u]=now; len[u]=n-i;
		y=merge(y,u);
	}
	int ans=u;
	u=1;
	fo(i,0,j)
	{
		c=s[i]-'a';
		len[u]+=n-j;
		u=ne[u][c];
	}
	rt=merge(x,merge(y,z));
	split_siz(rt,Rank(tot),x,y);
	DEBUG(siz[y]);
	pushid(y,n-j);
	rt=merge(x,y);
	return ans;
}
int value[N];
inline int ins_str(char *s)
{
	int n=strlen(s),c,u=1,sum=0;
	ff(i,0,n)
	{
		c=s[i]-'a';
		sum+=value[u];
		if(!ne[u][c]) return work(s,i,n,u,sum);
		u=ne[u][c];
	}
	return u;
}

inline void ins_val(int u,int v)
{
	value[u]+=v;
	push(u);
	int x,y,z;
	split_siz(rt,id[u]-1,x,y);
	split_siz(y,len[u],y,z);
	pushtag(y,v);
	rt=merge(x,merge(y,z));
}

int va[N],str_end[N];
int n,m,opt;
int main()
{
	srand(20030403);
	init();
	static char a[N];
	opt=read()-1;
	n=read(); m=read();
	fo(i,1,n) scanf("%s",a),str_end[i]=ins_str(a);
	fo(i,1,n) va[i]=max(0,read()),ins_val(str_end[i],va[i]);
	int x,v,ans=0; char t[10];
	fo(i,1,m)
	{
		scanf("%s",t);
		if(t[0]=='Q') printf("%lld\n",ans=mx[rt]);
		else
		{
			x=read();
			if(t[1]=='v')
			{
				v=read();
				if(opt) v=min(1000,v+(ans%1000));
				v=max(0,v);
				ins_val(str_end[x],v-va[x]);
				va[x]=v;
			}
			else
			{
				ins_val(str_end[x],-va[x]);
				scanf("%s",a); v=ans%26;
				if(opt) ff(i,0,strlen(a)) a[i]=(a[i]-'a'+v)%26+'a';
				str_end[x]=ins_str(a);
				ins_val(str_end[x],va[x]);
			}
		}
	}
	return 0;
}