（火神：爷究竟交了些什么冤种……）
原题目链接：link
「我的做题历程」：
step1：观察题面。
「他的好朋友风神给他一个有 N 个自然数的数组，然后对他进行 Q 次查询。每一次查询包含两个正整数 (L,R)，表示一个数组中的一个区间 ([L,R])，火神需要回答在这个区间中有多少个值刚好出现 (2) 次」，对于这种单点修改区间查询（但此处是对区间元素种类总数的查询），自然是想到树状数组，当然也有可能是莫队。（对于目前所学而言，题型：树状数组）
step2：思考解法。
先从最简单的想起。假如数组元素全部相同的话（默认枚举指针为 (i)）。
（就像酱紫↓）
随着区域左指针不变，右指针从左往右遍历，我们应该如何去维护呢。
当区域为 ([1,1]) 时，没有值刚好出现 (2) 次的元素。恰好，我们什么都不需要操作。
当区域为 ([1,2]) 时，(i) 号元素 (3) 与 (i – 1) 号元素相同，(i – 1) 号元素的位置上加一（表示 该位与该位的后一个数相同）。在这一个区间里，(3) 刚好出现 (2) 次，所以区域 ([1,2]) 的价值为 (1) ，维护成功。
当区域为 ([1,3]) 时，(i) 号元素 (3) 与 (i – 1) 号元素相同，(i – 1) 号元素的位置上加一。在这一个区间里，(3) 出现 (3) 次， 没有刚好出现两次的值，所以区域 ([1,3]) 的价值应该为 (0)，但此时却是 (2)。
于是，我们在当前 (i – 2) 号元素的位置上减 (2)（表示该元素后面还有两个相邻元素与它相同。 (3) 个连续元素相同，其价值为零）。此时区域 ([1,3]) 的价值为 (0)，维护成功。
当区域为 ([1,4]) 时，(i) 号元素 (3) 与 (i – 1) 号元素相同，(i – 1) 号元素的位置上加一。在这一个区间里，(3) 出现 (4) 次， 没有刚好出现两次的值，所以区域 ([1,4]) 的价值应该为 (0)，但此时却是 (-1)。
于是，我们在当前 (i – 3) 号元素的位置上加 (1)（表示该元素后面有三个连续元素与它相同，加一来维护平衡。 (4) 个连续元素相同，其价值仍为零）。此时区域 ([1,4]) 的价值为 (0)，维护成功。
当区域为 ([1,5]) 时，(i) 号元素 (3) 与 (i – 1) 号元素相同，(i – 1) 号元素的位置上加一，在 (i – 2) 号元素的位置上减 (2)，在 (i – 3) 号元素的位置上加 (1)。可以发现，此时我们维护成功了。以此类推，后面所有操作都是平衡的。（蓝色的加一表示：该位与后一位数相同； 绿色的减二表示：该元素后面还有两个相邻元素与它相同，减去多算的两对；紫色的加一表示：该元素后面有三个连续元素与它相同，补上多去的一对）
看完后你可能会发出疑问，你是不是「dou」得呀？？？欸，还真不是。
我们在计算的时候总是在 (i – 1) 号位上加一，是为了 记录当前有多少对满足题意的元素（在图中等价于记录当前位置的左括号有多少，其前缀和即当前区间 ([1,i]) 满足题意的元素对数）。但是遇到上图这种情况，（连续三个元素相等，出现两对相同元素）我们 需要舍弃这两对，于是乎在 (i – 2) 号位上减二。你可能又会问，那为啥不在 (i – 1) 号位上减呢？那如果在 (i – 1) 号位上减的话，区间 ([i – 1, i]) 你又打算怎么算呢。
遇到这种情况时，我们的操作是在(i – 1) 号元素的位置上加一，在 (i – 2) 号元素的位置上减 (2)，在 (i – 3) 号元素的位置上加 (1)。前面两个操作已解释过，不再赘述。如图（四个相同元素同框），我们按前两个操作记录了满足题意的对数，舍弃不符合题意的，这时候，我们会发现—— 我们实际舍弃了四对（(i – 2) 号减二，(i – 3) 号减二）， 实际只需舍弃三对。于是乎，在 (i – 3) 号位上加一，表示我 多舍弃了一对，现补上（如果你要问为什么不在其他位加一，我只能告诉你是为了后面方便求答案，道理同前）。
前面光是讲全是相同元素的情况了，可实际的数据不一定是这样啊 （疑似伪证)。别急，我们将这种观念放进数据，思考：是否可以将原数据改造成我们想要的样子呢？
（搞笑哦）
确实可以。我们可以 将相同的元素分别穿在同一条链上，分别计算。明显的，我们这样互不干扰的计算没有问题，只需同类与同类进行比较，将答案累加即可（在实现中，累加等价于直接在同一个树状数组中）。
特别的，我们需要 边维护边出答案。如果 维护完了再出答案的话，部分靠前的元素会记录到一些该区间本没有的信息。譬如 (3\ 3\ 3\ 3\ 3\ 3\ 3\ 3)，若是维护完后再求区间 ([1,3]) 的话，(2) 号位会记录到信息：「该元素后面还有两个相邻元素与它相同」，但实际该区间内并不存在这种情况。
step3：完成代码。
代码（抵制学术不端行为，拒绝 Ctrl + C）：
#include
using namespace std;
typedef long long ll;
const int N = 5e5 + 5;
int n, q, l, r, BIT[N], last[N], ans[N];
ll a[N];
map mp;
struct node {
int l, r, id;
} b[N];
bool cmp(node x, node y) { return x.r < y.r; }
int lowbit(int x) { return x & -x; }
void update(int x, int k) {
for (int i = x; i = 1; i -= lowbit(i)) {
ans += BIT[i];
}
return ans;
}
int main() {
scanf("%d %d", &n, &q);
for (int i = 1; i
赫菲斯托斯：阿涅弥伊你完犊子了！！1（ 风神留下了 Accepted 扬长而去）
让我们来解决 『火神之友』 叭~
Bye bye!!1 👋👋
Original: https://www.cnblogs.com/kylin-king/p/16497696.html
Author: 北柒kylin
Title: 「题解」火神之友
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/588156/
转载文章受原作者版权保护。转载请注明原作者出处！