제출 #1305864

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1305864		Newtonabc	XORanges (eJOI19_xoranges)	C++20	100 / 100	361 ms	5124 KiB

xoranges

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll MOD=1e9+7;
const int N=5e5+10;
const int M=1<<19;
int arr[N];
struct stree{
    int s[M],arr[N];
    void build(int l,int r,int idx){
        if(l==r) return void(s[idx]=arr[l]);
        int m=(l+r)/2;
        build(l,m,idx*2);
        build(m+1,r,idx*2+1);
        s[idx]=s[idx*2]^s[idx*2+1];
    }
    void update(int l,int r,int idx,int a,int b){
        if(a<l || a>r) return;
        if(l==r) return void(s[idx]=b);
        int m=(l+r)/2;
        update(l,m,idx*2,a,b);
        update(m+1,r,idx*2+1,a,b);
        s[idx]=s[idx*2]^s[idx*2+1];
    }
    int query(int l,int r,int idx,int a,int b){
        if(a>r || b<l) return 0;
        if(a<=l && b>=r) return s[idx];
        int m=(l+r)/2;
        return query(l,m,idx*2,a,b)^query(m+1,r,idx*2+1,a,b);
    }
}sa,sb;
int main(){
    int n,q;
    cin>>n >>q;
    for(int i=0;i<n;i++) cin>>arr[i];
    int na=(n+1)/2,nb=(n)/2;
    for(int i=0;i<n;i++){
        if(i%2==0) sa.arr[i/2]=arr[i];
        else sb.arr[i/2]=arr[i];
    }
    // cout<<na-1 <<" " <<nb-1 <<"\n";
    sa.build(0,na-1,1);
    sb.build(0,nb-1,1);
    // for(int i=0;i<na;i++) cout<<sa.query(0,na-1,1,i,i) <<" ";
    // cout<<"\n";
    // for(int i=0;i<nb;i++) cout<<sb.query(0,nb-1,1,i,i) <<" ";
    // cout<<"\n";
    while(q--){
        //cout<<"tmp" <<"\n";
        int t,a,b;
        cin>>t >>a >>b;
        if(t==1){
            a--;
            if(a%2==0) sa.update(0,na-1,1,a/2,b);
            else sb.update(0,nb-1,1,a/2,b);
        }
        else{
            if((b-a+1)%2==0){
                cout<<0 <<"\n";
                continue;
            }
            a--,b--;
            if(a%2==0) cout<<sa.query(0,na-1,1,a/2,b/2) <<"\n";
            else cout<<sb.query(0,nb-1,1,a/2,b/2) <<"\n";
        }
        // for(int i=0;i<na;i++) cout<<sa.query(0,na-1,1,i,i) <<" ";
        // cout<<"\n";
        // for(int i=0;i<nb;i++) cout<<sb.query(0,nb-1,1,i,i) <<" ";
        // cout<<"\n";
    }
}

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