HDU6579 Operation

问题分析

区间求异或和最大，比较自然的想到了线性基。而每次求一个区间的线性基显然是行不通的。我们考虑在每个位置求出首位置到当前位置的线性基。同时我们要使线性基中高位的位置所选的数尽量靠后。这样我们维护线性基的时候在同时维护一个位置信息就好了。

参考程序

#include <bits/stdc++.h>

//#define Debug

using namespace std;

const int Maxn = 1000010;

const int MaxBit = 30;

int n, m, A[ Maxn ], BitBase[ Maxn ][ MaxBit ], Pos[ Maxn ][ MaxBit ];

void Work();

int main() {

	int TestCases;

	scanf( "%d", &TestCases );

	for( ; TestCases--; ) Work();

	return 0;

}

void Work() {

	scanf( "%d%d", &n, &m );

	for( int i = 1; i <= n; ++i ) scanf( "%d", A + i );

	memset( BitBase, 0, sizeof( BitBase ) );

	memset( Pos, 0, sizeof( Pos ) );

	for( int i = 1; i <= n; ++i ) {

		for( int j = 0; j < MaxBit; ++j ) BitBase[ i ][ j ] = BitBase[ i - 1 ][ j ], Pos[ i ][ j ] = Pos[ i - 1 ][ j ];

		int Position = i;

		for( int j = MaxBit - 1; j >= 0; --j )

			if( ( A[ i ] >> j ) & 1 )

				if( BitBase[ i ][ j ] ) {

					if( Pos[ i ][ j ] < Position ) {

						swap( BitBase[ i ][ j ], A[ i ] );

						swap( Pos[ i ][ j ], Position );

					}

					A[ i ] ^= BitBase[ i ][ j ];

				} else {

					BitBase[ i ][ j ] = A[ i ];

					Pos[ i ][ j ] = Position;

					break;

				}

	}

	#ifdef Debug

		for( int i = 1; i <= n; ++i ) {

			for( int j = 0; j < MaxBit; ++j ) printf( "(%d,%d), ", BitBase[ i ][ j ], Pos[ i ][ j ] );

			printf( "\n" );

		}

	#endif

	int LastAns = 0;

	for( int i = 1; i <= m; ++i ) {

		int Opt; scanf( "%d", &Opt );

		if( Opt == 1 ) {

			++n; scanf( "%d", A + n );

			A[ n ] ^= LastAns;

			for( int j = 0; j < MaxBit; ++j ) BitBase[ n ][ j ] = BitBase[ n - 1 ][ j ], Pos[ n ][ j ] = Pos[ n - 1 ][ j ];

			int Position = n;

			for( int j = MaxBit - 1; j >= 0; --j )

				if( ( A[ n ] >> j ) & 1 )

					if( !BitBase[ n ][ j ] ) {

						BitBase[ n ][ j ] = A[ n ];

						Pos[ n ][ j ] = Position;

						break;

					} else {

						if( Pos[ n ][ j ] < Position ) {

							swap( BitBase[ n ][ j ], A[ n ] );

							swap( Pos[ n ][ j ], Position );

						}

						A[ n ] ^= BitBase[ n ][ j ];

					}

		} else {

			int l, r; scanf( "%d%d", &l, &r );

			l = ( l ^ LastAns ) % n + 1;

			r = ( r ^ LastAns ) % n + 1;

			if( l > r ) swap( l, r );

			LastAns = 0;

			for( int j = MaxBit - 1; j >= 0; --j )

				if( ( ( LastAns >> j ) & 1 ) == 0 && Pos[ r ][ j ] >= l )

					LastAns ^= BitBase[ r ][ j ];

			printf( "%d\n", LastAns );

		}

	}

	return;

}

巴特西

HDU6579 Operation

问题分析

参考程序

最新文章

热门文章