新的，但是TLE
```cpp
#include<bits/stdc++.h>
using namespace std;
inline int read(){
char ch=getchar();int x=0;bool f=1;
while(ch<'0'||'9'<ch){if(ch=='-')f=0;ch=getchar();}
while('0'<=ch&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return f?x:-x;
}
const int N=1e5+5,M=1002;
int n,m,a[N],pos[N],book[N],ans[M];
struct qwq{
int l,r,id;
}q[M*3];
vector<int>v;
bitset<100001>bs[M*3],vis;
inline int getid(int x){
return upper_bound(v.begin(),v.end(),x)-v.begin();
}
void sub(int x){
book[a[x]]--;
vis.reset(a[x]-book[a[x]]);
return;
}
void add(int x){
vis.set(a[x]-book[a[x]]);
book[a[x]]++;
return;
}
void solve(int T){
vis.reset();memset(book,0,sizeof(book));
for(int i=0;i<T;i++){
q[i*3+1]={read(),read(),i*3+1};
q[i*3+2]={read(),read(),i*3+2};
q[i*3+3]={read(),read(),i*3+3};
}
sort(q+1,q+T*3+1,[](qwq x,qwq y){return pos[x.l]==pos[y.l]?x.r<y.r:pos[x.l]<pos[y.l];});
for(int i=1,l=1,r=0;i<=T*3;i++){
while(l>q[i].l)add(--l);
while(r<q[i].r)add(++r);
while(l<q[i].l)sub(l++);
while(r>q[i].r)sub(r--);
bs[q[i].id]=vis;
ans[(q[i].id-1)/3]+=q[i].r-q[i].l+1;
}
for(int i=0;i<T;i++){
int siz=(bs[i*3+1]&bs[i*3+2]&bs[i*3+3]).count();
printf("%d\n",ans[i]-siz*3);
ans[i]=0;
}
return;
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n=read();m=read();
int ql=1000,bl=sqrt(n);
for(int i=1;i<=n;i++)a[i]=read(),pos[i]=(i-1)/bl+1,v.push_back(a[i]);
sort(v.begin(),v.end());
for(int i=1;i<=n;i++)a[i]=getid(a[i]);
while(m>ql)solve(ql),m-=ql;
solve(m);
return 0;
}
```
by sunzz3183 @ 2023-04-22 17:06:21
好了，$M$ 开小了。。
by sunzz3183 @ 2023-04-22 17:11:38