TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P6858
  • 問題
  • P6858wxh loves substring
    制限 : 時間制限 : 10000 MS   メモリ制限 : - KB
    審判説明 : 1.5s,512m
    問題説明

    wxh太强了,他觉得你们太菜了,所以懒得写背景了,给你一个字符串init,要求你支持三个操作
    (1):在当前字符串的后面插入若干个字符
    (2):在当前字符串的后面删除若干个字符
    (3):询问字符串s在当前字符串中出现了几次?(作为连续子串) 你必须在线支持这些操作。

    入力形式

    第一行一个数Q表示操作个数
    第二行一个字符串表示初始字符串init
    接下来Q行,每行2个字符串Type,Str
    Type是ADD的话表示在后面插入。
    Type是DEL的话表示在后面删除。
    Type是QUERY的话表示询问某字符串在当前字符串中出现了几次。
    为了体现在线操作,你需要维护一个变量mask,初始值为0
    读入串Str之后,使用这个过程将之解码成真正询问的串TrueStr。
    询问的时候,对TrueStr询问后输出一行答案Result
    然后mask = mask xor Result
    插入的时候,将TrueStr插到当前字符串后面即可。
    HINT:ADD和QUERY操作的字符串都需要解压
    字符集大写字母
    数据字符串变化长度以及初始长度和 <= 800000,询问次数 <= 100000,询问总长度 <= 3000000

    出力形式

    若干行,每次询问输出一个整数,表示答案

    サンプル入力

    3
    A
    QUERY B
    ADD BBABBBBAAB
    DEL 1

    サンプル出力

    0


    ソース  bzoj4768