339D codeforces - Xenia and Bit operations

339D codeforces - Xenia and Bit operations

Link ;   https://codeforces.com/problemset/problem/339/D

Solution in C++

#include <bits/stdc++.h>
using namespace std;

//Hello World

typedef long long int lli;
typedef long double ld;
#define pii pair<int,int>
#define mod 1000000007
#define S second
#define F first
#define PB push_back
#define lasB(b) (b&(-b))
#define N 140000

int n , m , sege[2*N] , arr[N];

struct seTree
{
    int build(int node , int l , int r)
    {
        if(l==r)
        {
            sege[node]=arr[l];
            return 1;
        }
        else
        {
            int mid = (l+r)/2;
            int r1=build(node*2+1 , l , mid );
            int r2=build(node*2+2 , mid+1 , r );
            if(r1||r2)
            {
                sege[node] = (sege[node*2+1]|sege[node*2+2]);
                return 0;
            }
            else
            {
                sege[node] = (sege[node*2+1]^sege[node*2+2]);
                return 1;
            }
        }
    }
    int update(int node , int l , int r , int a , int b)
    {
        if(l==r)
        {
            sege[node]=b;
            return 1;
        }
        else
        {
            int mid = (l+r)/2;
            int re ;
            if(a<=mid)re=update(node*2 +1 , l , mid , a , b );
            else re=update(node*2+2 , mid+1 , r , a , b );
            if(re)
            {
                sege[node] = (sege[node*2+1]|sege[node*2+2]);
                return 0;
            }
            else
            {
                sege[node] = (sege[node*2+1]^sege[node*2+2]);
                return 1;
            }
        }
    }
};
seTree T;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie();
    cin>>n>>m;
    for(int i=1;i<=(1<<n);i++)
        cin>>arr[i];
    T.build(0,1,(1<<n));
    for(int i=0;i<m;i++)
    {
        int t1 , t2;
        cin>>t1>>t2;
        T.update(0,1,(1<<n),t1,t2);
        cout<<sege[0]<<"\n";
    }
    return 0;
}

Share on Google Plus

About Mohamed Sobhi

My name is Mo.Sobhy ,I study at School excelling high school in Ain Shams ,Cairo
My hobbies is programming ,and web development ,playing chess and writing horror stories.