Submission #401514

#	Time	Username	Problem	Language	Result	Execution time	Memory
401514		raid	XORanges (eJOI19_xoranges)	C++17	100 / 100	657 ms	13420 KiB

xoranges

#include <iostream>

using namespace std;

const int MAXN = 200002;
int v[MAXN], n;

struct segtree {
  int tree[4 * MAXN], m;
  
  void init( int dim ) {
	for ( int i = 0; i <= 4 * n; ++i ) {
      this -> tree[i] = 0;
	}
	this -> m = dim;
  }
  void update( int node, int l, int r, int x, int pos ) {
	if ( l == r ) {
      this -> tree[node] = x;
	  return;
	}
	int mid = (l + r) / 2;
	if ( pos <= mid ) {
      update( 2 * node, l, mid, x, pos );
	} else {
	  update( 2 * node + 1, mid + 1, r, x, pos );
	}
	this -> tree[node] = this -> tree[2 * node] ^ this -> tree[2 * node + 1];
  }
  int query( int node, int l, int r, int x, int y ) {
    int a = 0, b = 0;
	if ( x <= l && r <= y ) {
	  return this -> tree[node];
	}
	int mid = (l + r) / 2;
	if ( x <= mid ) {
      a = query( 2 * node, l, mid, x, y );
	}
	if ( y > mid ) {
      b = query( 2 * node + 1, mid + 1, r, x, y );
	}
	return a ^ b;
  }
  void update( int x, int pos ) {
	update( 1, 1, m, x, pos );
  } 
  int query( int x, int y ) {
    return query( 1, 1, m, x, y );
  }
};

int main() {
  int q, t, x, y;
  segtree odd, even;

  cin >> n >> q;
  for ( int i = 1; i <= n; ++i ) {
	cin >> v[i];
  }
  odd.init( ((n + 1) >> 1) );
  even.init( (n >> 1) );
  for ( int i = 1; i <= n; ++i ) {
    if ( i & 1 ) {
      odd.update( v[i], (i >> 1) + 1 );
	} else {
      even.update( v[i], (i >> 1) );
	}
  }
  while ( q-- ) {
    cin >> t >> x >> y;
    if ( t == 1 ) {
	  if ( x & 1 ) {
        odd.update( y, (x >> 1) + 1 );      
	  } else {
        even.update( y, (x >> 1) );
	  }
	} else {
	  if ( (y - x + 1) & 1 ) {
        if ( x & 1 ) {
		  cout << odd.query( (x >> 1) + 1, (y >> 1) + 1 ) << "\n";
		} else {
		  cout << even.query( (x >> 1), (y >> 1) ) << "\n";
		}
	  } else {
		cout << "0\n";
	  }
	}
  }
  return 0;
}

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