제출 #288240

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
288240		Benmath	XORanges (eJOI19_xoranges)	C++14	100 / 100	998 ms	10104 KiB

xoranges

#include<bits/stdc++.h>
using namespace std;
int arr[200000];
int tree1[800000];
int tree2[800000];
int b[200000];
int c[200000];
void build1(int node,int start,int end){
 if(start==end){
        tree1[node]=b[start];
    }else{
        int mid=(start+end)/2;
        build1(2*node,start,mid);
        build1(2*node+1,mid+1,end);
        tree1[node]=tree1[2*node] ^ tree1[2*node+1];
    }

}
void build2(int node,int start,int end){
    if(start==end){
        tree2[node]=c[start];
    }else{
        int mid=(start+end)/2;
        build2(2*node,start,mid);
        build2(2*node+1,mid+1,end);
        tree2[node]=tree2[2*node] ^ tree2[2*node+1];
    }

}
void update1(int node,int start,int end,int index,int val){
    if(start==end){
        tree1[node]=val;
        b[index]=val;
    }else{
        int mid=(start+end)/2;
        if(start<=index and index<=mid){
            update1(2*node,start,mid,index,val);
        }else{
            update1(2*node+1,mid+1,end,index,val);
        }
        tree1[node]=tree1[2*node] ^ tree1[2*node+1];
    }
}
void update2(int node,int start,int end,int index,int val){
    if(start==end){
        tree2[node]=val;
        c[index]=val;
    }else{
        int mid=(start+end)/2;
        if(start<=index and index<=mid){
            update2(2*node,start,mid,index,val);
        }else{
            update2(2*node+1,mid+1,end,index,val);
        }
        tree2[node]=tree2[2*node] ^ tree2[2*node+1];
    }
}
int query1(int node,int start,int end,int l,int r){
    if(r<start or l>end){
        return 0;
    }
    if(l<=start and end<=r){
        return tree1[node];
    }
    int mid=(start+end)/2;
    int p1=query1(2*node,start,mid,l,r);
    int p2=query1(2*node+1,mid+1,end,l,r);
    return (p1 ^ p2);
}
int query2(int node,int start,int end,int l,int r){
    if(r<start or l>end){
        return 0;
    }
    if(l<=start and end<=r){
        return tree2[node];
    }
    int mid=(start+end)/2;
    int p1=query2(2*node,start,mid,l,r);
    int p2=query2(2*node+1,mid+1,end,l,r);
    return (p1 ^ p2);
}
int main(){
    int n,q;
    cin>>n>>q;

int x=0;
int y=0;
    for(int i=0;i<n;i++){
        cin>>arr[i];
        if(i%2==0){
           b[x]=arr[i];
           x++;
        }else{
            c[y]=arr[i];
            y++;
        }
        
    }
  
   build1(1,0,x-1);
   build2(1,0,y-1);
    for(int i=0;i<q;i++){
        int a,b1,c1;
        cin>>a>>b1>>c1;
        if(a==1){
            if((b1-1)%2==0){
                update1(1,0,x-1,(b1-1)/2,c1);
                arr[b1-1]=c1;
            }else{
                update2(1,0,y-1,(b1-2)/2,c1);
                arr[b1-1]=c1;
            }
        }else{
           
            if(c1==b1){
                cout<<arr[b1-1]<<endl;
            }else if(abs(c1-b1)%2==1){
                cout<<0<<endl;
            }else{
           
            if((b1-1)%2==0){
              
                  cout<<query1(1,0,x-1,(b1-1)/2,(c1-1)/2)<<endl;
            }else{
                cout<<query2(1,0,y-1,(b1-2)/2,(c1-2)/2)<<endl;
            }
       
              
            }
        }
    }
}

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