简单？瞎搞？搞我？

题目

题目描述：
一共有 n个数，第 i 个数是 xi 
xi 可以取 [li , ri] 中任意的一个值。
设S=∑xi2，求 S 种类数。

输入描述：
第一行一个数 n。 
然后 n 行，每行两个数表示 li，ri。

输出描述：
输出一行一个数表示答案。

解析

虽说简单，但这道题其实也不简单，这道题主要用到了bitset容器（详情见专栏）和递推。

题目啥意思呢？
  • 题目告诉了我们S=∑xi2：简单来说就是，我们每次输入一组边界，从其中选一个数取平方和。求这个和有多少种。

递推咋推呢？
  1. 在我们上面赏析了我们的题目之后呢，我们就知道了，我们要的每个平方和只能保留一次：简单来说就是只有存在和不存在两种关系。
  2. 既然只有两种关系，我们这里就可以用bitset容器来保存每一个数字。用来记录每一位数字时存在还是不存在。（简单来说就是，我们bitset容器的第pos位是0/1就表示，pos这个数字所表示的平方和是否存在。）
  3. 然后我们就是怎么将选到某个区间的所有sum值保存下来了。我们这里就可以用到或运算，我们循环遍历每一种情况，将所有的sum值或起来（这样的话，只要存在，无论出现了多少次，数组中的这一位都一定是1）。 
    for (int j = l; j <= r; j++) tmp |= x << j * j;
    从这里我们可以看出我们用了两个数组（x和tmp）x用来保存上一次所有S值，tmp保存这一次的所有tmp值。

打代码咯：
  1. 首先我们要输入我们该输入的东西。
  2. 然后我们要先得到我们第一组的数值（因为第一组要初始化，不能直接参与后面的递推）。
  3. 然后就开始递推，外层循环用作遍历n个区间（对n个区间进行累加求值，求到每一个sum）。
  4. 内层循环用作遍历区间范围内的所有xi值，用来得到累加到当前的所有S值是否存在。
  5. 强调：这里要额外开一个bitset容器数组用来保存累加到某一区间时的情况（因为这里的情况都是并行的，都要用到上一组区间计算的结果，所以不能让x数组在计算中被覆盖了）。
  6. 详情看代码吧~

bitset容器

这个容器说难也不难，主要是有一些方便的操作。
  • bitset容器本质上是一个数组：而且是一个每一位只能是0或1。（可以认为是一个布尔类型数组，或二进制数组）

那这个容器有什么优点呢？
  1. 这个容器的占用空间小，每一个元素只占用1b的空间。
  2. 这个容器重载了一些运算符，比如&和 | 都是按位操作然后放到每一位上，<<和>>就是数组左移位和右移位（自动补0）。
  3. 然后还有一些内置函数：比如reset可以用来数组清0，其他的就不赘述（我也不是很清楚，可以百度）。

本题运用：
  1. 这道题我们因为是要判断每一个数字的情况，就用数组的每一位代表了一个数字。
  2. 同时因为每一个数字只有两种情况我们才用上的（这点重要哦）。

AC代码 

#include <iostream>
#include <bitset>
using namespace std;
#define IOS ios::sync_with_stdio(false);
//代码预处理区

const int MAX = 1e2 + 7;
bitset<MAX * MAX * MAX> x, tmp;//x保存每个数字是否存在
//全局变量区

int main() {
    IOS;
    int n; cin >> n;
    int l, r; cin >> l >> r;
    for (int i = l; i <= r; i++) x[i * i] = 1;
    for (int i = 2; i <= n; i++) {
        cin >> l >> r;
        tmp.reset();
        for (int j = l; j <= r; j++) tmp |= x << j * j;
        //求或值表示，只要x中
        x = tmp;
    }
    cout << x.count() << endl;
    return 0;
}
//函数区