luogu#P5640. 【CSGRound2】逐梦者的初心

    ID: 9662 远端评测题 250ms 500MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>动态规划dpO2优化状态压缩状压位运算按位洛谷月赛

【CSGRound2】逐梦者的初心

题目背景

注意:本题时限修改至250ms,并且数据进行大幅度加强。本题强制开启O2优化,并且不再重测,请大家自己重新提交。

由于Y校的老师非常毒瘤,要求zhouwc在csp考前最后3天参加期中考,zhouwc非常生气,决定消极考试,以涂完卡但全错为目标。现在retcarizy看zhouwc太可怜了,想要帮zhouwc解决一个问题,但他自己又太忙了,咕咕咕,于是就把问题甩给了你。

题目描述

给你一个长度为n的字符串S。

有m个操作,保证mnm\le n

你还有一个字符串T,刚开始为空。

共有两种操作。

第一种操作:

在字符串T的末尾加上一个字符。

第二种操作:

在字符串T的开头加上一个字符。

每次操作完成后要求输出有几个l[1,T.size]l \in [1,T.size]满足以下条件:

对于i[1,l]\forall i \in [1,l]TT.sizel+iSiT_{T.size-l+i} \ne S_{i}

Tip:Tip:字符串下标从1开始。T.sizeT.size表示T的长度。

输入格式

第一行两个正整数n,mn,m

第二行n个正整数,用空格隔开,第ii个整数表示SiS_i

接下来mm行,每行两个数字opt,chopt,chopt=0opt=0表示在T的末尾加一个字符chch,opt=1opt=1表示在T的开头加一个字符chch

输出格式

mm行,每行一个非负整数表示第m操作后的输出。

10 3
1 2 3 1 2 3 2 3 2 3
0 1
1 2
0 3
0
1
1

提示

注意:本题采用捆绑测试,只有当你通过一个subtask的所有点后,你才能拿到这个subtask的分数

对于所有的数据 $n \leq 10^6,m \leq 3.3333 \times 10^4,|\sum|\leq10^3,S_i \in [1,|\sum|]$。(\sum表示字符集)

subtask1(17%)(17\%):m333m \leq 333

subtask2(33%)(33\%):m3333m \leq 3333

subtask3(20%)(20\%):2|\sum|\leq2

subtask4(30%)(30\%):无特殊条件

样例解释:

第一次操作后,T="1"T="1",

l=1l=1T[1]=S[1]T[1]=S[1],所以答案为0

第二次操作后,T="21"T="21",

l=1l=1时,T[2]=S[1]T[2]=S[1]

l=2l=2时,T[1]!=S[1]T[1]!=S[1],T[2]!=S[2]T[2]!=S[2]所以答案为1

第三次操作后,T="213"T="213",

l=1l=1时,T[3]!=S[1]T[3]!=S[1];

l=2l=2时,T[2]=S[1]T[2]=S[1];

l=3l=3时,T[3]=S[3]T[3]=S[3]所以答案为1