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

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

Michael_Bryant最喜欢的番剧

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

Michael_Bryant正在看的番剧

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

bzoj 5145: [Ynoi2018]未来日记

题目链接

传送门

Description

所以说,小雪的未来是由乃的~

嗯...我知道你的未来会怎样
听好吧,我妻由乃

因为小雪改变了未来,所以他们三人才能在一起...
为什么...
这样我简直就是坏人...

我不会刺的
因为...这就是未来啊
这里...就是我的家

我妻由乃给了你一个长为n的序列a,有m次操作
1.把区间[l,r]内所有x变成y
2.查询区间[l,r]内k小值

Input

第一行两个数n,m
第二行n个数表示序列a
后面m行
1 l r x y : 把区间[l,r]中所有x变成y
2 l r k : 查询区间[l,r]中的k小值
1 <= n , m , ai <= 100000
共10组数据

Output

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

Sample Input

3 3

2 3 3

2 1 3 1

1 1 3 3 1

2 1 3 2

Sample Output

2

1

想说的话

跟五彩斑斓的世界不同
这个番很虐了
26集
挺好看的 看看病娇的典型代表

从颜值来讲当然是没有那么出色了。。。
不过未来日记这部番好看啊

想说的话(II

这题是神题
看看出题人/再见
By f321dd & nzhtl1477 & Claris

题解

不看题解根本没思路系列
我们用分块的思想
对权值和序列都分块,假设n和值域同阶记b[i][j]表示前i块,权值在第j块的有几个记c[i][j]表示前i块,权值为j的有几个
然后查询就暴力查询
修改的话两边的暴力重构
中间的只针对x,y这两个值修改b数组c数组的值
然后可以用一个反向数组存一下反id
就是说一个数的id是什么
然后这个带着修改

代码

写在最后

由乃其实挺可爱的
只不过不是我的菜好了

Add a Comment

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

隐藏