首页 > 魔法学院(easy version)
开通博客写题解
头像 我是菜鸡小仙女
发表于 2021-11-13 07:56:47
题目描述 亚可喜欢上了收集不包括空格的可见字符(ASCII码为33~126)，在她眼中，一个字符的价值为其ASCII码大小，比如’a’的价值为97。 目前她已经收集了n个不包括空格的可见字符，第i个字符S[i]。可是她想要把自己收集的nn个字符的价值和最大化，因此去请求了戴安娜的帮助。戴安娜有m种魔 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 小小de风铃
发表于 2021-11-22 10:57:37
根据题目意思很容易就能明白，就是给一个序列，然后有 mmm 次区间修改，把区间[l,r][l,r][l,r] 内比 ccc 小的数全部改成 ccc ，最后求出序列的和。 第一眼看过去貌似线段树就可以水过去，然后写了半小时思路混乱放弃了（线段数还是学的太拉了）。 于是再仔细思考一下，它貌似只有一次查询 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 小琢卷不动
发表于 2021-11-13 09:01:02
每个位置有很多种放字符的方法，把初始的字符也离线下来，同时作为操作一起排序。 考虑到不管什么位置，我只要排过一遍序，后来者一定比先覆盖上去的严格不劣，所以直接进行区间覆盖单点查询即可。 代码实现细节的话也没啥好说的，就是无脑堆板子就好了。 时间复杂度 O(nlog⁡n)O(n\log n)O(nlo 展开全文
去ta的博客 赞 (1) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”