Michael_Bryant最喜欢的G(al)G(ame)

那些悲伤,那些寂寞,那些几乎让自己放弃生活的希望的痛苦的回忆,绝对绝对不要将它们忘记。

Michael_Bryant最喜欢的番剧

抱歉⋯我已经绝对不可能再获得幸福了,因为⋯我发现⋯ 其实我⋯ 早就已经被幸福包围了

Michael_Bryant正在看的番剧

死亡一点也不温柔,只有无尽的黑暗和孤独。 就算联系得再紧密,人也是孤独的。

bzoj 5143: [Ynoi2018]五彩斑斓的世界

写在前面

真红是我的
二阶堂真红是我的!!!!!

题目链接

传送门

Description

......羽毛
从天而降的羽毛
如雪一般的纯白,
在海风中摇曳,
在凉风中舞动,
仿佛要将谁的心带走一样--

不可原谅
我......
......我、绝对、不会原谅你
现在、就出发......
我一定......一定要,把你......!

实现愿望。
只留下这个事实,然后我们两人就会分别。
就是希望着这一点,我们才会两个人一起走到今天。
是这样吧?

来,出发吧,去选择那独一无二的明天

二阶堂真红给了你一个长为n的序列a,有m次操作
1.把区间[l,r]中大于x的数减去x
2.查询区间[l,r]中x的出现次数

Input

第一行两个数n,m
第二行n个数表示序列a
所有输入的数都在[1,100000]内,后面m行
1 l r x : 把区间[l,r]所有大于x的数减去x
2 l r x : 查询区间[l,r]内的x的出现次数
共10组数据,所有输入的数都在[1,100000]内

Output

对于每个询问,输出一个数表示答案

Sample Input

5 6

1 5 5 5 8

2 2 5 5

1 2 4 3

2 2 5 2

2 2 5 5

1 3 5 1

2 1 5 1

Sample Output

3

3

0

3

想说的话

以后提到五彩斑斓的世界
请先想到Favorite的游戏
再想到5143
然后实力推荐Favorite三部曲
五彩斑斓的世界
五彩斑斓的曙光
你朱眸中的五彩世界
给几张图

来自五彩斑斓的曙光

来自你朱眸中的五彩世界

好了好了不多说了
我爱真红你们都懂

题解

这个题是神题
呈现给我们的是两种帅气的区间操作
区间操作我们无非想到线段树 树状数组或者是分块
你想啊
线段树好像还没见过有关大于某个数的问题
树状数组更别谈了
所以说分块更切实可行
怎么分块呢
block=sqrt(n)
这个自然不用多说
然后对于第一种操作 把所有大于x的数减去x
这个怎么办呢
区间减法打标记
显然不可直接打标记维护
因为你要找的数太tm有特点了
考虑个数据结构
可以把一个块内 值相同的数 连在一起处理
ufs啊对吧
记录每个块内每个数值第一次出现的位置
维护一下每个块内每个数出现次数
修改的时候只需要把对应ufs合并
查询的时候直接查询就成
这是操作1
想一想 时间20s20个点挺虚的
所以我们考虑优化这个修改
怎么优化呢
当我们发现这个区间内的数大于x较多的时候
我们就考虑对于小于x的数做文章
我们把所有小于x的数加上x
然后块内减去x
这样巧妙优化了复杂度
当然了查询就是非常基本的查询
先查两边零散的
再查中间整块的
就搞定了

强调

所有的卡常技巧能用就用吧
数组别开太大
这两个东西卡的太死了
开正好的将将就就能过去

代码

写在最后

引用几句真红的名言吧
那些悲伤 那些寂寞 那些几乎让自己放弃生活的希望的痛苦的回忆 绝对绝对不要将它们忘记 要相信 明天的世界 更加五彩斑斓
————二阶堂 真红
然后
祈祷明天对于我们所有人又是幸福的一天 明天邂逅更加美好的事情 我 在此祝福

One Comment

Add a Comment

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

隐藏