Codeforces ECR #137 : F. Intersection and Union

なんかEよりすんなり解いてるな。
https://codeforces.com/contest/1743/problem/F

問題

N個の区間を成す整数集合S[i]が与えられる。
S[0] op S[1] op … S[N-1]という演算を考える。
opは、和集合・積集合・差集合のいずれかの演算子が来るとする。

演算子は3^(N-1)通り考えられるが、それぞれ演算結果の要素数の和を求めよ。

解法

SegTreeのi番目の要素には、i番目の演算が有効な場合、現在の区間がSに入るか入らないかの変換ルールを載せるようにする。

[0,300000]の区間に対する平面走査を行いながら、値xを見たとき、何番目の演算が有効/無効かをSegTreeに載せて行き、最終的にxが演算結果に含まれるケースを数え上げて行こう。

int N;
int L[303030],R[303030];
const ll mo=998244353;

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val[2][2];
	
	void init(int N){
		val[0][0]=val[0][1]=val[1][0]=val[1][1]=vector<V>(NV*2);
		int i;
		FOR(i,2*NV) val[0][0][i]=val[1][1][i]=1;
	};
	void update(int entry, V v) {
		entry += NV;
		val[0][0][entry]=0;
		val[1][0][entry]=0;
		val[0][1][entry]=0;
		val[1][1][entry]=0;
		if(v==0||v==2) {
			val[0][0][entry]=3;
			val[1][0][entry]=1; // and
			val[1][1][entry]=2; // xor, or
		}
		else {
			val[0][0][entry]=1; // and
			val[0][1][entry]=2; // or,xor
			val[1][0][entry]=1; // xor
			val[1][1][entry]=2; // and or
		}
		while(entry>1) {
			entry>>=1;
			int a,b,c;
			FOR(a,2) FOR(b,2) {
				val[a][b][entry]=0;
			}
			FOR(a,2) FOR(b,2) FOR(c,2) {
				(val[a][c][entry]+=val[a][b][entry*2]*val[b][c][entry*2+1])%=mo;
			}
		}
	}
};

vector<int> add[303030],del[303030];
SegTree_1<ll,1<<20> st;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>L[i]>>R[i];
		if(i) {
			add[L[i]].push_back(i-1);
			del[R[i]].push_back(i-1);
		}
	}
	st.init(N-1);
	FOR(i,N-1) st.update(i,0);
	
	ll sum=0;
	for(i=0;i<=300000;i++) {
		FORR(e,add[i]) {
			st.update(e,1);
		}
		ll add=0;
		if(L[0]<=i&&i<=R[0]) {
			add=st.val[1][1][1];
		}
		else {
			add=st.val[0][1][1];
		}
		//cout<<add<<" "<<st.val[0][0][1]<<" "<<st.val[0][1][1]<<" "<<st.val[1][0][1]<<" "<<st.val[1][1][1]<<" "<<endl;
		(sum+=add)%=mo;
		FORR(e,del[i]) st.update(e,0);
	}
	cout<<sum<<endl;
}

まとめ

ややこしいけどどうにか普通に解けたな。