4023: Sky 不想做背包
内存限制：512 MB
时间限制：6.000 S
评测方式：文本比较
命题人：
提交：2
解决：1
题目描述
bag.in/out
Sky 在学习背包，他遇到了一个神奇的背包题。
这道题目的背包容量是无限的，对应的，这个背包对放入的物品的属性有一定的要求。
一共有 n 个物品，物品由 1 到 n 依次编号。每个物品都有两个属性，编号为 i 的物品的特征值为 ai
,
价值为 bi。 背包中可以装下无限个物品，但是当背包中的某些物品的特征值的异或和为 0 时，背包将
会爆炸。
更严谨地，我们用 S 表示背包中物品的集合， 我们定义 Xor(S) 表示集合中所有物品的特征值异或
和， 当 ∃S
′ ⊆ S, Xor(S
′) = 0 成立时，背包将会爆炸。
有 q 次询问或修改：
询问就是给出一段区间 [l, r]，询问在编号为 l, l + 1, ..., r − 1, r 的物品中选出一个子集，能获得
的最大价值是多少（只询问，不改变序列信息）；
修改就是修改某种物品的特征值和价值。
注意：如果背包爆炸，那么获得的价值为 −1。
输入
第一行，一个正整数 n
接下来 n 行，每行两个数字，第 i 行为 ai、 bi
接下来一行，一个正整数 q
接下来 q 行，每行的第一个数字是 t
如果 t = 0 表示查询，接下来给出两个数字，分别为 l, r，表示一次在区间 [l, r] 上的查询。
如果 t = 1 表示修改，接下来给出三个数字，分别为 x, a, b，表示把编号为 x 的物品的特征值修
改为 a，价值修改为 b。
输出
对每个询问输出一行，表示用查询区间中的物品能获得的最大价值。
样例输入 复制
5
1 2
2 1
3 2
4 1
5 2
5
0 1 5
0 2 4
0 3 5
1 5 5 10
0 1 5样例输出 复制
6
4
5
14提示
对于前20%的数据，n,q<=5
对于前40%的数据，n<=20 ，没有修改操作
对于前60%的数据，n,q<=1000
对于100%的数据，n<=10^5 ，q<=10^4,1<=ai,bi<=10^9
对于后60%的数据，修改与查询的出现概率都是1/2