GEHA1804 - Editorial

editorial
,
1

PROBLEM LINKS:

Practice

Contest

DIFFICULTY:

Easy

PREREQUISITES:

  • Segment tree
  • Bit Manipulation

PROBLEM:

Consider Special numbers which have exactly three set bits.
There is an array of N numbers with initial value 0.
But ith bit of jth number can be flipped such that the value of that number does not exceed 1018 you need to output the length of longest subarray in the given range consisting only of special numbers.

EXPLANATION :

Segment tree can be used to solve this problem.For each node we store the following:

  • Prefix length - for length of longest subarray of special numbers in prefix
  • Suffix length - for length of longest subarray of special numbers in suffix
  • Total length - length of array in that particular range
  • Subarray length (Result for that very node)- for length of longest subarray of special numbers in that particular range
For l=r prefix length,sufix length and result in [l,r] would be 1 if array element at that index is a special number else would be 0.Total length for both cases would be 1.

The merge function which would return parent node after merging its left and right child would be


```
Node merge(Node left,Node right){
    Node parent;
    if(left.tot == left.pre)
        parent.pre = left.tot + right.pre;
    else
        parent.pre=left.pre;
    if(right.tot == right.suf)
        parent.suf = right.tot + left.suf;
    else
        parent.suf = right.suf;
    parent.tot = left.tot + right.tot;
    parent.res = max({parent.pre,parent.suf,left.res,right.res,left.suf+right.pre});
    return parent;
    }
```


For first type of query we would have to update the segment tree.


```

void update(int node,int start,int end,int idx,long long int val){
    if(start==end){
        long long int x = 1LL << val;
        A[start] = A[start]^x;
        long long int x=_builtin_popcountll(A[start];
        if(x==3){
             tree[node].pre=tree[node].suf=tree[node].res=1;
         }
        else{
             tree[node].pre=tree[node].suf=tree[node].res=0;
         }
         tree[node].tot=1;
    }
    else{
        int mid=(start+end)/2;
        if(start<=idx && idx<=mid)
            update(2*node,start,mid,idx,val);
        else
            update(2*node+1,mid+1,end,idx,val);
        tree[node]=merge(tree[2*node],tree[2*node+1]);
    }
}

```

For the second type of query function would be


```

Node query(int node,int start,int end,int l,int r){
    if(r < start || end < l){
        node n;
        n.pre=n.suf=n.res=n.tot=0;
        return n;
    }
    else if(l <= start && end <= r) {
        return tree[node];
    }
    else{
        int mid=(start+end)/2;
        Node left=query(2*node,start,mid,l,r);
        Node right=query(2*node+1,mid+1,end,l,r);
        return merge(left,right);
    }
}

```



TIME COMPLEXITY:


 


   O(logn) for each query type.


 
## AUTHOR'S AND TESTER'S SOLUTIONS:


Setter's solution

Tester's solution