牛客 132C 简单瞎搞题 (bitset)

大意: 给定序列$a$的第$i$个元素的取值范围$[L_i,R_i]$, 求$a$的平方和的种类数.

用bitset优化, 复杂度$O(frac{n^5}{omega})$

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <bitset>
#define REP(i,a,n) for(int i=a;i<=n;++i)
using namespace std;

const int N = 1e6+10;
int n, a[N];
bitset<N> ans, t;

int main() {
	scanf("%d", &n);
	ans[0] = 1;
	REP(i,1,n) {
		int l, r;
		scanf("%d%d", &l, &r);
		t.reset();
		REP(j,l,r) t |= ans<<(j*j);
		ans = t;
	}
	printf("%d
", (int)ans.count());
}