Submission #447577

#	Time	Username	Problem	Language	Result	Execution time	Memory
447577		MrDeboo	XORanges (eJOI19_xoranges)	C++17	100 / 100	180 ms	13568 KiB

xoranges

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define mod 1000000007
#define INF 1000000000000000000
using namespace std;
int seg1[600000];
int seg2[600000];
int N,a,b,c;
int solve1(int l=1,int r=N,int in=1){
    if(r<b||c<l)return 0;
    if(l>=b&&r<=c)return seg1[in];
    int mid=(l+r)/2;
    return solve1(l,mid,in*2)^solve1(mid+1,r,in*2+1);
}
int solve2(int l=1,int r=N,int in=1){
    if(r<b||c<l)return 0;
    if(l>=b&&r<=c)return seg2[in];
    int mid=(l+r)/2;
    return solve2(l,mid,in*2)^solve2(mid+1,r,in*2+1);
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("tttt.in", "r", stdin);
    //freopen("tttt.out", "w", stdout);
    int n,q;
    cin>>n>>q;
    N=exp2(ceil(log2(n)));
    for(int i=0;i<n;i++){
        if(i&1)cin>>seg1[i+N];
        else cin>>seg2[i+N];
    }
    for(int i=N-1;i;i--)seg1[i]=seg1[i*2]^seg1[i*2+1];
    for(int i=N-1;i;i--)seg2[i]=seg2[i*2]^seg2[i*2+1];
    // cout<<seg2[1]<<endl;
    while(q--){
        cin>>a>>b>>c;
        if(a&1){
            int in=N+b-1;
            if(b&1){
                seg2[in]=c;
                in/=2;
                while(in){
                    seg2[in]=seg2[in*2]^seg2[in*2+1];
                    in/=2;
                }
            }
            else{
                seg1[in]=c;
                in/=2;
                while(in){
                    seg1[in]=seg1[in*2]^seg1[in*2+1];
                    in/=2;
                }
            }
        }
        else{
            if((c-b+1)%2==1){
                if(b&1)cout<<solve2()<<endl;
                else cout<<solve1()<<endl;
            }
            else{
                cout<<0<<endl;
            }
        }
    }
}
/*
a b c
ab bc
abc
a- 3
b- 4
c- 3
-------------
a b c d
ab bc cd
abc bcd
abcd
a- 4
b- 6
c- 6
d- 4
--------------
a b c d e
ab bc cd de
abc bcd cde
abcd bcde
abcde
a- 5
b- 8
c- 9
d- 8
e- 5
*/

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