Submission #1099564

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099564		vjudge1	XORanges (eJOI19_xoranges)	C++17	100 / 100	440 ms	11252 KiB

xoranges

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

string abc = "abcdefghijklmnopqrstuvwxyz";


struct segTree{
    int sz;
    vector<int> t, a;
    void init(int n){
        sz = 1;
        while(sz < n) sz*=2;
        t.assign(2*sz, 0);
    }

    void merge(int v){
        t[v]=t[2*v]^t[2*v+1];
    }

    void inn(int v, int tl, int tr){
        if(tl == tr){
            t[v] = a[tl-1];
            return;
        }
        int tm = (tl+tr)/2;
        inn(2*v, tl, tm);
        inn(2*v+1, tm+1, tr);
        merge(v);
    }

    void in(int n, vector<int> va){
        a = va;
        inn(1, 1, n);
        for(int i = 1; i <= n; i++){
        }
    }

    int get(int v, int tl, int tr, int l, int r){
        // if(min(v, tl) < 0) return 33;
        if(tl == l && tr == r){
            return t[v];
        }
        int tm = (tl+tr)/2;
        if(tm >= r) return get(2*v, tl, tm, l, r);
        if(tm < l) return get(2*v+1, tm+1, tr, l, r);
        int ga = get(2*v, tl, tm, l, tm), gb = get(2*v+1, tm+1, tr, tm+1, r);
        return ga^gb;
    }

    void upd(int v, int tl, int tr, int pos, int va){
        if(tl == tr){
            t[v]=va;
            return;
        }
        int tm = (tl+tr)/2;
        if(tm >= pos) upd(2*v, tl, tm, pos, va);
        else upd(2*v+1, tm+1, tr, pos, va);
        merge(v);
    }

};



signed  main(){
    int n, q;
    cin >> n >> q;
    vector<int> v(n+1);
    for(int i = 1; i <= n; i++) cin >> v[i];
    segTree sa, sb;
    sa.init(n/2+2);
    sb.init(n/2+2);
    vector<int> ra, rb;
    for(int i = 1; i <= n; i++){
        if(i%2 == 1){
            ra.push_back(v[i]);
        }
        else rb.push_back(v[i]);
    }

    sa.in(ra.size(), ra);
    sb.in(rb.size(), rb);
    int na = ra.size();
    int nb = rb.size();
     n = n/2+2;
    while(q--){
        int qu;
        cin >> qu;
        if(qu == 1){
            int p, va;
            cin >> p >> va;
            if(p%2 == 0){
                int np = p/2;
                sb.upd(1, 1, nb, np, va);
            }
            else{
                int np = p/2+1;
                sa.upd(1, 1, na, np, va);
            }
        }
        else{
            int l, r;
            cin >> l >> r;
            if((r-l+1)%2 == 0){
                cout << 0 << endl;
            }
            else if(l%2 == 0){
                int ll = l/2, rr = r/2;
                int ans = sb.get(1, 1, nb, ll, rr);
                cout << ans << endl;
            }
            else{
                int ll = (l+1)/2, rr = (r+1)/2;
                int ans = sa.get(1, 1, na, ll, rr);
                cout << ans << endl;
            }
        }
    }
}

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