[Nowcoder Multi Univerisity Training 2J]Subarray

Solution

可能作为区间端点的点个数最多为3e7
f[i]表示以第i个区间右端点为答案右端点的最大区间和
g[i]表示以第i个区间左端点为答案左端点的最大区间和
f[i]=\max(0,f[i−1]−(l[i]−r[i−1]−1))+r[i]−l[i]+1
g[i]=\max(0,g[i+1]−(l[i+1]−r[i]−1))+r[i]−l[i]+1
如果f[i]+g[i+1]≥l[i+1]−r[i]−1,说明答案的左右端点可以跨越[r[i]+1,l[i+1]−1],那么把这些合并考虑
搞完上面,问题就变成了给你若干个长度和不超过3e7的(1,−1)序列,问有多少区间和大于1
然后就好做了

发表评论

电子邮件地址不会被公开。 必填项已用*标注