题目背景
注意:本题时限修改至250ms,并且数据进行大幅度加强。本题强制开启O2优化,并且不再重测,请大家自己重新提交。
由于Y校的老师非常毒瘤,要求zhouwc在csp考前最后3天参加期中考,zhouwc非常生气,决定消极考试,以涂完卡但全错为目标。现在retcarizy看zhouwc太可怜了,想要帮zhouwc解决一个问题,但他自己又太忙了,咕咕咕,于是就把问题甩给了你。
题目描述
给你一个长度为n的字符串S。
有m个操作,保证m≤n。
你还有一个字符串T,刚开始为空。
共有两种操作。
第一种操作:
在字符串T的末尾加上一个字符。
第二种操作:
在字符串T的开头加上一个字符。
每次操作完成后要求输出有几个l∈[1,T.size]满足以下条件:
对于∀i∈[1,l]有TT.size−l+i=Si
Tip:字符串下标从1开始。T.size表示T的长度。
输入格式
第一行两个正整数n,m。
第二行n个正整数,用空格隔开,第i个整数表示Si。
接下来m行,每行两个数字opt,ch,opt=0表示在T的末尾加一个字符ch,opt=1表示在T的开头加一个字符ch。
输出格式
共m行,每行一个非负整数表示第m操作后的输出。
提示
注意:本题采用捆绑测试,只有当你通过一个subtask的所有点后,你才能拿到这个subtask的分数
对于所有的数据 n≤106,m≤3.3333×104,∣∑∣≤103,Si∈[1,∣∑∣]。(∑表示字符集)
subtask1(17%):m≤333
subtask2(33%):m≤3333
subtask3(20%):∣∑∣≤2
subtask4(30%):无特殊条件
样例解释:
第一次操作后,T="1",
l=1时T[1]=S[1],所以答案为0
第二次操作后,T="21",
l=1时,T[2]=S[1]
l=2时,T[1]!=S[1],T[2]!=S[2]所以答案为1
第三次操作后,T="213",
l=1时,T[3]!=S[1];
l=2时,T[2]=S[1];
l=3时,T[3]=S[3]所以答案为1