← 返回题目

题库练习「SDOI / SXOI2022」无处存储

← 上一题下一题 →

A6595 | $「SDOI / SXOI2022」无处存储$

时间限制4s

内存限制64MB

通过 / 提交0/0

题目描述

小 Ω 想出一个数据结构题，于是它先造了一棵点有点权的树： 给定一棵大小为 $n$ 的树，编号 $1$ 到 $n$，第 $i \in [2,n]$ 个点的父节点记作 $f_i \in [1, i-1]$。另外，每个点 $i$ 有一个点权 $a_i$​，初始点权由输入确定，具体方式见输入格式。 在数据结构题里面，需要有对应的修改和查询的操作，而树上最简单的两种非平凡操作当然是链加、链求和了。 因此你需要支持以下两种操作： ``0 x y v``：将树上从 $x$ 到 $y$ 的简单路径上的点的权值增加 $v$； ``1 x y``：求树上从 $x$ 到 $y$ 的简单路径上的点的权值和； 出完之后小 Ω 拿给小 N 看，小 N 表示： ……这也太简单了，这不是轻重链剖分模板题吗？！！ 小 Ω 于是想到在刚刚接触 OI 的时候了解到的时间换空间的原理，因此他决定本题的空间限制为 **64 MB**。

输入格式

第一行输入三个正整数 $id, n, q$，其中 $i d$ 为子任务编号，和四个非负整数 $A,B,C,a_{0}$。 $A,B,C,a_{0}$ 用于生成点权 $a_{1}, a_{2}, \ldots, a_{n}$，具体方法是按照下式进行递推: $$ a_{i}=\left(A a_{i-1}^{2}+B a_{i-1}+C\right) \bmod 2^{32} $$ 接下来一行 $n-1$ 个正整数表示 $f_{2}, \ldots, f_{n}$。 接下来 $q$ 行，每行若干整数，形如 ``0 x y v` 或者 `1 x y``，表示一次修改或查询。 其中 $x^{\prime},y^{\prime},v^{\prime}$ 用于强制在线，实际操作的 $x=x^{\prime} \operatorname{xor} P, y=y^{\prime}\operatorname{xor}P,v=v^{\prime}\operatorname{xor}P$，其中 ``xor` 是 `C/C++` 中的按位异或运算符 `^`，$P= \mathrm{lastans}\ \& \left(2^{20}-1\right)$，其中 $\mathrm{lastans}$ 为上一次询问的答案（没有上次询问则记为 $0$），$\&$ 为 `C/C++` 中的按位与运算符 `&``。

输出格式

若干行，依次输出每个询问的答案对 $2^{32}$ 取模后的结果。

输入输出样例

输入 #1

0 10 10 935995202 406705156 7034169 418665824
1 1 1 1 1 1 1 7 2
0 10 3 781084039
1 7 5
0 897574 897583 833116301
1 897583 897572
0 886189 886179 123805569
1 886182 886190
1 145142 145136
1 854537 854538
1 896515 896525
0 879409 879412 746499584

输出 #1

C++ 编辑器

输入

输出