题解：P11659 小夫
dyc2022
·
·
题解
只能说是非常套路的题目吧。赛时最后半小时入场，可能不到 15 分钟切掉。
这个是很经典的，考虑进行莫队，开个桶数区间中每一个数字出现多少次，每在开头插入一个 $a_k$，若 $a_k$ 为偶数，则将答案加上其产生的贡献即 $\frac{a_k}{2}$ 出现次数；从末尾插入一个 $a_k$，同理将贡献加上 $2 \times a_k$ 的出现次数。删除同理。
可以用同样的方法求出 $2:3$ 的数对有多少个。
那么做到这里我们就会了。我们可以维护对于每个数字开头、结尾的 $2:1$ 与 $2:3$ 数对数量，然后每从开头插入一个数字 $a_k$，产生的贡献就是以 $\frac{a_k}{2}$ 为开头的 $2:3$ 数对数量；每从结尾插入一个 $a_k$，产生的贡献就是以 $\frac{2a_k}{3}$ 为结尾的 $2:1$ 数对数量。
那么我们就使用普通莫队完成了这一道题，复杂度 $O(m \sqrt n)$。
代码如下：
```cpp
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define N 800006
using namespace std;
int n,m,a[N],B,bel[N],outp[N];
int cnt[N],c42h[N],c42t[N],c23h[N],c23t[N],c423h[N],c423t[N],ans;
struct Node{int l,r,id;}q[N];
void addh(int k)
{
if(a[k]%4==0)c423h[a[k]]+=c23h[a[k]/2],c423t[a[k]/4*3]+=c23h[a[k]/2],ans+=c23h[a[k]/2];
if(a[k]%2==0)c42h[a[k]]+=cnt[a[k]/2],c42t[a[k]/2]+=cnt[a[k]/2];
if(a[k]%2==0)c23h[a[k]]+=cnt[a[k]/2*3],c23t[a[k]/2*3]+=cnt[a[k]/2*3];
cnt[a[k]]++;
}
void addt(int k)
{
if(a[k]%3==0)c423t[a[k]]+=c42t[a[k]/3*2],c423h[a[k]/3*4]+=c42t[a[k]/3*2],ans+=c42t[a[k]/3*2];
if(a[k]%1==0)c42t[a[k]]+=cnt[a[k]*2],c42h[a[k]*2]+=cnt[a[k]*2];
if(a[k]%3==0)c23t[a[k]]+=cnt[a[k]/3*2],c23h[a[k]/3*2]+=cnt[a[k]/3*2];
cnt[a[k]]++;
}
void delh(int k)
{
cnt[a[k]]--;
if(a[k]%2==0)c42h[a[k]]-=cnt[a[k]/2],c42t[a[k]/2]-=cnt[a[k]/2];
if(a[k]%2==0)c23h[a[k]]-=cnt[a[k]/2*3],c23t[a[k]/2*3]-=cnt[a[k]/2*3];
if(a[k]%4==0)c423h[a[k]]-=c23h[a[k]/2],c423t[a[k]/4*3]-=c23h[a[k]/2],ans-=c23h[a[k]/2];
}
void delt(int k)
{
cnt[a[k]]--;
if(a[k]%1==0)c42t[a[k]]-=cnt[a[k]*2],c42h[a[k]*2]-=cnt[a[k]*2];
if(a[k]%3==0)c23t[a[k]]-=cnt[a[k]/3*2],c23h[a[k]/3*2]-=cnt[a[k]/3*2];
if(a[k]%3==0)c423t[a[k]]-=c42t[a[k]/3*2],c423h[a[k]/3*4]-=c42t[a[k]/3*2],ans-=c42t[a[k]/3*2];
}
main()
{
scanf("%lld%lld",&n,&m),B=pow(n,0.5);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]),bel[i]=i/B+1;
for(int i=1;i<=m;i++)scanf("%lld%lld",&q[i].l,&q[i].r),q[i].id=i;
sort(q+1,q+1+m,[](Node x,Node y){
return (bel[x.l]^bel[y.l])?x.l<y.l:((bel[x.l]&1)?x.r<y.r:x.r>y.r);
});
for(int i=1,l=1,r=0;i<=m;i++)
{
int L=q[i].l,R=q[i].r,id=q[i].id;
while(r<R)addt(++r);
while(r>R)delt(r--);
while(l<L)delh(l++);
while(l>L)addh(--l);
outp[id]=ans;
}
for(int i=1;i<=m;i++)printf("%lld\n",outp[i]);
return 0;
}
```