Submission #999962

#	Time	Username	Problem	Language	Result	Execution time	Memory
999962		0pt1mus23	XORanges (eJOI19_xoranges)	C++14	100 / 100	103 ms	22100 KiB

xoranges

/*       ==========================
        | Bismillahirrahmanirrahim | ⠀⠀ 
         ==========================
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⠁⠸⢳⡄⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⠃⠀⠀⢸⠸⠀⡠⣄⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡠⠃⠀⠀⢠⣞⣀⡿⠀⠀⣧⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣠⡖⠁⠀⠀⠀⢸⠈⢈⡇⠀⢀⡏⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⡴⠩⢠⡴⠀⠀⠀⠀⠀⠈⡶⠉⠀⠀⡸⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⢀⠎⢠⣇⠏⠀⠀⠀⠀⠀⠀⠀⠁⠀⢀⠄⡇⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢠⠏⠀⢸⣿⣴⠀⠀⠀⠀⠀⠀⣆⣀⢾⢟⠴⡇⠀⠀⠀⠀⠀<===== this is wolf, not everest
⠀⠀⠀⠀⠀⢀⣿⠀⠠⣄⠸⢹⣦⠀⠀⡄⠀⠀⢋⡟⠀⠀⠁⣇⠀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⡾⠁⢠⠀⣿⠃⠘⢹⣦⢠⣼⠀⠀⠉⠀⠀⠀⠀⢸⡀⠀⠀⠀⠀
⠀⠀⢀⣴⠫⠤⣶⣿⢀⡏⠀⠀⠘⢸⡟⠋⠀⠀⠀⠀⠀⠀⠀⠀⢳⠀⠀⠀⠀
⠐⠿⢿⣿⣤⣴⣿⣣⢾⡄⠀⠀⠀⠀⠳⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢣⠀⠀⠀
⠀⠀⠀⣨⣟⡍⠉⠚⠹⣇⡄⠀⠀⠀⠀⠀⠀⠀⠀⠈⢦⠀⠀⢀⡀⣾⡇⠀⠀
⠀⠀⢠⠟⣹⣧⠃⠀⠀⢿⢻⡀⢄⠀⠀⠀⠀⠐⣦⡀⣸⣆⠀⣾⣧⣯⢻⠀⠀
⠀⠀⠘⣰⣿⣿⡄⡆⠀⠀⠀⠳⣼⢦⡘⣄⠀⠀⡟⡷⠃⠘⢶⣿⡎⠻⣆⠀⠀
⠀⠀⠀⡟⡿⢿⡿⠀⠀⠀⠀⠀⠙⠀⠻⢯⢷⣼⠁⠁⠀⠀⠀⠙⢿⡄⡈⢆⠀
⠀⠀⠀⠀⡇⣿⡅⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠦⠀⠀⠀⠀⠀⠀⡇⢹⢿⡀
⠀⠀⠀⠀⠁⠛⠓⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠼⠇⠁ 

m : 11059739 -> l ~23
p : 4567896467
*/
#pragma GCC optimize("O3", "inline")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define all(v) v.begin(), v.end()
#define ins insert
#define pb push_back
#define int long long int
#define pii pair<int, int>
#define str string
#define endl '\n'
#define drop(x) cout<<(x)<<endl;return;
// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <class T> using ot = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int mod = 998244353, sze =8*1e5 + 10, inf = 1e9, prime = 4567896467;

struct genuisahmed{

    vector<int> lst;
    int n;
    int T1[sze];
    int T2[sze];
    genuisahmed(int _n,vector<int> arr){
        lst=arr;
        n=_n;
        build(1,0,n-1);
    }

    void build(int node,int l,int r){
        if(l==r){
            if((l+1)%2){
                T1[node]=lst[l];
            }
            else{
                T2[node]=lst[l];
            }
            return;
        }
        int mid = (l+r)/2;
        build(2*node,l,mid);
        build(2*node +1,mid+1,r);
        T1[node]= T1[node*2] ^ T1[node *2 +1];
        T2[node]= T2[node*2] ^ T2[node *2 +1];
    }

    int qry1(int node,int lx,int rx,int l,int r){
        if(l>rx || r<lx){
            return 0;
        }
        if(l>=lx && r<=rx){
            return T1[node];
        }
        int mid = (l+r)/2;
        int left = qry1(2*node,lx,rx,l,mid);
        int right = qry1(2*node +1,lx,rx,mid+1,r);
        return left ^ right;
    }
    int qry1(int l,int r){
        return qry1(1,l,r,0,n-1);
    }
    int qry2(int node,int lx,int rx,int l,int r){
        if(l>rx || r<lx){
            return 0;
        }
        if(l>=lx && r<=rx){
            return T2[node];
        }
        int mid = (l+r)/2;
        int left = qry2(2*node,lx,rx,l,mid);
        int right = qry2(2*node +1,lx,rx,mid+1,r);
        return left ^ right;
    }
    int qry2(int l,int r){
        return qry2(1,l,r,0,n-1);
    }

    void update(int node,int idx,int l,int r,int v){
        if(l==r){
            if((l+1)%2){
                T1[node]=v;
            }
            else{
                T2[node]=v;
            }
            return;
        }
        int mid = (l+r)/2;
        if(mid>=idx){
            update(2*node,idx,l,mid,v);
        }
        else{
            update(2*node+1,idx,mid+1,r,v);

        }
        T1[node]= T1[node*2] ^ T1[node *2 +1];
        T2[node]= T2[node*2] ^ T2[node *2 +1];
    }

    void update(int idx,int v){
        update(1,idx,0,n-1,v);
    }

    
};

void mal(){
    /*
        obvs :
        range len cut olanda cavab 0 olur

        cut segtree

        basladigi indexe gore, cut indexlilerin xoru goturulmur
    */
    // str s="abcdefgjk";
    // int n=s.size();
    // map<char,int> count;
    // for(int i=1;i<=n;i++){
    //     for(int j=0;j+i<=n;j++){
    //         str t="";
    //         for(int x=j;x<j+i;x++){
    //             t+=s[x];
    //             count[s[x]]++;
    //         }    
    //         cout<<t<<" ";
    //     }    
    //     cout<<endl;
    // }
    // for(auto v:s){
    //     cout<<v<<" "<<count[v]<<endl;
    // }

    int n,q;
    cin>>n>>q;
    vector<int> arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    genuisahmed ahmed(n,arr);
    vector<pii> tekqueries,cutqueries;
    while(q--){
        int op;
        cin>>op;

        if(op==2){
            int l,r;
            cin>>l>>r;

            if( (r-l+1)%2==0){
                cout<<0<<endl;
            }
            else{
                l--;
                r--;
                if((l+1)%2){
                    // tekden baslayir, cut indexliler sayilmiyacaq
                    cout<<ahmed.qry1(l,r)<<endl;
                }
                else{
                    // cutden basliyir, TEKLERI SIL
                    cout<<ahmed.qry2(l,r)<<endl;
                }
            }
        }
        else{
            int idx,v;
            cin>>idx>>v;
            ahmed.update(--idx,v);
        }
    }
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int tt = 1;
    // cin>>tt;

    while (tt--) mal();
}

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