AtCoder ARC #207 (AtCoder Japan Open -予選-) : C - Combine to Make Non-decreasing

手間取ったけど辛うじて解けて良かった。
https://atcoder.jp/contests/arc207/tasks/arc207_c

問題

整数列Aが与えられる。
Aをいくつかの連続部分列に分割し、各部分列をそのbitwise-orに置き換えたとき単調増加となるようにしたい。
最大何個の連続部分列に分割できるか。

解法

max(A)は2^30以下である。
例えば連続部分列の端を片方決めたとき、もう片方を動かしてもその値は高々31通りである。
よって以下を考える。

dp(n,v) := Aのうちn要素目までの分割を考えたとき、最後の部分列のbitwise-orがvとなるようなときの最大分割数
この時、A[n+1]～A[m]までを次の部分列とする場合、mを動かしてもそのbitwise-or wも高々31通りになる。
そのうちw≧v以上となるものに対し、dp(m,w)を更新すればよい。
dpのテーブルを直に2次元で持つと更新が大変なので、wが一致する範囲においてはイベント走査の要領でテーブルを使いまわそう。

int N;
int A[202020];

template<class V,int NV> class SegTree_ma {
public:
	vector<V> val;
	static V const def=0;
	V comp(V l,V r){ return l|r;};
	
	SegTree_ma(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=v;
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_ma<int,1<<20> st;

map<int,int> M[202020];
int nex[30][202020];
vector<pair<int,int>> add[202020],del[202020];

map<int,multiset<int>> memo;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
	}
	FOR(j,30) nex[j][N]=N;
	for(i=N-1;i>=0;i--) {
		FOR(j,30) {
			nex[j][i]=nex[j][i+1];
			if(A[i]&(1<<j)) nex[j][i]=i+1;
		}
	}
	add[0].push_back({0,0});
	del[0].push_back({0,0});
	int ret=0;
	FOR(i,N) {
		FORR2(a,b,add[i]) {
			memo[a].insert(b);
			ret=max(ret,b);
		}
		vector<int> cand={N+1};
		FOR(j,30) cand.push_back(nex[j][i]);
		sort(ALL(cand));
		cand.erase(unique(ALL(cand)),cand.end());
		
		FORR2(a,b,memo) {
			int v=0;
			int num=*b.rbegin();
			FOR(j,cand.size()-1) {
				v|=A[cand[j]-1];
				if(v>=a) {
					add[cand[j]].push_back({v,num+1});
					del[cand[j+1]-1].push_back({v,num+1});
				}
			}
		}
		
		FORR2(a,b,del[i]) {
			memo[a].erase(memo[a].find(b));
			if(memo[a].empty()) memo.erase(a);
		}
	}
	FORR2(a,b,add[N]) {
		ret=max(ret,b);
	}
	
	
	cout<<ret<<endl;
	
}

まとめ

bitwise-orの種類が少ないことを思い出すまでちょっと手間取った。