C++编程 翻硬币

2024-11-24 14:36:00
推荐回答(1个)
回答1:

这题显然在线不可做,我们考虑离线,将所有操作保存下来,并且差分,把一次[l,r]取反变成两次[0,l-1]和[0,r]取反,记录在数组里,因为取两次反和不取反是一样的,且取反先后顺序没有影响,这样我们从0开始往后扫,扫到一个端点时,如果它之后(包括它自己)有偶数次操作,continue,否则将它和上一端点之间的位置取反。每个位置只会被取反一次所以是O(n)的