C/C++教程

题解 Cicada 拿衣服

本文主要是介绍题解 Cicada 拿衣服，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

传送门

神仙题！ 听@Yubai给我讲了半个下午，快%@Yubai

  • 见到这些奇奇怪怪的题是不是应该试着证下状态数上界啊

首先观察题目里给的柿子，可以发现 \(or-and\) 单调增， \(min-max\) 单调减
神仙思路，发现对于一个给定的左端点，我怀疑出题人是左撇子，不同的 \(or-and\) 最多只有 \(2logn\) 个，证明应该很简单
那尝试把这些 \(or-and\) 相同的区间拎出来，从右向左枚举区间，在区间内二分可得合法的最远右端点
然后问题来了：如何 \(O(1)\) 维护出这些区间
神仙思路，考虑什么是这些区间的边界，会发现一个数是边界当且仅当这一位上出现了之前没有在这一位上出现过的数
也即比如左边界上第 \(i\) 位是1，那向右找到第一个这一位上是0的数，那个数就会是一个边界
这个可以维护出一个next0和一个next1单调指针，每次排个序处理
然后区间最值，区间与或都需要 \(O(1)\) 出，都可以用ST表

  • 所以满足区间可重性的东西都可以用ST表？

然后区间取max，可以

这篇关于题解 Cicada 拿衣服的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航