A - 道路
首先，很容易想到一个 \(O(n^2 \times m + n\times m \log n)\) 的做法，可以枚举起点和终点以及那条边，预处理出 \(x,y\) 之间最短路以及最短路方案，就可以直接算。
考虑如何优化。
比如一条从 \(s\) 到 \(t\) 的最短路，假如它能有贡献的充要条件是 \(dis_{s,t}=dis_{s,x}+dis_{y,t}+edgedis_{x,y}\).
这有太多未知数了，不好计算，尝试将它分成两部分。
第一部分是这条边作为终止边，也就是只用考虑，有多少种不同的最短路终止为这条边。
第二部分同理，计算多少种不同的最短路起始为这条边。
计算这两个分别都是 \(O(n\times m)\) 的。
两部分答案相乘并不是最终答案。因为这个只满足两边分别成立，其实不满组整体成立。
所以还需要减去一些不满足 \(dis_{s,t}=dis_{s,y}+dis_{x,t}-edgedis_{x,y}\) 的，好像也不大好做。
回到第一个式子，\(dis_{s,t}=dis_{s,x}+dis_{y,t}+edgedis_{x,y}\)。
移项得，\(dis_{s,t}-dis_{s,x}=dis_{y,t}+edgedis_{x,y}\)
假如枚举边 \((x,y)\) 和终点 \(t\) ，只要能在 log 内求出有多少 \(s\) 满足 \(dis_{s,t}-dis_{s,x}=k\) 并算出 \(sum_{s,x}\)（sum 表示最短路方案数）。
看看这个能不能预处理，再移项得 \(dis_{s,t}=k+dis_{s,x}\)，
也做不了。
看了题解，可以枚举最短路的起点 \(s\)，将能跑出最短路的边使用，建出一个 DAG。接着可以分成两部分，分别表示在这个 DAG 中以 \(s\) 出发，到达 \(x\) 这个点的方案数，和从这个点出发到达任意一个终点的方案数。最后枚举边，将两个端点答案乘起来就可以了。
B - 影魔
枚举 \(c\)，计算出 \(c\) 为最大值的最远左端点 \(l\) 和最远右端点 \(r\)。
很显然，\(i\) 和 \(j\) 的范围也就确定了，\(i\in [l-1,c-1],j \in [c+1,r+1]\)，因为假如过了 \(l-1\) 和 \(r+1\)，\(c\) 就不是 \(\max_{i+1}^{j-1} a_i\) 了。
对于第一种 \(p1\) 的情况，也就是 \(c<\min(a_i,a_j)\)，这只能出现在 \(i=l-1,j=r+1\) 的时候。
而对于第二种 \(p2\) 的情况，即 \(\min(a_i,a_j)<c<\max(a_i,a_j)\)，这个同理，只有可能出现在 \(i=l-1,j\in[c+1,r]\) 或 \(j=r+1,i\in [l,c-1]\) 中。
二维区间修改，很容易想到二维线段树，暴力维护就可以了。
还需要考虑的是没有 \(c\) 的情况，也就是 \(j=i+1\) 时，加上一下 \((r-l)\times p1\) 就可以了。
但是二维线段树会 TLE+MLE，注意到可以离线，直接计算。
C - 带子串包含约束LCS问题
对于要包涵的建 AC 自动机，两个模式串分别建子序列自动机。
用 dfs(x,y,i,S) 表示匹配两个模式串到 \(x,y\)，AC 自动机在点 \(i\)，目前的状态为 \(S\) 的最长公共子序列。
记忆化搜索。证不出时间复杂度，\(O(能过)\)，好像 zzwdsj 造出到 hack 了？
总结
对于这种字符串的题，假如要包含若干个字符串为其字串，可以建 AC 自动机；而对于类似公共子序列可以分别建子序列自动机，记忆化搜索。
而这道题正是两个相结合。