#include<stdio.h>
#include
#include<math.h>
#include<string.h>
using namespace std;
struct SegmentTreeNode {
int start, end;
int mini;
bool bits[32];//false = 0, true = 1
void assignLeaf(int value ) {
int tmp = value;
for ( int i = 0; i < 32; i++ ) {
if ( ( tmp & 1 ) == 0 ) {
bits[i] = false;
}
else {
bits[i] = true;
}
tmp >>=1;
}
mini = value;
}
void merge(SegmentTreeNode& left, SegmentTreeNode& right) {
mini = min( left.mini, right.mini );
for ( int i = 0; i < 32; i++ ) {
if ( left.bits[i] == true || right.bits[i]== true ) {
bits[i] = true;
}
else {
bits[i] = false;
}
}
}
int query() {
return mini;
}
bool isUpdateRequired(int updateValue ) {
bool updateBits[32];
for ( int i = 0; i < 32; i++ ) {
if ( ( updateValue & 1 )== 0 ) {
updateBits[i] = false;
}
else {
updateBits[i] = true;
}
}
for ( int i = 0; i < 32; i++ ) {
if ( updateBits[i] == false && bits[i] == true ) {
return true;
}
}
return false;
}
};
template<class InputType, class UpdateType, class OutputType>
class SegmentTree{
SegmentTreeNode* nodes;
int N;
public:
SegmentTree(InputType arr[], int N ) {
this->N = N;
nodes = new SegmentTreeNode[getSegmentTreeSize(N)];
buildTree(arr,1, 0, N-1);
}
~SegmentTree() {
delete[] nodes;
}
void update(int startRange, int endRange, UpdateType updateValue ) {
update(1, startRange, endRange, updateValue);
}
OutputType query(int startRange, int endRange ) {
SegmentTreeNode result = query(1,startRange, endRange);
return result.query();
}
private:
SegmentTreeNode query(int stIndex, int startRange , int endRange ) {
SegmentTreeNode result;
if ( nodes[stIndex].start == startRange && nodes[stIndex].end == endRange ) {
result = nodes[stIndex];
return result;
}
int mid = ( nodes[stIndex].start + nodes[stIndex].end ) / 2;
int leftIndex = 2 * stIndex;
int rightIndex = leftIndex + 1;
if ( startRange > mid ) {
result = query(rightIndex, startRange, endRange);
}
else if ( endRange <= mid ) {
result = query(leftIndex, startRange, endRange);
}
else {
SegmentTreeNode leftNode = query(leftIndex, startRange, mid);
SegmentTreeNode rightNode = query(rightIndex, mid + 1, endRange);
result.merge(leftNode,rightNode);
result.start = leftNode.start;
result.end = rightNode.end;
}
return result;
}
void update(int stIndex, int startRange, int endRange, UpdateType updateValue ) {
//if leaf node
if ( nodes[stIndex].start == nodes[stIndex].end ) {
nodes[stIndex].mini = (nodes[stIndex].mini & updateValue);
int tmp = nodes[stIndex].mini;
for ( int i = 0; i < 32; i++ ) {
if ( ( tmp & 1 ) == 0 ) {
nodes[stIndex].bits[i] = false;
}
else {
nodes[stIndex].bits[i] = true;
}
tmp >>=1;
}
return;
}
//if need for anding exists
if ( nodes[stIndex].start == startRange && nodes[stIndex].end == endRange ) {
if (nodes[stIndex].isUpdateRequired(updateValue) ) {
int mid = ( nodes[stIndex].start + nodes[stIndex].end ) / 2;
int leftIndex = 2 * stIndex;
int rightIndex = leftIndex + 1;
if ( startRange > mid ) {
update(rightIndex, startRange, endRange, updateValue);
}
else if ( endRange <= mid ) {
update(leftIndex, startRange, endRange, updateValue);
}
else {
update(leftIndex, startRange, mid , updateValue);
update(rightIndex, mid + 1, endRange, updateValue);
}
nodes[stIndex].merge(nodes[leftIndex], nodes[rightIndex]);
}
}
}
void buildTree(InputType arr[], int stIndex, int first, int last ) {
nodes[stIndex].start = first;
nodes[stIndex].end = last;
if ( first == last ) {
nodes[stIndex].assignLeaf(arr[first]);
return;
}
int mid = ( first + last ) / 2;
int leftNodeIndex = 2 * stIndex;
int rightNodeIndex = leftNodeIndex + 1;
buildTree(arr,leftNodeIndex,first, mid);
buildTree(arr,rightNodeIndex,mid+1, last);
nodes[stIndex].merge(nodes[leftNodeIndex],nodes[rightNodeIndex]);
}
long long getSegmentTreeSize(int N ) {
long long size = 1;
for ( ; size< N; size<<=1) {
;
}
return size<<1;
}
};
int main() {
int n, q, l, r, x, choice;
int arr[100000];
cin>>n>>q;
for ( int i = 0; i < n; i++ ) {
cin>>arr[i];
}
SegmentTree<int, int, int> st(arr, n);
while ( q-- ) {
cin>>choice;
cin>>l>>r;
if ( choice == 0 ) {
//query 0 l r
cout<<st.query(l-1,r-1)<<endl;
}
else {
//1 l r x update
cin>>x;
st.update(l-1,r-1,x);
}
}
return 0;
}
The above is the code.
Here is the link to the problem statement:
Can someone please tell me where the bug is?
