Description
小 $E$ 是一位实力强大的 $OIer$，经常在各类比赛中随手 $AK$ 虐场。然而她最近秒题时遇到了一道需要她思考 $15$ 秒才能做出的题目，整整花了 $15$ 倍于其他题目的时间。她认为这个问题十分有意思，并且对其进行了一些拓展和修改以后抛给了你。你能接受小 $E$ 的挑战吗？
设 $p_i$ 表示非负整数 $p$ 的二进制表示中在项 $2^i$ 前的系数，对于非负整数 $p$,$q$ ，可以定义二元运算 $xnor$（同或）为：$p\;xnor\;q=\sum^m_{i=0}{((p_i\wedge q_i)\vee(\neg(p_i\vee q_i)))\times2^i}$（在这里我们认为布尔表达式的值 $false$ 或 $true$ 能够直接对应于整数 $0$ 或 $1$ 并参与算术运算，反之亦然；其中 $M$ 为常数，本题中M 的取值为 $31$）。
给定一个长度为 $n$ 的非负整数序列 $a$ ，在序列的每个位置上有非负整数权值 $w_i$ ，现在希望实现对该序列的以下操作：
给 定 区 间 $[l,r]$ 和 非 负 整 数 $k$ ， 查 询。 $(\sum_{i=l}^r{a_i\times w’(i))xnor(\sum_{i=l}^r{a_i})}$
其中$w’(i)=\begin{cases}w_i,if \space w_i \le k \\ 0,if \space w_i>k \end{cases}$。
给定正整数 $p$ 和非负整数 $k$ ，将 $a_p$ 的值修改为 $k$ 。
给定正整数 $p$ 和非负整数 $k$ ，将 $w_p$ 的值修改为 $k$ 。
如果你不认识题目描述中的某些符号，可参见Hint部分。
Input Format
输入的第 $1$ 行包含两个整数 $n$,$q$ ，$n$ 表示序列长度，$q$ 表示操作次数。
接下来 $1$ 行，包含 $n$ 个整数，其中第 $i$ 个表示 $a_i$ 。
接下来 $1$ 行，包含 $n$ 个整数，其中第 $i$ 个表示 $w_i$ 。
接下来 $q$ 行，每行包含 $4$ 个或 $3$ 个整数，其中第 $1$ 个整数表示操作类型（见题目描述）。
对于第 $1$ 种操作，接下来 $3$ 个整数依次表示 $l$,$r$,$k$ ；对于第 $2$ 或第 $3$ 种操作，接下来 $2$ 个整数依次表示 $p$,$k$ 。
Output Format
对于每个第 $1$ 种操作输出一行一个整数，表示答案。
Input Sample
1 | 10 10 |
Output Sample
1 | 4294966372 |
Hint
【样例 $1$ 说明】
对于第 $1$ 次询问，$k=17$ ，此时在 $[2,8]$ 区间内第 $3$、第 $5$ 和第 $7$ 位置上的 $w_i\le17$ 。因此
答案为$(a_3\times w_3+a_5\times w_5+a_7\times w_7)xnor(\sum_{i=1}^8{a_i})$。按照定义式计算即可得上式的值。
对于第 $3$ 次询问，此时序列上的权值为 $w=\{12,32,15,47,15,32,12,47,6,32\}$。$k=5$，但不存在 $w_i\le5$ 的位置，因此答案为 $0\;xnor(\sum_{i=1}^7{a_i})$。
【数据范围与约定】
对于全部数据，有 $1\le n,q\le10^5$，$0\le a_i,w_i,k\le10^5$，$1\le l,r,p\le n$。下表中留空的位置
代表该测试点在这一项目上没有特殊约定。
$\wedge$表示逻辑与（即布尔代数中的与运算 $\text{and}$），$\neg$ 表示逻辑非（即布尔代数中的非运算 $not$）。
本题输入输出数据规模较大且时限较紧，请不要使用 $C$++ 风格 $I/O$ 操作并考虑使用 $I/O$ 优化。另请注意常数因子对程序效率的影响。标准程序未对常数因子进行专门优化，用时约为所给时间限制的一半。
题解
题目怎么那么长啊喂，这样我的题解就短一点吧。
我们观察$xnor$操作，不难发现这个操作就相当于在无符号的$int$下的$not(x \space xor \space y)$
然后我们考虑分块，这样就变成一个裸题了，$Ai$的和用树状数组维护。
注：编译环境下开启$O2$优化
1 |
|