Submission #1159081

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159081		75_yabuki	XORanges (eJOI19_xoranges)	C++20	100 / 100	53 ms	6224 KiB

xoranges

#define _DEB231UG
// #include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
// using namespace atcoder;
#define endl "\n"
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define CNT_LOWER(v, n) (ll)(lower_bound((v).begin(), (v).end(), (n)) - (v).begin())
#define CNT_UPPER(v, n) (ll)(upper_bound((v).begin(), (v).end(), (n)) - (v).begin())
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef vector<int> vi;
typedef vector<pii> vii;
const long double pi = acos(-1.0);
const int INF = 1987654321;
const ll LLINF = 1e18;
const double eps = 1e-9;
template<class T>bool chmax(T& a, const T& b) { if (a <= b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b <= a) { a = b; return 1; } return 0; }

//////////////////////

// #ifndef ONLINE_JUDGE
// #include "template.cpp"
// #else
// #define debug(...)
// #define debugArr(...)
// #endif

//////////////////////
ll arr[202020];
struct BIT{
    ll n;
    vector<ll> tree;
    BIT(ll n):n(n+10),tree(n+10,0){}

    void update(ll i,ll val){
        for(;i<=n;i+=i&-i)tree[i]^=val;
    }

    ll query(ll i){
        ll res=0;
        for(;i>0;i-=i&-i)
            res^=tree[i];
        return res;
    }

    ll queryRange(ll l,ll r){
        return query(r)^query(l-1);
    }
};


int main(){
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N,Q;cin>>N>>Q;
     
    for(int i=1;i<=N;i++)cin>>arr[i];
    BIT odd(N),even(N);
    for(int i=1;i<=N;i++){
        if(i%2==0)even.update(i,arr[i]);
        else odd.update(i,arr[i]);
    }
    while(Q--){
        int q;cin>>q;
        if(q==1){
            ll i,j;cin>>i>>j;
            // V[i]=j;
            // ll sex=V[i]^j;
            if(i%2==0)even.update(i,arr[i]^j);
            else odd.update(i,arr[i]^j);
            arr[i]=j;
        }
        else{
            int l,u;cin>>l>>u;
            if(l%2!=u%2)cout<<0<<endl;
            else{
                if(l%2==0)cout<<even.queryRange(l,u)<<endl;
                else cout<<odd.queryRange(l,u)<<endl;
            }
        }
    }

    return 0;
}

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