TDOG模拟 #4 密码门
密码门(cipher)
题目描述
为了防止秘密情报泄露,Kiana决定在基地内加装\(n\)道密码门,每道密码门可以对输入的数字做一定计算,并将结果输出给下一道密码门作为输入。只要Kiana对比入口处输入的数字经过所有密码门后的结果,就可以判断出来者是否掌握真正的密码。
具体而言,第\(i\)道密码门有一个操作符\(OP_i\)和一个参数\(B_i\),其中操作符分为三种:AND、OR和XOR,分别表示该密码门会将输入的数字与\(B_i\)进行按位与、按位或、按位异或后进行输出。按位与对应C++中的\('\&'\)运算符,按位或对应C++中的\('|'\)运算符,按位异或对应C++中的\('\^{}'\)运算符,你可以分别用表达式\('a\&b'\)、\('a|b'\)和\('a\^{}b'\)计算两个数\(a\)和\(b\)进行按位与、按位或、按位异或运算的结果。
为进一步保证安全,在某些时刻,Kiana还可能修改某些密码门的操作符和参数。基地中按时间顺序共发生了\(m\)个事件,每个事件可能为有人在基地门口输入了一个数字,或者Kiana修改了某一道密码门的操作符和参数。
对于每个输入数字事件,虽然密码门可以自动计算出结果来,但Kiana还是希望提前知道该数字依次通过所有密码门后的结果是什么,以便针对特殊情况做出预警。由于Kiana自己不会算,所以希望你能够帮助她。
输入输出格式
输入格式
第一行包含两个正整数\(n\)和\(m\),分别表示密码门的数量与发生的事件数。
接下来\(n\)行,第\(i\)行包含一个字符串\(OP_i\)和一个正整数\(B_i\),分别表示初始时第\(i\)道密码门的操作符和参数。
接下来\(m\)行,每行首先包含一个正整数\(type\),若\(type=1\),则后面跟一个正整数\(X\),表示有人在门口输入了数字\(X\),你需要计算\(X\)依次通过所有密码门后的结果;若\(type=2\),则后面跟一个正整数\(id\)、一个字符串\(OP'\)和一个正整数\(B'\),表示Kiana将第\(id\)道密码门的操作符改为了\(OP'\),参数改为了\(B'\)。
数据保证输入中的字符串均为'AND'、'OR'或'XOR'中的一种,其分别对应这道密码门进行按位与、按位或、按位异或运算。
输出格式
对于每个输入数字事件,输出一行一个正整数,表示基地门口输入的数字依次通过所有密码门后输出的结果。
输入输出样例
输入样例#1:
3 3
XOR 11
AND 7
OR 17
1 13
2 2 AND 15
1 5
输出样例#1:
23
31
输入样例#2:
输出样例#2:
样例解释
Kiana一共加装了\(3\)道密码门,初始时密码门的操作符和参数依次为\(XOR\,11\)、\(AND\,7\)和\(OR\,17\),按时间顺序发生了\(3\)个事件如下:
有人在门口输入了数字\(13\),而\(13\,XOR\,11=15\)、\(15\,AND\,7=7\)、\(7\,OR\,17=23\),故最终密码门输出的结果为\(23\)
Kiana将第\(2\)道密码门的参数改为\(AND\,15\)
有人在门口输入了数字\(5\),而\(5\,XOR\,11=14\)、\(14\,AND\,15=14\)、\(14\,OR\,17=31\),故最终密码门输出的结果为\(31\)。
数据范围
对于\(20\%\)的数据,保证\(1\leq n,m\leq 2000\)。
对于\(60\%\)的数据,保证\(1\leq n,m\leq 20000\)。
对于\(100\%\)的数据,保证\(1\leq n,m\leq 2\times 10^5,1\leq type\leq 2,1\leq B_i,B',X\leq 1000,1\leq id\leq n\)。
在后两档数据中,各有三组数据没有发生过Kiana修改密码门的事件,好各有三组数据所有的操作符都是相同的.
信息
- ID
- 1017
- 难度
- 9
- 分类
- (无)
- 标签
- 递交数
- 21
- 已通过
- 2
- 通过率
- 10%
- 上传者