类似分成一些矩形(类似笛卡尔树）
把条件放在矩形上（条件桶排放进高度，然后往上扫即可）
然后树形DP
f[x][0/1]以x为根的子树，是否灌满水的最大收益
不灌满的话，直接把这个矩形从下往上扫一遍即可
法二：
dp[i][j]前i个柱子，最后一个灌了j的水的最优值（不管第i个柱子的后面位置的高度）
设i个柱子左边的板长度为j
dp[i][j]=max(dp[i-1][k])+sum[i][j] (j<=h&&k<=h)
dp[i][j]=dp[i-1][j]+sum[i][j] (j>h)
sum[i][j]表示i位置高度为j的收益
线段树维护j那一维，维护区间最大值，区间加，区间对一个数取max。j和h的不同分别处理即可。
总字符串长度是1e5，长度都是k，有q个询问
qk<=1e5
然后就是分块乱搞了
1.k<=sqrt(1e5):
vector[l][r]表示，左端点在l，右端点在r的询问
询问放进去
枚举w的所有子串，用hash找到出现次数，vector[l][r]二分找到[a,b]之间的询问个数作为系数乘上去
或者，
S建SAM，枚举w的k个li，往上面跑，跑一步到了ri，vector[li][ri]类似上面的二分即可。
2.q<=sqrt(1e5)
先把m个区间在右端点的位置放进vector：
对S建SAM，然后w在上面匹配，如果当前r位置有询问，就倍增找到，right集合大小就是ans
O(m+qklogn)
原文：https://www.cnblogs.com/Miracevin/p/10437353.html