Codeforces #622 Div2 D. Happy New Year

参加が遅れたので全完できないのはしょうがないか…。
https://codeforces.com/contest/1313/problem/D

問題

M要素の整数列Aがあり、初期値が0である。
ここでN個の区間が与えられる。
各区間は1回まで選択でき、選択するとAの区間内がインクリメントされる。
なお、Aの各要素は最大8区間までしか含まれない。

最大でAの何要素を奇数にできるか。

解法

各要素は8区間しか覆われないので、整数列の端から走査して「その要素を含む8区間の選択の有無2^8通りを状態にもって、奇数個にカバーされる要素数の最大値をDP」でよい。
8つの区間のスロットがあると考えて、新たな区間が始まるときは、8つのうち空きスロットを適宜割り当て用。

int N,M,K;
int L[101010],R[101010];
int ID[101010];
vector<pair<int,int>> add;

int from[256];
int to[256];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	
	FOR(i,N) {
		cin>>L[i]>>R[i];
		L[i]--;
		add.push_back({L[i],i+N});
		add.push_back({R[i],i});
	}
	int mask=0;
	sort(ALL(add));
	
	FOR(i,256) from[i]=-1<<30;
	from[0]=0;
	int pre=0;
	
	FORR(v,add) {
		FOR(i,256) if(__builtin_popcount(i)%2==1) from[i]+=v.first-pre;
		pre=v.first;
		if(v.second<N) {
			x=ID[v.second];
			mask ^= 1<<x;
			FOR(i,256) if(i&(1<<x)) {
				from[i^(1<<x)]=max(from[i^(1<<x)],from[i]);
				from[i]=-1<<30;
			}
		}
		else {
			FOR(i,8) if((mask&(1<<i))==0)  break;
			
			x=ID[v.second-N]=i;
			mask ^= 1<<x;
			FOR(i,256) if(i&(1<<x)) from[i]=from[i^(1<<x)];
		}
	}
	
	int ret=0;
	FOR(i,256) ret=max(ret,from[i]+(__builtin_popcount(i)%2)*(M-pre));
	cout<<ret<<endl;
}

まとめ

これ要素をカバーする区間数に制限がないと難易度どうなるんだろ。