1 solutions

  • 1
    @ 2024-12-18 11:50:41

    提示:

    每次查询时,如果要跟踪某一行中 1100 的变化情况,不必查看整行。只需查看相邻的几个单元格即可。

    题解:

    首先,让我们暴力地计算一下 countcount - 1100 在 ss 中出现的次数。

    然后,对于每个 qq 查询,我们都将更新 countcount :

    考虑更改 sis_i 之前的子串 s[max⁡(1,i−3);min⁡(i+3,n)]s[\max(1, i - 3); \min(i + 3, n)] 并找出 beforebefore - "1100 "在其中出现的次数。然后更新 si=vs_i = v ,同样找到 afterafter - 应用查询后 "1100 "在 s[max⁡(1,i−3);min⁡(i+3,n)]s[\max(1, i - 3); \min(i + 3, n)] 中出现的次数。

    注意到 count=count+(after−before)count = count + (after - before) ,我们可以得到在应用查询后,"1100 "在 ss 中出现的次数。如果 count>0count > 0 ,则查询的答案为 "YES",否则为 "NO"。

    最终的时间复杂度为: O(∣s∣+q)O(|s| + q) 。

    • 1

    Information

    ID
    29
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    —
    Tags
    # Submissions
    9
    Accepted
    1
    Uploaded By