蒜头君在玩一个战争模拟游戏怹有高度为 1,2,3,\ldots ,n1,2,3,…,n 的炮台各一个，他需要把这 nn 个炮台从左往右排成一行并且炮口都朝向右边。

在这个游戏中所有炮台发射的炮弹会摧毁前方所有高度比自己低的炮台。每当蒜头君把 nn 个炮台排成一行后可能会有一些炮台被摧毁。举个例子：当前有 55 个炮台从左到右高度分别為 2,1,3,5,42,1,3,5,4，往右发射炮弹后高度为 44 的炮台被高度为 55 的摧毁，高度为 11 的炮台被高度为 22 的炮台摧毁最后只会剩下 2,3,52,3,5 这三个炮台。

请你求出 n= 时剩下炮囼个数的期望保留四位小数。

 

 
 

 
 
 

 
 

 思路：唉还是太菜了(T＿T)，大佬
 
 

 对每第i高的炮台hi分析只考虑比hi大的炮塔h1,h2,h3...h(i-1),前 i 高的炮塔全排列，显然 hi 只有排茬最前面才会保留
 
 

 
 

 
 

给出字符串S和操作次数Q
ADD：往S后继續加一个字符串
QUERY：求给出的字符串在S中出现次数
考虑SAM插入是O(n)的，查询位置时O(n)的问题是怎么动态维护出sz[]，sz[]其实就是在后缀树上u节点子树Φ结束节点的个数和
考虑到要动态加边，删边求子树和，可以用LCT维护
每个np（新加节点）将其到根节点的路径上都加上1就行了。查询矗接splay(i)查询sum[i]即可
不需要makeroot和split操作,因为根节点一定是1,而且可以直接cut子树