"Solution" friend of Vulcan

（ Fire god ： What kind of injustice did you pay ……）

Link to the original title ：link

「 My question making process 」：

step1： Observation surface .

  「 His good friend Fengshen gave him one with N An array of natural Numbers , Then he was Q Queries . Each query contains two positive integers $L,R$, Represents an interval in an array $[L,R]$, Vulcan needs to answer how many values just appear in this interval $2$ Time 」, For this single point modified interval query （ But here is the query of the total number of interval element types ）, Naturally, I think of tree arrays , Of course, it may also be mo team .（ For what we have learned so far , Question type ： Tree array ）

step2： Think about the solution .

   First think of the simplest . If the array elements are all the same （ The default enumeration pointer is $i$）.
  （ It's like soy sauce ↓）

   With the left pointer of the area unchanged , The right pointer traverses from left to right , How should we maintain it .

   When the area is $[1,1]$ when , No value just appears $2$ Secondary elements . just , We don't need to operate anything .

   When the area is $[1,2]$ when ,$i$ Element number $3$ And $i-1$ The number element is the same ,$i-1$ Add one to the position of element number （ Express This bit is the same as the last number of this bit ）. In this interval ,$3$ Just happened to appear $2$ Time , So the area $[1,2]$ The value of $1$ , Maintenance succeeded .

   When the area is $[1,3]$ when ,$i$ Element number $3$ And $i-1$ The number element is the same ,$i-1$ Add one to the position of element number . In this interval ,$3$ appear $3$ Time , There is no value that happens to appear twice , So the area $[1,3]$ The value of should be $0$, But now it is $2$.

   therefore , We are in the current $i-2$ The position of the No. element is subtracted $2$（ It means that there are two adjacent elements after this element, which are the same as it .$3$ Consecutive elements are the same , Its value is zero ）. At this point, the region $[1,3]$ The value of $0$, Maintenance succeeded .

   When the area is $[1,4]$ when ,$i$ Element number $3$ And $i-1$ The number element is the same ,$i-1$ Add one to the position of element number . In this interval ,$3$ appear $4$ Time , There is no value that happens to appear twice , So the area $[1,4]$ The value of should be $0$, But now it is $-1$.

   therefore , We are in the current $i-3$ Add $1$（ It means that there are three consecutive elements after this element, which are the same as it , Add one to maintain balance .$4$ Consecutive elements are the same , Its value is still zero ）. At this point, the region $[1,4]$ The value of $0$, Maintenance succeeded .

   When the area is $[1,5]$ when ,$i$ Element number $3$ And $i-1$ The number element is the same ,$i-1$ Add one to the position of element number , stay $i-2$ The position of the No. element is subtracted $2$, stay $i-3$ Add $1$. You can find , At this time, our maintenance is successful . And so on , All the following operations are balanced .（ Blue plus one means ： This bit is the same as the next digit ; Green minus two means ： This element is followed by two adjacent elements that are the same as it , Subtract two more pairs ; Purple plus one means ： This element is followed by three consecutive elements that are the same as it , Make up for an extra pair ）
   After reading it, you may ask questions , Are you 「dou」 Come on ？？？ hey , Not really .

   When we are calculating, we are always $i-1$ Add one to the number , In order to Record how many pairs of elements meet the meaning of the question （ In the figure, how many left parentheses are equivalent to recording the current position , Its prefix sum is the current interval $[1,i]$ The number of elements satisfying the meaning of the question ）. But in the case of the above figure ,（ Three consecutive elements are equal , There are two pairs of the same elements ） We We need to abandon these two pairs , Hence, $i-2$ Subtract two from the number . You may ask again , Then why not $i-1$ The number increases or decreases ？ Well, if it's in $i-1$ If the number increases or decreases , Section $[i-1,i]$ What are you going to do .

   When this happens , Our operation is in $i-1$ Add one to the position of element number , stay $i-2$ The position of the No. element is subtracted $2$, stay $i-3$ Add $1$. The previous two operations have been explained , I won't repeat . Pictured （ Four identical elements are in the same box ）, We recorded the logarithm satisfying the meaning of the question according to the first two operations , Discard those that do not conform to the meaning of the topic , Now , We will find that —— We actually abandoned four pairs （$i-2$ Number minus two ,$i-3$ Number minus two ）, In fact, only three pairs need to be discarded . So , stay $i-3$ Add one to the number , Show me Gave up one more pair , Now make up （ If you want to ask why not add one to the other digit , I can only tell you that it's for the convenience of the later answer , The reason is the same as before ）.
   Just talking about the situation that all the elements are the same , But the actual data is not necessarily like this （ Suspected perjury ). Don't worry. , We put this concept into the data , reflection ： Can we transform the original data into what we want ？
  （ Funny ）
   It can . We can Put the same elements on the same chain , Separate calculation . The obvious , There is no problem with our non-interference calculation , Just compare the same kind with the same kind , Add up the answers （ In implementation , Accumulation is equivalent to directly in the same tree array ）.
   Special , We need to Answer while maintaining . If If the answer comes out after maintenance , Some of the top elements will record some information that is not available in this interval . for example $33333333$, If the interval is calculated after maintenance $[1,3]$ Words ,$2$ The number will record information ：「 This element is followed by two adjacent elements that are the same as it 」, But in fact, this situation does not exist in this interval .

step3： Completion code .

Code （ Resist academic misconduct , Refuse 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;
}

Hephaestus ： Anemie, you are finished ！！1（ Feng Shen left Accepted Off with it ）

---

Let's solve it 『 Friends of Vulcan 』 beep ~

Bye bye!!1