1 solutions
Information
- ID
- 29
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- —
- Tags
- # Submissions
- 9
- Accepted
- 1
- Uploaded By
提示:
每次查询时,如果要跟踪某一行中 1100 的变化情况,不必查看整行。只需查看相邻的几个单元格即可。
题解:
首先,让我们暴力地计算一下 count - 1100 在 s 中出现的次数。
然后,对于每个 q 查询,我们都将更新 count :
考虑更改 si 之前的子串 s[max(1,i−3);min(i+3,n)] 并找出 before - "1100 "在其中出现的次数。然后更新 si=v ,同样找到 after - 应用查询后 "1100 "在 s[max(1,i−3);min(i+3,n)] 中出现的次数。
注意到 count=count+(after−before) ,我们可以得到在应用查询后,"1100 "在 s 中出现的次数。如果 count>0 ,则查询的答案为 "YES",否则为 "NO"。
最终的时间复杂度为: O(∣s∣+q) 。
By signing up a wangzaioj universal account, you can submit code and join discussions in all online judging services provided by us.