You are given an n-bit integer (initially 0). There are Q queries. Each query is of following type: 0 L R: Set all the bits from Lth bit to Rth bit to zero. 1 L R: Set all the bits from Lth bit to Rth bit to one. 2 L R: Find the integer formed by the bits in range [L, R]. Answer all the queries of type 2. Indexing is 0-based. See the sample test case for clarity. Input Format First line contains two integers, nand q. Next Q lines contains Q queries. Constraints 1<=n,q<=200000 0<=L,R<n Output Format For each query of type 2, print the integer(in decimal) formed by it modulo 109+7. Sample Input 3 6 1 0 1 2 0 2 0 1 1 2 1 1 1 2 2 2 0 2 Sample Output 6 0 5 Explanation Initially the integer in binary is “000”. After first query, it becomes, 110(=6). Answer to next query comes out to be 6, i.e. “110” in decimal. After 3rd query, it becomes “100”. Answer to 4th query is 0,i.e. decimal of “0”. After 5th query, it becomes, “101” and thus answer to the last query comes out to be 5, i.e. “101” i decimal.
#include
#include
using namespace std;
int query1(int no,int i,int n)
{
int mask=1<<(n-i-1);
no=(no)|(mask);
return no;
}
int query0(int no,int i,int n)
{
int mask=(~1<<(n-i-1));
no=no&(mask);
return no;
}
int query2(int no,int l,int r,int n)
{
int arr[n];
int digit;
for(int i=0;i<n;i++)
{
digit=no&1;
arr[i]=digit;
no=no>>1;
}
int temp;
for(int i=0;i<n/2;i++)
{
temp=arr[i];
arr[i]=arr[n-i-1];
arr[n-i-1]=temp;
}
int answer=0;
for(int i=l;i<=r;i++)
{
answer+= arr[i]*(pow(2,n-i-1));
}
return answer;
}
int main()
{
int n;
cin>>n;
int qn;
cin>>qn;
int answer=0;
for(int i=0;i<qn;i++)
{
int q;
cin>>q;
int l;
int r;
cin>>l;
cin>>r;
if(q==1)
{
for(int i=l;i<=r;i++)
{
answer=query1(answer,i,n);
}
}
else if(q==0)
{
for(int i=l;i<=r;i++)
{
answer=query0(answer,i,n);
}
}
else
{
cout<<query2(answer,l,r,n)<<endl;
}
}
}