Cleverly split each bit operation interval query question. See the content for the title.

Title: definition operation x × Y = ~ (X & Y), X and y are unsigned integers.
To an unsigned integer array a [], two operations are supported:

Operation 1: give the integer l,r and unsigned integer q, and output q × a[l] × a[l+1] ×……× a[r].
Operation 2: give the integer p and the unsigned integer x, and modify a[p] to X.

Input: the first line: n, m < = 10 ^ 5, n is the size of the array, and M is the number of operations.

Line 2: n unsigned integers.

Line 3 to line m+2: operation: for example: 1 l r q or 2 p x

Output: the answer obtained by operation 1 of each operation and line feed.

Sample input:

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

Sample output:

4294967103
4294966957
4294967103

 

Analysis: interval query modification = > segment tree solution. But obviously, the operation cannot use the combination law, such as a × b × c≠a × (b × c) , just write it out:

a × b × C = ~ (~ (A & B) & C) = A & B | ~ C and a × (b × c) = ~ (A & (~ (B & C)) = ~ a | (B & C) is obviously unequal. Therefore, the conventional line segment tree method can not be done. Because the operation must be carried out in order.

The problem is that we can only preprocess the interval of the segment tree, and the first number is not in the segment tree. How to solve it? If we calculate the query number q with the first number in the interval to get tmp, and the operation result when the first number is tmp is stored in the line segment tree, then this problem is finished.

However, tmp is in the range of 2 ^ 32-1, and there is no time and space for preprocessing. be careful! This is a bit operation. Obviously, each bit of bit operation is independent. We divide the number of queries into 32-bit binary numbers and calculate the result of each bit operation according to the above idea (that is, the first number is 0 / 1). Then this problem can be solved perfectly. That is, each node of the segment tree has a parameter mul [i] [J], 0 < = I < 32, j = 0 / 1, which indicates that for the binary bit I, the first number of the node interval is the result of J operation.

The next step is how to preprocess parameters mul[i][j] and single point modification. The relationship is relatively simple, so I won't repeat it.

Note that the leaf node mul[i][j]=j.

Attach Code:

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1e5+10;
typedef unsigned int uint;
int n,m,k;
uint now;//Global variable storage now Perform interval operation. 
uint a[maxn];
struct seg{
    int l,r;
    uint mul[32][2];
}t[maxn<<2];
//mul[i][0]Indicates the second in the interval i Bit binary number. When the left end point of the interval is 0, the operation result of the whole interval.
//Similarly mul[i][1]Indicates the second in the interval i Bit binary number,When the left end point of the interval is 1, the operation result of the whole interval.
//These two are used to merge intervals. 
int cal(int x,int y){if(x==y&&x==1)return 0;return 1;}//nand Operation. 
void update(int id,int j)//to update
{
    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)];//Operation. 
}
void query(int id,int l,int r,int p)//yes l-r Second of interval p Bit.
{
    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;//initialization. 
        }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;
}

 

Posted by phenley on Tue, 10 May 2022 03:22:16 +0300