思路：离线做法：

  • 首先离散化数字arr，并按右端点处理询问，原理和处理区间种类数一样
  • 然后把1~n的相同的数字预处理一下，让每个相同的数字可以索引到它后面那个位置，也称为这个节点的后继，实际上就是按类构造静态链表
  • 之后预处理每个链表首部有后继的节点在表头位置+1
  • 然后根据树状数组处理1~n的区间，每当一个节点有后继时它的位置-1，后继+1，使得该区间的总数不变，并且靠后的区间也能够共享到这个成果，这个查询的意义在于它能够统计区间大于等于2的数字种类数
  • 同理可得区间大于等于3的数字种类数，根据A1-A2得到数量恰好为2的数字种类数

Code:

#include <bits/stdc++.h>
using namespace std;

const int N  = (int)5e5+5;
int arr[N], xia[N], ans[N],n,tr[N], tmp[N];
map<int,int>Hash;
struct Node
{
        int l,r,id;
        Node(){}
        Node(int a,int b,int c):l(a),r(b),id(c){ }
        bool operator < (const Node& A) const
        {
                return l < A.l;
        }
}Que[N];
inline int lowbit(int x) {
        return x&(-x);
}
void add(int i,int val)
{
        for(;i<=n;i+=lowbit(i))
                tr[i]+=val;
}
int query(int i)
{
        int res = 0;
        for(;i>=1;i-=lowbit(i))
                res+=tr[i];
                return res;
}
int main()
{
        Hash.clear();
        int c,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)  {scanf("%d",&arr[i]);tmp[i]=arr[i];}
        sort(tmp + 1, tmp + 1 + n);
		c = unique(tmp + 1, tmp + 1 + n) - tmp - 1;
		for (int i = 1; i <= n; i++) {
			arr[i] = lower_bound(tmp + 1, tmp + 1 + c, arr[i]) - tmp; //rnk [1,...]
		}
        for(int i=n;i>=1;i--)  xia[i] = Hash[arr[i]],Hash[arr[i]] = i;
        for(int i=1;i<=c;i++)  if(xia[Hash[i]]) add(xia[Hash[i]],1);
        for(int i=1;i<=m;i++)
        {
                int l,r;
                scanf("%d%d",&l,&r);
                Que[i] = Node(l,r,i);
        }
        sort(Que+1,Que+1+m);

        int l = 1;
        for(int i=1;i<=m;i++)
        {
               while( l < Que[i].l)
               {
                        if(xia[l]) add(xia[l],-1);
                        if(xia[xia[l]]) add(xia[xia[l]],1);
                        l++;
               }
               ans[Que[i].id] = query(Que[i].r) - query(Que[i].l-1);
        }
        
        memset(tr, 0, sizeof(tr));
        memset(tmp, 0, sizeof(tmp));
        for(int i=1;i<=c;i++)  if(xia[xia[Hash[i]]]) add(xia[xia[Hash[i]]],1);
        l = 1;
        for(int i=1;i<=m;i++)
        {
               while( l < Que[i].l)
               {
                    if(xia[xia[l]]) add(xia[xia[l]], -1);
                    if(xia[xia[xia[l]]]) add(xia[xia[xia[l]]], 1);
                    l++;
               }
               tmp[Que[i].id] = query(Que[i].r) - query(Que[i].l-1);
        }
        
        for(int i=1;i<=m;i++) printf("%d\n",ans[i]-tmp[i]);
        return 0;
}