爱彼迎电面遇到较难题

上周面的。
题目如下：
输入正整数N，表示有N个灯泡排成一列，每个灯泡可以亮可以灭，初始假设全灭。
要求实现两个操作：
1. toggle(a, b), 0 <= a <= b <= N-1
表示将第a个

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

一定会出面经题。放上来提醒大家还是要尽量全面复习，像我虽然复习了线段树现场也写完了，但是忘记了lazy update仍然失败了，大家要引以为戒。

拍脑袋想Segment tree和Fenwick tree都超纲了。
可以用平衡树。一个记录起点，一个记录终点。插入log(n)复杂度。
在平衡树结点上维护大于或小于本结点的计数，就可以log(n)复杂度查询有多少段已经开始还没有结束。通过奇偶判断这个灯的状态。
不过平衡树当场基本写不出来，估计写个二叉树，解释下就可以了。

ND0406 发表于 2021-5-30 06:39
你这个On是每个query都是On update O1
换句话说 query是N 就成了n平方了 肯定是不对的

能讲讲是lc 哪题吗？ 怎么用BIT 实现的思路呢？ 怎么做range update 在logN？

lazy tag的线段树感觉还是可以handle的，区间BIT我觉得就有点太取巧了。。。

lc的原题吧…

ND0406 发表于 2021-5-27 09:48
lc的原题吧…

求题号？

天啊

扫描线可以做不？

扫描线，起点+1，终点-1，然后重新扫一遍过去，遇到奇数是1偶数是0，On解决

匿名用户 发表于 2021-05-26 18:52:25
求题号？

抱歉回复完了。
就是BIT的题。
每次update是 2个logn
求具体某个点的时候是一个logn
你等我给你找下类似的…这题我太有印象了…

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

区间操作变成点操作然后使用树状数组的题。出这个题coding有点过分。