（修改序列问题）

给定长度为n的序列a，定义b[i]=a[1]^a[2]^…^a[i]，其中^为异或运算。每次操作你可以将序列a中任意一个元素修改为任意数，求最少几次操作可以使得b序列单调不降。

数据范围：n <= 10^6,0 <= a[i] <= 10^9。

提示：贪心，维护每一位可能的取值。

#include <iostream>


using namespace std;





const int N = 1000001;





int n, a[N], sta[30];





int main() {


	cin >> n;


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


		cin >> a[i];


	for(int i = 0; i < 30; i += 1)


		__(1)__ ;


	int ans = 0;


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


	{


		int msb = __(2)__ ;


		for(int j = 29; j >= 0; j -= 1) {


			if( __(3)__ ) {


				msb = j;


				break;


			}


		}


		if(msb == -1)


			continue;


		if(sta[msb] == 1) {


			ans += 1;


			fill(sta, sta + 30, __(4)__ );


		} else {


			for(int j = 0; j < 30; j += 1)


				if(sta[j] != -1)


					sta[j] ^= (a[i] >> j & 1);


			__(5)__;


		}


	}


	cout << ans << endl;


}

选择题