简单瞎搞题

题意:求s有多少种情况....
题解:bitset,第一次认识这个东西
我们先看暴力怎么做,每次输入一个区间,然后对于每一个位置的元素,与上一次的到的所有元素相加,然后去重
比如输入[1,2],然后我们之前输入的区间一共可以得到[4,9,16];
那么可以新的得到[5,10,17,8,13,20],然后新得到的会出现重复,具体的可以根据样例试一试
然后如果一直输入的右区间都是100的话,输入100次最大可以得到100100100=1e6,然后区间长度100,100个区间.....1e10的时间复杂度,
然后现在用bitset,现在有[4,9,16]这三个数可以改写成二进制00000001000000100001000这种情况倒数第4,9,16位为1,然后每次比如说+4,相当于上面这个串后面加4个0,即000000010000001000010000000,然后如果此时输入的是[1,2],2的情况如左边,1的情况就是后面加1个0,即00000001000000100001000,然后对于[1,2]得到的串取或运算即000010010001001010010000,然后统计1的个数

bitset<4> bitset1;　　//无参构造，长度为４，默认每一位为０

 bitset<8> bitset2(12);　　//长度为８，二进制保存，前面用０补充

 string s = "100101";
 bitset<10> bitset3(s);　　//长度为10，前面用０补充

 char s2[] = "10101";
 bitset<13> bitset4(s2);　　//长度为13，前面用０补充

 cout << bitset1 << endl;　　//0000
 cout << bitset2 << endl;　　//00001100
 cout << bitset3 << endl;　　//0000100101
 cout << bitset4 << endl;　　//0000000010101
bitset<2> bitset1(12);　　//12的二进制为1100（长度为４），但bitset1的size=2，只取后面部分，即00

 string s = "100101";　　
 bitset<4> bitset2(s);　　//s的size=6，而bitset的size=4，只取前面部分，即1001

 char s2[] = "11101";
 bitset<4> bitset3(s2);　　//与bitset2同理，只取前面部分，即1110

 cout << bitset1 << endl;　　//00
 cout << bitset2 << endl;　　//1001
 cout << bitset3 << endl;　　//1110
bitset<4> foo (string("1001"));
 bitset<4> bar (string("0011"));

 cout << (foo^=bar) << endl; // 1010 (foo对bar按位异或后赋值给foo)
 cout << (foo&=bar) << endl; // 0010 (按位与后赋值给foo)
 cout << (foo|=bar) << endl; // 0011 (按位或后赋值给foo)

 cout << (foo<<=2) << endl; // 1100 (左移２位，低位补０，有自身赋值)
 cout << (foo>>=1) << endl; // 0110 (右移１位，高位补０，有自身赋值)

 cout << (~bar) << endl;  // 1100 (按位取反)
 cout << (bar<<1) << endl;  // 0110 (左移，不赋值)
 cout << (bar>>1) << endl;  // 0001 (右移，不赋值)

 cout << (foo==bar) << endl; // false (0110==0011为false)
 cout << (foo!=bar) << endl; // true (0110!=0011为true)

 cout << (foo&bar) << endl; // 0010 (按位与，不赋值)
 cout << (foo|bar) << endl; // 0111 (按位或，不赋值)
 cout << (foo^bar) << endl; // 0101 (按位异或，不赋值)

#include<bits/stdc++.h>
using namespace std;
bitset<1000005>dp[105];
int main(){
    int n;
    cin>>n;
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        int l,r;
        cin>>l>>r;
        for(int j=l;j<=r;j++){
            dp[i]|=dp[i-1]<<j*j;
        }
    }
    cout<<dp[n].count()<<endl;
    return 0;
}