「题解」火神之友

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

原题目链接：link

  「他的好朋友风神给他一个有 N 个自然数的数组，然后对他进行 Q 次查询。每一次查询包含两个正整数 L , R L,R L,R，表示一个数组中的一个区间 [ L , R ] [L,R] [L,R]，火神需要回答在这个区间中有多少个值刚好出现 2 2 2 次」，对于这种单点修改区间查询（但此处是对区间元素种类总数的查询），自然是想到树状数组，当然也有可能是莫队。（对于目前所学而言，题型：树状数组）

  先从最简单的想起。假如数组元素全部相同的话（默认枚举指针为 i i i）。
  （就像酱紫↓）

  随着区域左指针不变，右指针从左往右遍历，我们应该如何去维护呢。

  当区域为 [ 1 , 1 ] [1,1] [1,1] 时，没有值刚好出现 2 2 2 次的元素。恰好，我们什么都不需要操作。

  当区域为 [ 1 , 2 ] [1,2] [1,2] 时， i i i 号元素 3 3 3 与 i − 1 i - 1 i−1 号元素相同， i − 1 i - 1 i−1 号元素的位置上加一（表示该位与该位的后一个数相同）。在这一个区间里， 3 3 3 刚好出现 2 2 2 次，所以区域 [ 1 , 2 ] [1,2] [1,2] 的价值为 1 1 1 ，维护成功。

  当区域为 [ 1 , 3 ] [1,3] [1,3] 时， i i i 号元素 3 3 3 与 i − 1 i - 1 i−1 号元素相同， i − 1 i - 1 i−1 号元素的位置上加一。在这一个区间里， 3 3 3 出现 3 3 3 次，没有刚好出现两次的值，所以区域 [ 1 , 3 ] [1,3] [1,3] 的价值应该为 0 0 0，但此时却是 2 2 2。

  于是，我们在当前 i − 2 i - 2 i−2 号元素的位置上减 2 2 2（表示该元素后面还有两个相邻元素与它相同。 3 3 3 个连续元素相同，其价值为零）。此时区域 [ 1 , 3 ] [1,3] [1,3] 的价值为 0 0 0，维护成功。

  当区域为 [ 1 , 4 ] [1,4] [1,4] 时， i i i 号元素 3 3 3 与 i − 1 i - 1 i−1 号元素相同， i − 1 i - 1 i−1 号元素的位置上加一。在这一个区间里， 3 3 3 出现 4 4 4 次，没有刚好出现两次的值，所以区域 [ 1 , 4 ] [1,4] [1,4] 的价值应该为 0 0 0，但此时却是 − 1 -1 −1。

  于是，我们在当前 i − 3 i - 3 i−3 号元素的位置上加 1 1 1（表示该元素后面有三个连续元素与它相同，加一来维护平衡。 4 4 4 个连续元素相同，其价值仍为零）。此时区域 [ 1 , 4 ] [1,4] [1,4] 的价值为 0 0 0，维护成功。

  当区域为 [ 1 , 5 ] [1,5] [1,5] 时， i i i 号元素 3 3 3 与 i − 1 i - 1 i−1 号元素相同， i − 1 i - 1 i−1 号元素的位置上加一，在 i − 2 i - 2 i−2 号元素的位置上减 2 2 2，在 i − 3 i - 3 i−3 号元素的位置上加 1 1 1。可以发现，此时我们维护成功了。以此类推，后面所有操作都是平衡的。（蓝色的加一表示：该位与后一位数相同； 绿色的减二表示：该元素后面还有两个相邻元素与它相同，减去多算的两对；紫色的加一表示：该元素后面有三个连续元素与它相同，补上多去的一对）
  看完后你可能会发出疑问，你是不是「dou」得呀？？？欸，还真不是。

  我们在计算的时候总是在 i − 1 i - 1 i−1 号位上加一，是为了记录当前有多少对满足题意的元素（在图中等价于记录当前位置的左括号有多少，其前缀和即当前区间 [ 1 , i ] [1,i] [1,i] 满足题意的元素对数）。但是遇到上图这种情况，（连续三个元素相等，出现两对相同元素）我们需要舍弃这两对，于是乎在 i − 2 i - 2 i−2 号位上减二。你可能又会问，那为啥不在 i − 1 i - 1 i−1 号位上减呢？那如果在 i − 1 i - 1 i−1 号位上减的话，区间 [ i − 1 , i ] [i - 1, i] [i−1,i] 你又打算怎么算呢。

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

#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 <= 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("%dn", ans[i]);
	}
    return 0;
}

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

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

Bye bye!!1 