先考虑\(a\leq 2\)。
\(g\)值为\(1\)的区间可以从原数列中删除。
显然如果两个区间\(a1\)包含\(a2\)，则\(a1\)是无用的，把它去掉。
去掉无用的区间的过程显然可以使用单调栈维护。
剩余的区间肯定没有包含关系。
把所有区间按照左端点从小到大排序，则右端点也是递增的。
考虑离散化，从左到右dp。发现我们如果方案合法，则任何时候被覆盖的一定是一段前缀。
设\(f_{i,j}\)表示dp到第\(i\)个段，排序后\([1...j]\)被覆盖的方案数。
令\(t_{i,j}\)表示如果\([1...j]\)被覆盖，接下来在\(i\)位置填2的方案数。
如果填入后不连续则\(t_{i,j}=-1\)
显然\(t_{i,}\)可以使用双指针预处理。
当前位置填\(2\)，假如当前段长度为\(len\)，则根据补集转化方案数为\(2^{len}-1\)。
当前位置填\(1\)，则方案数为\(1\)
预处理转移系数，时间复杂度\(O(n^2)\)
再考虑原问题。
注意到两个相交区间\([l1,r1],[l2,r2]\)，假设第一个的值为\(a\)，第二个值为\(b\)，\(a<b\)
则可以把第二个区间调整到与第一个区间不相交，答案不变。
所以考虑对于所有值相同的区间计算答案，然后删除这些区间在原数列覆盖的位置后计算值更大的区间，再把每种值的区间的答案乘起来。
假设当前处理区间值为\(v\)，会发现转移系数或者为\(g^{len}-(g-1)^{len}\)或者\((g-1)^{len}\)。
预处理转移系数，时间复杂度还是\(O(n^2)\)
原文：https://www.cnblogs.com/ctmlpfs/p/14339062.html