yukicoder : No.2901 Logical Sum of Substring

解法は割とオーソドックスな気がする。
https://yukicoder.me/problems/no/2901

問題

整数列Aと、正整数Kが与えられる。
以下のクエリに順次答えよ。

• Aの1要素の値を更新する。
• Aの区間A[L...R]が指定される。この部分列の部分列のうち、orを取ると(2^K-1)となるものの最短の長さを答えよ。

解法

SegTreeで解く。SegTreeのノードには下記の値を乗せる。

• 対応する部分列の長さ
• 部分列に含まれる、orを取ると(2^K-1)となる部分列の最短長。
• prefix orのうち、値が変わるところだけ値と位置を圧縮して持つ
• suffix orのうち、値が変わるところだけ値と位置を圧縮して持つ

数列の全部ではなく、圧縮して意味がある(orを取ったとき値が変わる)場所だけ残すのがコツ。
ノードに載せる情報がO(K)で済むし、ノードのマージがO(K)で済む。以下はマージをO(K^2)でやっているが、それでも間に合う。

int T;
int X,Y,M;
set<int> E[202020];
int okA[202020],okB[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>X>>Y>>M;
		FOR(i,X+Y) E[i].clear();
		FOR(i,M) {
			cin>>x>>y;
			E[x-1].insert(y-1);
		}
		
		int sa=0,sb=0;
		while(1) {
			sa=sb=0;
			FOR(i,Y) {
				okB[i]=(rand()<rand());
				sb+=okB[i];
			}
			FOR(i,X) {
				x=0;
				FORR(e,E[i]) x^=okB[e];
				okA[i]=x;
				sa+=x;
			}
			
			if(sa+sb>=(X+Y+1)/2) break;
		}
		cout<<sa<<" "<<sb<<endl;
		FOR(i,X) if(okA[i]) cout<<i+1<<" ";
		cout<<endl;
		FOR(i,Y) if(okB[i]) cout<<i+1<<" ";
		cout<<endl;
	}
		
		
}

まとめ

prefix orやandの時には座標圧縮することを忘れないようにしないとな。