Codeforces #408 Div2 F. Sequence Recovery

これを本番通すのは厳しいな…。
http://codeforces.com/contest/796/problem/F

問題

N要素の数列Aがある。ただし初期値は不明である。
これらに以下のクエリiを順次行った結果が与えられる。

• ある区間(L[i],R[i])におけるAの最大値はX[i]であった。
• A[K[i]]を更新し、D[i]に置き換えた。

条件を満たすAの初期値のうち、bitwise-orの最大値を求めよ。
ただしAで取れる値は10^9以下の非負整数である。
なお、前者のクエリに対しX[i]が複数同じになることはない。

解法

まずbitwise-orは無視してA[i]の初期値の範囲を求めよう。
前者のクエリは、言い換えるとA[L[i]...R[i]]の初期値はX[i]以下であるということである。
よってこれらのクエリは範囲に対し最小値を設定するSegTreeで処理することができる。
ただし、後者のクエリが実行されると、そのようについては以下の最小値処理は無視される。

こうして各初期値の最大値を求めたら、クエリを再度実行し、結果に矛盾がないか検証しよう。
矛盾が生じた場合、条件を満たすAは存在しない。

そうでない場合、A[i]に対しbitwise-orを最大化することを考える。

• 最小値処理を成されていない要素が2個以上ある場合
  • 1つを2^29、もう1つを(2^29)-1にすれば、その時点でbitwise-orが(2^30)-1となることが確定する。
• そうでない場合
  • A[j]=vとなるjが複数あったとする。X[i]が複数同じになることはないため、A[j]のうち実際にX[i]を取るのは1つだけでよい。
  • よって、残りのjについてはA[j]はX[i]のMSBは0だが以下のbitはすべて1となる値を設定すればよい。
  • こうしてA[j]を定めた場合、最小値処理を成されていない要素A[k]が1個だけある場合がある。
  • その場合、他の要素のbitwise-orのうちクリアなbitを埋めるように(10^9を超えない範囲で)A[k]のbitを上から定めていく。

template<class V,int NV> class SegTree_2 {
public:
	vector<V> val;
	SegTree_2(){val.resize(NV*2,1<<30);}
	
	V getval(int entry) {
		entry += NV;
		int ret=1<<30;
		while(entry>0) ret=min(ret,val[entry]), entry>>=1;
		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]=min(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);
		}
	}
};

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=0;
	V comp(V l,V r){ return max(l,r);};
	
	SegTree_1(){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]);
	}
};

int N,M;
int T[303030],A[303030],B[303030],C[303030];

int ma[303030];
SegTree_2<int,1<<20> st_mi;
SegTree_1<int,1<<20> st_ma;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	MINUS(ma);
	FOR(i,M) {
		cin>>T[i]>>A[i]>>B[i];
		A[i]--;
		if(T[i]==1) {
			cin>>C[i];
			st_mi.update(A[i],B[i],C[i]);
		}
		else {
			if(ma[A[i]]==-1) ma[A[i]]=st_mi.getval(A[i]);
		}
	}
	FOR(i,N) {
		if(ma[i]==-1) ma[i]=st_mi.getval(i);
		st_ma.update(i,ma[i]);
	}
	
	FOR(i,M) {
		if(T[i]==1) {
			if(st_ma.getval(A[i],B[i])!=C[i]) return _P("NO\n");
		}
		else {
			st_ma.update(A[i],B[i]);
		}
	}
	
	map<int,int> P;
	FOR(i,N) P[ma[i]]++;
	
	_P("YES\n");
	if(P[1<<30]>=2) {
		int first=1;
		FOR(i,N) {
			if(ma[i]==1<<30) {
				if(first) {
					ma[i]=(1<<29)-1;
					first=0;
				}
				else ma[i]=1000000000;
			}
			_P("%d ",ma[i]);
		}
	}
	else {
		int ret=0;
		FOR(i,N) {
			if(ma[i]==0 || ma[i]==1<<30) continue;
			P[ma[i]]--;
			if(P[ma[i]]>0) {
				int x=0;
				while(x*2+1<=ma[i]) x=x*2+1;
				ma[i]=x;
			}
			ret |= ma[i];
		}
		int left=0;
		for(i=29;i>=0;i--) if((ret&(1<<i))==0 && left+(1<<i)<=1000000000) left += 1<<i;
		FOR(i,N) {
			if(ma[i]==1<<30) ma[i]=left;
			_P("%d ",ma[i]);
		}
	}
}

まとめ

A[i]の最大値を求めるところまでは思いついたが、その後が詰められなかった。