제출 #999742

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
999742		vjudge1	XORanges (eJOI19_xoranges)	C++17	100 / 100	297 ms	14092 KiB

xoranges

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define pb push_back
#define pf push_front
#define pi pair<int,int>

const int MAX  = 2e5+1;


ll odd[MAX*4], even[MAX*4];
ll arr[MAX];

void build_odd(int v, int l, int r){
    if(l==r){
        if(l%2==1){ 
            
            odd[v] =arr[l];
        }
        return;
    }
    int m =(l+r)/2;
    build_odd(v*2,l,m);
    build_odd(v*2+1,m+1,r);
    odd[v] = odd[v*2]^odd[v*2+1];
}

void build_even(int v, int l, int r){
    if(l==r){
        
       
        if(l%2==0){
        even[v] =arr[l];
        }
        return;
    }
    int m =(l+r)/2;
    build_even(v*2,l,m);
    build_even(v*2+1,m+1,r);
    even[v] = even[v*2]^even[v*2+1];
}

void update_even(int v, int l, int r, int pos , int val){
    if(l==r){
        even[v] = val;
        return;
    }
    int m = (l+r)/2;
   
    if(pos<=m) update_even(v*2,l,m,pos,val);
    else update_even(v*2+1,m+1,r,pos,val);
    even[v]= even[v*2]^even[v*2+1];
}


void update_odd(int v, int l, int r, int pos , int val){
    if(l==r){
        odd[v] = val;
        return;
    }
    int m = (l+r)/2;
   
    if(pos<=m) update_odd(v*2,l,m,pos,val);
    else update_odd(v*2+1,m+1,r,pos,val);
    odd[v]= odd[v*2]^odd[v*2+1];
}



ll get_odd(int v, int l, int r, int fl, int fr){
    if(fl>fr) return 0;
    else if(l==fl && r==fr) return odd[v];
    int m = (l+r)/2;
    ll a= get_odd(v*2,l,m,fl,min(fr,m));
    ll b = get_odd(v*2+1,m+1,r,max(fl,m+1),fr);
    return a^b;
}


ll get_even(int v, int l, int r, int fl, int fr){
    if(fl>fr) return 0;
    else if(l==fl && r==fr) return even[v];
    int m = (l+r)/2;
    ll a= get_even(v*2,l,m,fl,min(fr,m));
    ll b = get_even(v*2+1,m+1,r,max(fl,m+1),fr);
    return a^b;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,q;
    cin >> n >> q;
    for(int i  = 1; i <= n; i++){
        cin >> arr[i];
    }
    
    
    build_odd(1,1,n);
    build_even(1,1,n);
    int type,a,b;
    while(q--){
        cin >> type >> a >> b;
        if(type==2){
            if((b-a+1)%2==0){
                cout << 0 << endl;
            }
            else if(a%2==1) cout << get_odd(1,1,n,a,b)<< endl;
            else cout<<  get_even(1,1,n,a,b)<<endl;
        }
        else{
            if(a%2==1) update_odd(1,1,n,a,b);
            else update_even(1,1,n,a,b);
        }
    }
    
    
}

• Subtask 1: 12 / 12
• Subtask 2: 18 / 18
• Subtask 3: 25 / 25
• Subtask 4: 20 / 20
• Subtask 5: 25 / 25