网站建设费是几个点的税,学网站建设难吗,湖州建设局网站,莞城最新通告CF896E Welcome home, Chtholly
对于给定一个长度为n(n1e5)的序列#xff0c;值域范围为1e5,要求支持两类操作。
将区间[l,r]内所有大于x的数减x查询区间[l,r]内值为x的数的个数
首先由于n和值域同阶#xff0c;所以我们应该在值域上进行操作#xff0c;但是这个东西…CF896E Welcome home, Chtholly
对于给定一个长度为n(n1e5)的序列值域范围为1e5,要求支持两类操作。
将区间[l,r]内所有大于x的数减x查询区间[l,r]内值为x的数的个数
首先由于n和值域同阶所以我们应该在值域上进行操作但是这个东西不好用线段树的结构维护因为它的修改比较独特我们难以标记下传的方式处理。
但是我们可以使用分块暴力处理然后因为操作一的复杂度与值域有关我们可以看出来因为只有减操作所以最大值一定是单调递减的然后我们可以做到维护值域然后复杂度就可以做到O(n*\sqrt(n))所以我们要尽量调整块的个数尽量少所以就不能使用线段树这样的分治结构了。
然后我们考虑复杂度当x2mx的时候我们可以让块整体左移相当于0点右移然后只用处理O(x)的值域即可当x2mx时我么可以处理O(mx-x)的值域然后整体就是用O(x)的复杂度使得最大值减少了O(x)所以复杂度是正确的。 然后对于零散块个数不超过O(\sqrt(n))所以可以暴力重构。
然后我们考虑一种数据结构可以做到O(1)合并O(1)查询大小显然可以使用并查集。
然后还有一个trick就是我们可以单独考虑每一个块的贡献这样可以将空间复杂度降低。
这道题维护时移动零点的trick很重要可以实现O(1)整体移动然后通过判断我们就可以做到O(x)处理O(x)
