莫队
by S00021 @ 2023-03-11 21:42:37
把莫队拍上去
by devans @ 2023-03-11 21:42:40
预处理组合数+莫队板子
by 2949767807qwer @ 2023-03-11 21:43:12
莫队
by Esawkm @ 2023-03-11 21:43:21
@[2949767807qwer](/user/577066) 所以可以帮我看看哪里有问题吗
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,bl,nl=1,nr,cnt[100001],a[100001],ans[100001];
struct ask{
int l,r,id;
}q[100001];
set<int> se;
bool cmp(ask a,ask b){
if(a.l/bl==b.l/bl) return a.r<b.r;
else return a.l<b.l;
}
void add(int pos){
if((++cnt[a[pos]])==1){
se.insert(a[pos]);
}
}
void del(int pos){
if(!(--cnt[a[pos]])){
se.erase(a[pos]);
}
}
int C(int x){
return x*(x-1)*(x-2)/6;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>m;
bl=sqrt(n);
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=m;i++){
cin>>q[i].l>>q[i].r;
q[i].id=i;
}
sort(q+1,q+1+m,cmp);
for(int i=1;i<=m;i++){
int L=q[i].l,R=q[i].r;
while(nl<L){
del(nl);
nl++;
}
while(nl>L){
nl--;
add(nl);
}
while(nr<R){
nr++;
add(nr);
}
while(nr>R){
del(nr);
nr--;
}
int sum=0;
for(set<int>::iterator it=se.begin();it!=se.end();it++){
int k=*it;
//cout<<k<<","<<cnt[k]<<","<<C(cnt[k])<<" ";
if(cnt[k]>=3) sum+=C(cnt[k]);
}
ans[q[i].id]=sum;
//cout<<q[i].id<<"="<<sum<<endl;
}
for(int i=1;i<=m;i++){
cout<<ans[i]<<endl;
}
return 0;
}
```
by luqyou @ 2023-03-11 21:44:38
莫队。
by _Ad_Astra_ @ 2023-03-11 21:45:07
不会超时吗？
by DaiRuiChen007 @ 2023-03-11 21:45:13
~~你对着P1494打一遍准没错~~
by Hell0_W0rld @ 2023-03-11 21:45:17
@[luqyou](/user/464732) 数据范围2e5你数组1e5。。。
by Hell0_W0rld @ 2023-03-11 21:45:52
@[luqyou](/user/464732) 你这莫队复杂度是假的吧
考虑
$$
\dfrac{(k+1)k(k-1)}{6}=\dfrac{k(k-1)(k-2)}{6}+\dfrac{k(k-1)}{2}
$$
by bykem @ 2023-03-11 21:46:03