제출 #1219221

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219221		takoshanava	XORanges (eJOI19_xoranges)	C++20	100 / 100	338 ms	11344 KiB

xoranges

#include <bits/stdc++.h>
#define int long long 
#define pb push_back
#define fs first
#define sc second
using namespace std;

const int N = 2e5 + 5;
int a[N], seg1[4 * N], seg2[4 * N];

void upd1(int k, int l, int r, int i, int v){
    if(l + 1 == r){
        seg1[k] = a[l] = v;
        return;
    }
    int m = (l + r) / 2;
    if(i < m){
        upd1(k * 2 + 1, l, m, i, v);
    }else{
        upd1(k * 2 + 2, m, r, i, v);
    }
    seg1[k] = seg1[k * 2 + 1] ^ seg1[k * 2 + 2]; 
}

void upd2(int k, int l, int r, int i, int v){
    if(l + 1 == r){
        seg2[k] = a[l] = v;
        return;
    }
    int m = (l + r) / 2;
    if(i < m){
        upd2(k * 2 + 1, l, m, i, v);
    }else{
        upd2(k * 2 + 2, m, r, i, v);
    }
    seg2[k] = seg2[k * 2 + 1] ^ seg2[k * 2 + 2]; 
}

int get1(int k, int l, int r, int s, int e){
    if(l >= e or r <= s){
        return 0;
    }
    if(l >= s and r <= e){
        return seg1[k];
    }

    int m = (l + r) / 2;
    return get1(k * 2 + 1, l, m, s, e) ^ get1(k * 2 + 2, m, r, s, e);
}

int get2(int k, int l, int r, int s, int e){
    if(l >= e or r <= s){
        return 0;
    }
    if(l >= s and r <= e){
        return seg2[k];
    }

    int m = (l + r) / 2;
    return get2(k * 2 + 1, l, m, s, e) ^ get2(k * 2 + 2, m, r, s, e);
}

signed main(){
    int n, q;
    cin >> n >> q;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }

    for(int i = 0; i < n; i++){
        if(i % 2 == 0){
            upd1(0, 0, n, i, a[i]);
        }else{
            upd2(0, 0, n, i, a[i]);
        }
    }

    while(q--){
        int tp;
        cin >> tp;
        if(tp == 2){
            int l, r;
            cin >> l >> r;
            if((r - l + 1) % 2 == 0){
                cout << 0 << endl;
                continue;
            }
            l--, r--;
            if(l % 2 == 0){
                cout << get1(0, 0, n, l, r + 1) << endl;
            }else{
                cout << get2(0, 0, n, l, r + 1) << endl;
            }
        }else{
            int l, v;
            cin >> l >> v;
            l--;
            if(l % 2 == 0){
                upd1(0, 0, n, l, v);
            }else{
                upd2(0, 0, n, l, v);
            } 
        }
    }
}

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