【题解】P5212 SubString

反正投不了了，随便写写（其实这是卡常记录）

算法

查给定字符串的出现次数常用 SAM，就是查 SAM 对应节点的 parent 树子树里有多少个主链上的节点，向后加字符串可以直接记录节点时间戳等实现。

但是这题有强制在线，所以要支持的操作就是在 parent 树上加点和更换父节点，查询子树和，显然可用 LCT，但也可以用平衡树维护 dfs 序实现，更换父节点即区间平移。

我写了个 fhqTreap，发现用它做这个常数比 LCT 还大，开 O2 都只有45pts。

考虑优化常数，对于新建节点原本是先直接并在 dfs 序的最后，找到父节点时再插到对应区间。于是新建节点时暂不加进平衡树，找到父节点了才直接加到父节点后面，于是就不开 O2 最劣解卡过了。

code

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define re register
typedef long long ll;
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return xy) x=y;}
inline void swp(int &x,int &y){x^=y^=x^=y;}

const int N=1200050;
int tot,la,ch[N][2],ml[N],fa[N],rt,ls[N<<1],rs[N<<1],pr[N<<1],sz[N<<1],sm[N<<1],v[N<<1],ff[N<<1];
char ss[N];

inline void mt(int &x){sz[x]=sz[ls[x]]+sz[rs[x]]+1,sm[x]=sm[ls[x]]+sm[rs[x]]+v[x],ff[ls[x]]=ff[rs[x]]=x,ff[x]=0;}
inline int merge(int x,int y){
	if(!x||!y) return x|y;
	if(pr[x]=k) b=x,split(ls[x],k,a,ls[x]);
	else a=x,split(rs[x],k-sz[ls[x]]-1,rs[x],b);
	mt(x);
}
inline int rk(int x){
	int s=sz[ls[x]]+1;
	for(;x;x=ff[x]) if(x==rs[ff[x]]) s+=sz[ls[ff[x]]]+1;
	return s;
}
inline int xl(int &x){return (x<<1)-1;}
inline int xr(int &x){return x<<1;}
inline void newf(int x,int y,int ssm){
	fa[x]=y,sz[xl(x)]=sz[xr(x)]=1,sm[xl(x)]=v[xl(x)]=ssm,
	pr[xl(x)]=rand(),pr[xr(x)]=rand();
	int a=merge(xl(x),xr(x)),b;split(rt,rk(xl(y)),rt,b);
	rt=merge(merge(rt,a),b);
}
inline void chf(int x,int y){
	fa[x]=y;int a,b;
	split(rt,rk(xr(x)),rt,b),split(rt,rk(xl(x))-1,rt,a),
	rt=merge(rt,b),split(rt,rk(xl(y)),rt,b),rt=merge(merge(rt,a),b);
}
inline void qry(int x,int &mask){
	if(x){
		int a,b;
		split(rt,rk(xr(x)),rt,b),split(rt,rk(xl(x))-1,rt,a),
		printf("%d\n",sm[a]),mask^=sm[a],rt=merge(merge(rt,a),b);
	}
	else putchar('0'),putchar('\n');
}
inline void build(int c){
	int p=la,x=++tot,q;ml[x]=ml[la]+1,la=x;
	while(!ch[p][c]&&p) ch[p][c]=x,p=fa[p];
	if(!p) return newf(x,1,1),void();
	if(ml[q=ch[p][c]]==ml[p]+1) return newf(x,q,1),void();
	newf(++tot,fa[q],0),newf(x,tot,1),chf(q,tot),ml[tot]=ml[p]+1,
	ch[tot][0]=ch[q][0],ch[tot][1]=ch[q][1];
	while(ch[p][c]==q&&p) ch[p][c]=tot,p=fa[p];
}
inline int walk(char *s,int n){int x=1;for(re int i=0;i
平衡树SAM字符串

相关

js 正则匹配 两个字符串之间，某个字符串之前（之后）的内容

大爽Python入门教程 1-2 数与字符串

Java21-统计字符串中每个字符出现的次数

全（十五）Jmeter 之 参数化 函数助手：__Random string（译：瑞德.丝锥）：随机字符串

生成随机字符串

09练习：统计输入的字符串中各种字符的个数

2-14str1转义字符，格式化_2-15str2格式化，字符串内置函数

python基本数据类型；关于字符串格式化的补充

Java基础-02 字符串(汉字)与16进制字符串转换(无乱码)

C语言判断给定的字符串是否为合法的ip地址的代码-C-J

把字符串a复制到字符串b，利用指针

javascript模板字符串（反引号）

标签