Codeforces #1019 : Div2 F. Maximize Nor

なるほど…。
https://codeforces.com/contest/2103/problem/F

問題

数列に対するnor値とは、数列の各値を左結合でnorを取った値とする。
各値は2進数でK桁以下であるような、N要素の整数列Aが与えられる。

Aの各要素A[i]に対し、A[i]を含むような連続部分列A[L..i...R]のうちnorの最大値を求めよ。

解法

各bitごとに見て行く。
区間[L,R]定めたとき、A[L...R]のnorの各bitの値bは以下のように決まる。

• Rの手前で、bitが1になっている箇所をxとする。
  • L≦x の場合、bはxとRの偶奇が異なれば1
  • L＞x の場合、bはLとRの偶奇が異なれば1

Rに対し、xの候補は高々K個であり、それ以外の箇所はLとRの偶奇でnorが同じ値が交互に登場する。
また、RごとにA[L...R]のnorの値は高々O(K)個である。
よってそれらを列挙し、区間最大値が取れるSegTreeに載せて行けばよい。

int T,N,K;
int A[101010];

int pre[17][101010];

template<class V,int NV> class SegTree_2 {
public:
	vector<V> val;
	SegTree_2(){val.resize(NV*2);};
	
	V getval(int k) {
		int e=k+NV;
		V ret=0;
		while(e>=1) ret=max(ret,val[e]), e/=2;
		return ret;
	}
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) val[k]=max(val[k],v);
		else if(l < y && x < r) {
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
		}
	}
	void update0(int k) {
		int e=k+NV;
		while(e>=1) val[e]=0, e/=2;
	}
};
SegTree_2<int,1<<20> st;

int hoge(int L,int R) {
	if(L<0||L>R) return -1;
	if(L==R) return A[L];
	int ret=0;
	int i;
	FOR(i,K) {
		int add=1<<i;
		if(pre[i][R]<L && L%2==R%2) add=0;
		if(pre[i][R]==L && L%2!=R%2) add=0;
		if(pre[i][R]>L && pre[i][R]%2==R%2) add=0;
		ret+=add;
	}
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		FOR(i,N) {
			cin>>A[i];
			st.update0(i);
		}
		FOR(j,17) {
			x=-1;
			FOR(i,N) {
				if(A[i]&(1<<j)) x=i;
				pre[j][i]=x;
			}
		}
		FOR(i,N) {
			st.update(i,i+1,A[i]);
			st.update(0,i+1,hoge(0,i));
			FOR(j,K) {
				for(x=pre[j][i]-2;x<=pre[j][i]+2;x++) {
					y=hoge(x,i);
					if(y>=0) st.update(x,i+1,y);
				}
			}
		}
		FOR(i,N) cout<<st.getval(i)<<" ";
		cout<<endl;
	}
}

まとめ

norやnandが絡む問題、状態遷移で頭が混乱する。