牛客——简单瞎搞题（bitsit优化DP）
UP:好像01的东西都会有些奇奇怪怪的优化，比如双端队列BFS就是一个很秀的算法。https://blog.csdn.net/weixin_45675097/article/details/106265696
前言：（bitset的学习）
很容易看出来是背包问题，我们用dp[i] [j] 表示只由前i个数字构成j，分界点就是第i个数字是否选择。当dp[i-1] [j-x*x ]==1时可以转移到dp[i] [j] 。但这样的话复杂度就是O（n^5），有些爆表了。
根据雨巨的思路，可以用bitset来优化，bitset就是一个只含有0和1的类型，类似bool数组，但是空间出奇的小。
常用函数：
bitset<maxn>tmp;///定义的时候就需要初始化位数 tmp.size();///返回位数 tmp.count;//返回1的个数
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000010;
bitset<maxn>tmp,res;
int main(){
int n;cin>>n;
res[0]=1;
for(int i=1;i<=n;i++){
int l,r;
scanf("%d%d",&l,&r);
for(int j=l;j<=r;j++)
tmp|=res<<(j*j);
res=tmp;
tmp.reset();
}
cout<<res.count()<<endl;
return 0;
}
