[NOIP2018模拟]挑战书

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

10 10
13 15 23 45 21 23 14 26 35 44
12 32 15 47 15 32 12 47 32 32
1 2 8 17
2 4 26
1 1 6 47
3 9 6
2 9 4
1 1 7 5
3 7 6
2 7 2
3 3 6
1 4 9 6

Output Sample

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$ 优化

#include <math.h>
#include <stdio.h>
#include <utility>
#include <iostream>
#include <algorithm>
#define Re register int
#define LL long long
#define uint unsigned int
#define mp make_pair

int N,Q,A[100005],W[100005],L[405],BlkSz,BlkNum;
LL Sum[100005];
std::pair<int,LL> Data[100005];

template <typename T> inline void read(T &var)
{
	T x=0; int w=0; char ch=0;
	while (!isdigit(ch)) w|=ch=='-',ch=getchar();
	while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	var=w?-x:x;
}
class TreeArr{
	LL T[100005];
	inline int lowbit(int x) {return x&-x;}
public:
	inline void AddNum(int pos,int x)
		{for (;pos<=N;pos+=lowbit(pos)) T[pos]+=x;}
	inline LL Query(int pos)
	{ LL ret=0;
		for (;pos;pos-=lowbit(pos))ret+=T[pos];
		return ret;
	}
}Tr;
inline uint xnor(LL a,LL b) {return ~(uint)((a&4294967295u)^(b&4294967295u));}
inline int GetID(int x) {return (x+BlkSz-1)/BlkSz;}
inline void ReBuild(int Ind)
{
	for (Re i=L[Ind]; i<L[Ind+1]; ++i) Data[i]=std::mp(W[i],1LL*A[i]*W[i]);
	sort(Data+L[Ind],Data+L[Ind+1]); Sum[L[Ind]]=Data[L[Ind]].second;
	for (Re i=L[Ind]+1; i<L[Ind+1]; ++i) Sum[i]=Sum[i-1]+Data[i].second;
}
int main(int argc, char const *argv[])
{
	read(N),read(Q); BlkSz=sqrt(N),BlkNum=GetID(N);
	for (Re i=1; i<=N; ++i)	read(A[i]),Tr.AddNum(i,A[i]);
	for (Re i=1; i<=N; ++i)	read(W[i]); L[1]=1; L[BlkNum+1]=N+1;
	for (Re i=2; i<=BlkNum; ++i) L[i]=L[i-1]+BlkSz;
	for (Re i=1; i<=BlkNum; ++i) ReBuild(i);
	while (Q--)
	{ int opt,l,r,k;
		read(opt);
		switch (opt)
		{
			case 1: {
				LL S=0;
				read(l),read(r),read(k);
				if (GetID(l)!=GetID(r))
				{
					for (Re i=GetID(l)+1; i<=GetID(r)-1; ++i)
					{
						int x=L[i],y=L[i+1]-1;
						while (x<=y)
						{
							int mid=(x+y)>>1;
							if (Data[mid].first>k) y=mid-1;
							else x=mid+1;
						} if (y>=L[i]) S+=Sum[y];
					}
					for (Re i=l; i<L[GetID(l)+1]; ++i)
						if (W[i]<=k) S+=1LL*A[i]*W[i];
					for (Re i=L[GetID(r)]; i<=r; ++i)
						if (W[i]<=k) S+=1LL*A[i]*W[i];
				}
				else for (Re i=l; i<=r; ++i) if (W[i]<=k) S+=1LL*A[i]*W[i];
				printf("%u\n",xnor(S,Tr.Query(r)-Tr.Query(l-1)));
			} break;
			case 2:
				read(l),read(k),Tr.AddNum(l,k-A[l]);
				A[l]=k; ReBuild(GetID(l));
			break;
			case 3:
				read(l),read(k),W[l]=k;
				ReBuild(GetID(l));
			break;
		}
	}
	return 0;
}