首页 > 一道简单题
开通博客写题解
头像 pvzelyyds
发表于 2021-12-12 19:43:42
B 一道简单题 一个ST表的题解 显然题目询问的那个东西有前缀和的性质 即T(l,r,x)=T(l,x,x)−T(r+1,x,x)T(l,r,x)=T(l,x,x)-T(r+1,x,x)T(l,r,x)=T(l,x,x)−T(r+1,x,x) 令ansi=T(1,i,i),f(l,r)ans_i=T 展开全文
去ta的博客 赞 (9) 回复(0) 收起
头像 yangjl⁣⁣⁣⁣
发表于 2021-12-14 16:53:27
一道简单题 线段树题解 对于每次查询的T(l,r,x)，暂时不看第三个参数，即 Q(l,r)=∑i=lr\sum_{i=l}^{r}∑i=lr​ max(a[i],a[i+1],…,a[r]). 每个位置对答案有个贡献且这个贡献等于[i,r]这段区间中a的最大值所以 左边的a[j] (j< 展开全文
去ta的博客 赞 (2) 回复(0) 收起
查看本题
查看本题讨论

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”