成功用二维树状数组卡过本题。

P3157 [CQOI2011] 动态逆序对

首先你加自定义哈希函数没?没有的话建议加了再测一下 然后我之前试了这种写法可以以大概700ms最大点的速度通过P3810,但是我测了一下在那题里`unordered_map`T成狗,要`gp_hash_table`。
by fangzichang @ 2023-11-16 13:45:15


然后这也是树套树啊。
by fangzichang @ 2023-11-16 13:46:06


@[fangzichang](/user/678087) 是因为 `gp_hash_table` 默认不能良好地处理 `unsigned long long` 键值吗?经测试,向其中插入元素的速度肉眼可见地在变慢。(能不能给个自定义哈希函数的博客链接?球球。) 二维树状数组确实可以理解成“树状数组套树状数组”,但是这里不把它理解成树套树是因为:①二维树状数组不存在谁套谁的问题,维度互换并无本质差别(`i`,`j` 枚举顺序翻过来也无影响),可以当成一个不区分的整体来看待;②二维树状数组的实现难度上比其他树套树更简单,不需要区别低层树和高层树。
by Terrible @ 2023-11-16 14:12:34


@[Terrible](/user/195942) 那个OI-Wiki上有,在无序关联式容器页面。 然后我感觉这个还是很树套树。 然后`std::hash`什么的若智实现用不了一点,没多少参考价值。
by fangzichang @ 2023-11-16 14:25:16


|