「题解」火神之友

（火神：爷究竟交了些什么冤种……）

原题目链接：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$ 号位上加一，表示我多舍弃了一对，现补上（如果你要问为什么不在其他位加一，我只能告诉你是为了后面方便求答案，道理同前）。
  前面光是讲全是相同元素的情况了，可实际的数据不一定是这样啊 （疑似伪证)。别急，我们将这种观念放进数据，思考：是否可以将原数据改造成我们想要的样子呢？
  （搞笑哦）
  确实可以。我们可以将相同的元素分别穿在同一条链上，分别计算。明显的，我们这样互不干扰的计算没有问题，只需同类与同类进行比较，将答案累加即可（在实现中，累加等价于直接在同一个树状数组中）。
  特别的，我们需要边维护边出答案。如果维护完了再出答案的话，部分靠前的元素会记录到一些该区间本没有的信息。譬如 $33333333$，若是维护完后再求区间 $[1,3]$ 的话，$2$ 号位会记录到信息：「该元素后面还有两个相邻元素与它相同」，但实际该区间内并不存在这种情况。

step3：完成代码。

代码（抵制学术不端行为，拒绝 Ctrl + C）：

#include <bits/stdc++.h>
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<ll, int> 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 <= n; i += lowbit(i)) {
    
		BIT[i] += k; 
	}
	return;
}
int sum(int x) {
    
	int ans = 0;
	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 <= n; i++) {
    
    	scanf("%lld", a + i);
    	if (mp.find(a[i]) != mp.end()) {
    
    		last[i] = mp[a[i]];
		} else {
    
			last[i] = -1;
		}
    	mp[a[i]] = i;
	}
	for (int i = 1; i <= q; i++) {
    
		scanf("%d %d", &b[i].l, &b[i].r);
		b[i].id = i;
	}
	sort(b + 1, b + q + 1, cmp);
	int now = 1;
	for (int i = 1; i <= q; i++) {
    
		while (now <= b[i].r) {
    
			if (last[now] != -1) {
    
				update(last[now], 1);
				if (last[last[now]] != -1) {
    
					update(last[last[now]], -2);
					if (last[last[last[now]]] != -1) {
    
						update(last[last[last[now]]], 1);
					}
				}
			}	
			now++;
		}
		ans[b[i].id] = sum(b[i].r) - sum(b[i].l - 1);
	}
	for (int i = 1; i <= q; i++) {
    
		printf("%d\n", ans[i]);
	}
    return 0;
}

赫菲斯托斯：阿涅弥伊你完犊子了！！1（ 风神留下了 Accepted 扬长而去）

---

让我们来解决 『火神之友』 叭~

Bye bye!!1