只有10分用树状数组做的看一下
查看原帖
只有10分用树状数组做的看一下
333147
AB_IN楼主2020/8/3 09:50

10分的可能和本菜鸡一样用的lower_bound搭配unique的离散化。但是这样的话,两个相同的元素,它们的大小顺序是相同的。

比如 3 3 5 6 8 -> 1 1 2 3 4

而我们实际需要的是 1 2 3 4 5。

其实wa9个点,有可能不是因为wa,而是因为tle了 (没看过数据,瞎猜的)

为什么呢?众所周知,这题的精华就在于新建数列,c[a[i] ]=b[i]c[a[i]]=b[i] 但比如用lower_bound+unique离散化后的数据为

a :1 1 2 3 4

b: 2 2 3 4 5

这样的话c数组是没有下标5的!!!这样就会绕进去。

所以可以选择用结构体离散化的方式,题解里基本都是这样的。

2020/8/3 09:50
加载中...