自动搬运

查看原文

来自洛谷，原作者为

	dyc2022 「知らない世界を見せてよ」

搬运于2025-08-24 23:09:13，当前版本为作者最后更新于2025-02-03 21:22:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

只能说是非常套路的题目吧。赛时最后半小时入场，可能不到 $15$ 分钟切掉。

$4:2:3$ 不大好做，先考虑数区间中 $2:1$ 的数对有多少个。

这个是很经典的，考虑进行莫队，开个桶数区间中每一个数字出现多少次，每在开头插入一个 $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)$。

代码如下：

#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;
}