2020牛客暑期多校训练营（第八场）Enigmatic Partition
题目大意：
注意：对于每一个序列，一定要有三个不同的数，且这三个数连续，意思是一定存在 a1,a1+1,a1+2
题解：
先看上面这个图，这个是对于长度是7，最小数为1的序列对答案的贡献，很容易发现求贡献的规律。
对于区间 ([10,18]) 长度是7，最小数是1，贡献规律就是：每隔两个数方案数+1，到一个点之和，每隔一个数方案数-1。这个箭头向上表示2->3 箭头向右表示 1->2。
所以很容易推出之前的贡献规律是对的：
- 因为第一个向上的箭头肯定是因为有两个2可以向上走了，如果只有一个是肯定不行的，往上走一次就会消耗掉一个2，所以下次不能马上向上走，而是要等一格，凑齐两个2。
- 到一个点之后，一定会向上走，这个是因为1被消耗的只有1个了，无法往右走了，只能往上走，往上走之后也不能往右走了，因为没有1的生成，所以之候每一次的方案都要-1
找到这个之和，会发现这个就是一个差分数组，然后求和。
知道这里，其实这个题目差不多写完了，之后的二阶差分就是一种处理，也可以用线段树代替。
接下来说说为什么要用二阶差分或者线段树：
- 首先明确，一定要枚举这个组成的数的长度 (len) 和最小的数 (base) ，因为这个规律就是建立在这个基础之上的，再算算这个枚举的复杂度，枚举是 (O(n)) 的，最小的数看起来也是 (O(n)) 的，但是实际上没有这么大，因为每次枚举一个(base) ，是不是这个值就加了 (len) 这么大，因为是三个连续的数，所以最小的数+1，那么第二大第三大的数也要+1，所以整个 (len) 长的序列都+1，所以就是加了 (len) ，所以其实是每次跳 (len) 这么长，所以复杂度就是 (n/1+n/2+n/3+...) 提取n，后面是一个调和级数，复杂度是 (O(log)) 的，所以最后复杂度就是 (n*log)
- 对于每次枚举这个 (len) 和 (base) ，只要处理是一个常数，则这个复杂度肯定是过得去的。
- 每次枚举一个 (len) 和 (base) ，可以直接求出这个区间的 (l) 和 (r) 和中间点 (x)，如果我直接构造差分数组，那么是不是这个区间每隔两个数+1，(x) 之和每隔一个数-1，那么这个处理的复杂度就是 (O(r-l+1)) 应该比 (len) 还大，所以这样显然会 (TLE) ，所以考虑区间更新。
- 区间加，这个区间更新其实可以用线段树或者差分数组来维护，所以我们就考虑对于本来要求的这个数组进行一个差分，这样的话，求一次前缀和就可以还原这个数组。（这个就是二阶差分，其实很好理解的，如果还是不太会可以看看代码，再自己理解理解）
- 最后要明确对于不同的 (len) 和 (base) 都可以直接加到这个差分数组，因为对于一个数可能是由很多不同的 $len $ 或者 (base) 构成，这个都不影响方案数，因为方案数是直接累加的。
#include <bits/stdc++.h>
#define debug(x) cout<<"debug:"<<#x<<" = "<<x<<endl;
using namespace std;
typedef long long ll;
const int maxn = 5e5+10;
ll add[maxn],del[maxn],sum[maxn];
int main() {
int n = 1e5;
for (ll len = 3; len <= n; len++) {
for (int base = 1; base * len <= n; base++) {
int left = base * len + 3;
add[left]++;
add[(base + 2) * len - 3 + 2]--;
del[(base + 1) * len + 1]++;
del[(base + 2) * len - 3 + 2]--;
}
}
for (int i = 3; i <= n; i++) {
add[i] += add[i - 2];//+差分数组
del[i] += del[i - 1];//-差分数组
}
for (int i = 3; i <= n; i++) {
add[i] -= del[i];//差分数组
}
for (int i = 3; i <= n; i++) {
add[i] += add[i - 1];//方案数
sum[i] = sum[i - 1] + add[i];
}
int T;
scanf("%d", &T);
for (int cas = 1; cas <= T; cas++) {
int l, r;
scanf("%d%d", &l, &r);
printf("Case #%d: %lld
", cas, sum[r] - sum[l - 1]);
}
}