[Description]

zsl是MZOI 2012级的信奥班成员,银牌爷。

zsl最近想到一个奇怪的事情:用字符串作为数组下标。

当然这不是什么难事,map<string, int>就可以了。但是这么简单的方法怎么能满足zsl神犇的胃口?!所以他提出了三个操作(保证字典序str1≤str2,i为整数):

  1. I str i:设置下标为str的数组元素的值为i,如果下标为str的数组元素不存在,则插入一个下标为str的数组元素。
  2. Q str1 str2:询问下标的字典序大于等于str1并且小于等于str2的所有数组元素的和。
  3. A str1 str2 i:给每一个下标的字典序大于等于str1并且小于等于str2的数组元素加i。

这种简单题zsl神犇并不认为需要他自己来写,于是变成了你的作业。

为了安慰你,zsl神犇把字符集缩小到了'0'~'9'。但是,zsl神犇同时发现这道题有一个问题,那就是可以先读入所有出现过的字符串,然后排序,这道题就变成了一道很弱的线段树。因此,他决定强行实现在线算法。对每个出现的字符加上上一次询问的结果再取模10(如果以前还没有任何询问,则不做处理)。例如上一次询问的结果是63,那么输入数据里的字符串“38481”事实上的含义是“05158”

注意字典序的比较方式:从左到右按位比较,第一个不同的位小的字典序在前,空字符小于任何字符。例如:"aaa" < "aaaz" < "aab" < "aabd" < "b" < "zdfdg" < "zdfe"。

请只看下图的最后一行:

字符串总长度不超过400,000

来源

原创