BZOJ-2506: calc

[文章目录]

Description

给一个长度为n的非负整数序列A1,A2,…,An。现有m个询问,每次询问给出l,r,p,k,问满足l<=i<=r且Ai mod p = k的值i的个数。0< n,m < =10^5,任意1<=i<=n满足Ai<=10^4,0< p<=10^4,0<=k< p。

关于模数根号分治,小于根号的直接维护前缀和,大于根号的莫队+桶,暴力扫桶统计答案即可。时间复杂度O(n√p+m√n+p√p)

#include <cmath>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#define pb push_back 
#define N 101000 
#define W 10100 
inline char nc()
{
    static char buf[100000],*p1,*p2;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    int re=0; char ch=nc();
    while(!isdigit(ch)) ch=nc();
    while(isdigit(ch)) re=re*10+(ch^'0'),ch=nc();
    return re;
}
int n,m,tot,a[N],t[W],fna[N];
struct ques
{
    int l,r,b,p,k,id;
}q[N];
bool cmp(ques x,ques y) {return x.b==y.b ? x.r<y.r : x.b<y.b;}
vector<ques>qv[110];
vector<int>ve[110];
int getans(int k,int l,int r)
{
    return lower_bound(ve[k].begin(),ve[k].end(),r+1)-
    lower_bound(ve[k].begin(),ve[k].end(),l);
}
int main()
{
    n=read(); m=read();
    int i,j,l,r,p,k,bl=sqrt(n)+1;
    for(i=1;i<=n;++i) a[i]=read();
    for(i=1;i<=m;++i)
    {
        l=read(); r=read(); p=read(); k=read();
        if(p>100)
        {
            q[++tot].id=i; q[tot].l=l; q[tot].b=l/bl;
            q[tot].r=r; q[tot].p=p; q[tot].k=k;
        }
        else qv[p].pb((ques){l,r,0,p,k,i});
    }
    for(i=1;i<=100;++i) if(qv[i].size())
    {
        for(j=1;j<=n;++j) ve[a[j]%i].pb(j);
        for(j=qv[i].size()-1;~j;--j)
            fna[qv[i][j].id]=getans(qv[i][j].k,qv[i][j].l,qv[i][j].r);
        for(j=0;j<i;++j) ve[j].clear();
    }
    sort(q+1,q+tot+1,cmp);
    for(l=1,r=0,i=1;i<=tot;++i)
    {
        while(r<q[i].r) t[a[++r]]++;
        while(l>q[i].l) t[a[--l]]++;
        while(r>q[i].r) t[a[r--]]--;
        while(l<q[i].l) t[a[l++]]--;
        for(j=q[i].k;j<=10000;j+=q[i].p) fna[q[i].id]+=t[j];
    }
    for(i=1;i<=m;++i) printf("%d\n",fna[i]);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注