Codeforces ECR #084 : F. AND Segments

Fまではなんとか解けたんだけどね。
https://codeforces.com/contest/1327/problem/F

問題

M個の区間と設定値の組(L[i],R[i],X[i])が与えられる。
0～(2^K)-1の範囲をとるN要素の整数列Aを考える。
Aの組み合わせとして、M個の組に対し、その区間のandを取った値がXになるのは何通りか。

解法

2進数表記の桁毎に考える。
今見ている桁について、X[i]が1となる組に対しては、その区間の値がすべて1でなければならない。
あとは、直前に登場した0がどこにあるか、という状態に対する値を用いてDPしていけばよい。

なお、BITを使うとこの処理は楽なのだが、そうするとO(K(NlogN+M))かかってしまいTLEする。
BITをやめて適宜累積和をとるようにすると間に合う。

int N,K,M;
int L[505050],R[505050],X[505050];
int add[505050][30];
const ll mo=998244353;

vector<pair<int,int>> E[30];
ll dp[505050];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d%d",&N,&K,&M);
	FOR(i,M) {
		scanf("%d%d%d",&L[i],&R[i],&X[i]);
		R[i]++;
		FOR(j,30) {
			if(X[i]&(1<<j)) add[L[i]][j]++,add[R[i]][j]--;
			else E[j].push_back({L[i],R[i]});
		}
	}
	
	FOR(j,30) {
		FOR(i,N) {
			add[i+1][j]+=add[i][j];
		}
	}
	
	
	ll ret=1;
	FOR(i,K) {
		vector<pair<int,int>> R;
		sort(ALL(E[i]));
		FORR(e,E[i]) {
			while(R.size() && e.second<=R.back().second) R.pop_back();
			if(R.empty() || R.back().first<e.first) R.push_back(e);
		}
		R.push_back({N+2,N+3});
		ZERO(dp);
		dp[0]=1;
		dp[1]=mo-1;
		int cur=0;
		FOR(j,N+1) {
			if(j) {
				dp[j]+=dp[j-1];
				if(dp[j]>=mo) dp[j]-=mo;
			}
			if(add[j][i]==0) {
				ll v=dp[j];
				while(R[cur].first<=j) cur++;
				dp[j+1]+=v;
				if(dp[j+1]>=mo) dp[j+1]-=mo;
				dp[R[cur].second]+=mo-v;
				if(dp[R[cur].second]>=mo) dp[R[cur].second]-=mo;
			}
		}
		dp[N+1]+=dp[N];
		ret=ret*dp[N+1]%mo;
	}
	cout<<ret<<endl;
	
}

まとめ

BITを避けるのにちょっと手間取った。