题解

题目大意：

一共 $t$ 次询问，每次询问给定区间 $[l,r]$，要求输出恰好出现两次的自然数个数。

思路

首先这题肯定要离散，但是数据水不离散也能过。

莫队板题，注意是恰好出现两次，所以在移动的时候答案的更改要注意下。然后注意，这里要进行常数优化，不然你就会像我一样 T 飞。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+10;
int a[N],ans[N],v[N],n,m,b,c,k;
struct node{
    int l,r,id,block;
}md[N];
bool cmp(node x,node y){
    if(x.block!=y.block)return x.block<y.block;
    if(x.block%2==1)return x.r<y.r;
    else return x.r>y.r;
}
void add(int x){
    if(v[x]==1)c++;
    if(v[x]==2)c--;
    v[x]++;
}
void del(int x){
    if(v[x]==3)c++;
    if(v[x]==2)c--;
    v[x]--;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    memset(v,0,sizeof v); 
    int x=1,y=0;
    cin >> n >> m;
    b=m/sqrt(n)+1;
    for(int i=1;i<=n;i++)cin >> a[i];
    for(int i=1;i<=m;i++){
        cin >> md[i].l >> md[i].r;
        md[i].id=i;
        md[i].block=(md[i].l-1)/b+1;
    }
    sort(md+1,md+m+1,cmp);
    for(int i=1;i<=m;i++){
        int l=md[i].l,r=md[i].r;
        while(x>l)add(a[--x]);
        while(y<r)add(a[++y]);
        while(x<l)del(a[x++]);
        while(y>r)del(a[y--]);
        ans[md[i].id]=c;
    }for(int i=1;i<=m;i++)cout << ans[i] << "\n";
    return 0;
}