题目：定义运算x×y=~(x&y)，x，y为无符号整数类型。
给一无符号整数数组a[],支持2个操作：
操作1：给出整数l,r和无符号整数q,输出q×a[l]×a[l+1]×……×a[r]。
操作2：给出整数p和无符号整数x将a[p]修改为x。
输入:第一行：n,m<=10^5,n为数组大小,m为操作个数。
第二行：n个无符号整数。
第3行至m+2行：操作：如:1 l r q或2 p x
输出：每个操作1运算得到的答案并换行。
样例输入：
5 5
571 342 228 152 192
1 1 5 409
2 1 414
1 1 2 100
2 4 341
1 2 5 315
样例输出：
4294967103
4294966957
4294967103
分析：区间查询修改=>线段树解决。但是很显然该运算是不可使用结合律的，如a×b×c≠a×(b×c)，写出来就知道了：
a×b×c=~(~(a&b)&c)=a&b|~c而a×(b×c)=~(a&(~(b&c)))=~a|(b&c)显然不等。因此常规的线段树做法就做不出来了。因为该运算一定要按顺序来。
问题出在我们只能预处理出线段树的区间，而进行运算时第一个数又不在线段树里。如何解决？假如我们把查询的数q与该区间第一个数运算得到tmp,而线段树里面存储了第一个数为tmp时的运算结果，那么这道题就做完了。
但tmp在2^32-1范围，没有时间也没有空间进行预处理。注意！这是位运算。而显然位运算每一位都是独立的，我们把查询的数拆成32位二进制数，按照上面的思路(即第一个数为0/1)求出每一位运算后的结果，那么这个问题就可以完美解决了。即线段树每个节点有参数mul[i][j],0<=i<32,j=0/1,表示对于二进制第i位，该节点区间第一个数为j运算后的结果。
接下来就是如何预处理参数mul[i][j]和单点修改了。关系比较简单就不再赘述。
注意叶子节点mul[i][j]=j。
贴上代码：
#include<cstdio> #include<algorithm> using namespace std; const int maxn=1e5+10; typedef unsigned int uint; int n,m,k; uint now;//全局变量存now进行区间运算。 uint a[maxn]; struct seg{ int l,r; uint mul[32][2]; }t[maxn<<2]; //mul[i][0]表示该区间第i位二进制数，区间左端点为0时整个区间运算结果。 //同理mul[i][1]表示该区间第i位二进制数,区间左端点为1时整个区间运算结果。 //这2个用于合并区间。 int cal(int x,int y){if(x==y&&x==1)return 0;return 1;}//nand运算。 void update(int id,int j)//更新 { int ls=id<<1,rs=ls+1; t[id].mul[j][0]=t[rs].mul[j][cal(t[ls].mul[j][0],(a[t[rs].l]&(1<<j))>>j)]; t[id].mul[j][1]=t[rs].mul[j][cal(t[ls].mul[j][1],(a[t[rs].l]&(1<<j))>>j)];//运算。 } void query(int id,int l,int r,int p)//对l-r区间的第p位进行运算。 { if(t[id].r<l||t[id].l>r)return ; if(t[id].l>=l&&t[id].r<=r) { now=t[id].mul[p][cal(now,(a[t[id].l]&(1<<p))>>p)];return; }query(id<<1,l,r,p); query((id<<1)+1,l,r,p); } void build(int id,int l,int r) { t[id].l=l;t[id].r=r; if(l==r) { for(int j=0;j<32;j++) { t[id].mul[j][0]=0; t[id].mul[j][1]=1;//初始化。 }return ; }int mid=(l+r)/2; build(id<<1,l,mid);build((id<<1)+1,mid+1,r); for(int j=0;j<32;j++)update(id,j); } void change(int id,int p,uint x) { if(t[id].l==t[id].r)return ; int mid=(t[id].l+t[id].r)/2; if(p<=mid)change(id<<1,p,x); else change((id<<1)+1,p,x); for(int j=0;j<32;j++)update(id,j); } int main() { //freopen("nand.in","r",stdin); //freopen("nand.out","w",stdout); scanf("%d%d",&n,&m); int i; for(i=1;i<=n;i++)scanf("%u",&a[i]); build(1,1,n); int opt,l,r,j; uint x; for(i=1;i<=m;i++) { scanf("%d",&opt); if(opt==1){ scanf("%d%d%u",&l,&r,&x); uint ans=0; for(j=0;j<32;j++) { now=(x&(1<<j))>>j; query(1,l,r,j); ans+=now<<j; }printf("%u\n",ans); }else { scanf("%d%u",&l,&x); a[l]=x; change(1,l,x); } }return 0; }
原文：https://www.cnblogs.com/whiteblue/p/13891036.html