Submission #285875

#	Time	Username	Problem	Language	Result	Execution time	Memory
285875		wildturtle	XORanges (eJOI19_xoranges)	C++14	100 / 100	936 ms	9720 KiB

xoranges

#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,i,e,f,g,n,m,k,l,A[500005],x,BITree[500005],BITree1[500005],t;
int getSum(int index) {
    int sum = 0;
    index = index + 1; 
    while (index>0) {
        sum ^= BITree[index]; 
        index -= index & (-index); 
    } 
    return sum; 
}
void updateBIT(int index, int val) {
    index = index + 1; 
    while (index <= 200005) { 
    BITree[index] ^= val; 
    index += index & (-index); 
    } 
} 
int getSum1(int index) {
    int sum = 0;
    index = index + 1; 
    while (index>0) {
        sum ^= BITree1[index]; 
        index -= index & (-index); 
    } 
    return sum; 
}
void updateBIT1(int index, int val) {
    index = index + 1; 
    while (index <= 200005) { 
    BITree1[index] ^= val; 
    index += index & (-index); 
    } 
} 
int main() {
    cin>>n>>t;
    for(long long i=1;i<=n;i++) {
        cin>>A[i];
        if(i%2==1) updateBIT(i/2+i%2,A[i]);
        else updateBIT1(i/2,A[i]);
    }
    while(t--) {
        cin>>a;
        if(a==1) {
            cin>>a>>b;
            if(a%2==1) {
                updateBIT(a/2+a%2,A[a]);
                updateBIT(a/2+a%2,b);
                A[a]=b;
            }
            else {
                updateBIT1(a/2,A[a]);
                updateBIT1(a/2,b);
                A[a]=b;                
            }
        }
        else {
            cin>>a>>b;
            if(a%2!=b%2) { cout<<0<<endl; continue; }
            if(a%2==1) {
                a=a/2+a%2;
                b=b/2+b%2;
                c=getSum(a-1)^getSum(b);
                cout<<c<<endl;
            }
            else {
                a/=2;
                b/=2;
                c=getSum1(a-1)^getSum1(b);
                cout<<c<<endl;
            }
        }
    }
}

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