TDOG模拟 #4 密码门

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:

cipher2.in

输出样例#2:

cipher2.ans

样例解释

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%
上传者