莫队+分块的有机结合

3lizabeth · 2019-09-11 20:14:30 · 题解

莫队+分块

好像很多写莫队+分块的，但是代码可读性个人感觉有点差，就写了个码风奇特的版本给各位带哥康康。

第一次写题解，审核大大给个过8 ！ლ(°◕‵ƹ′◕ლ) 话说这题好水

对于本题，在察觉了出现数字个数时就很容易察觉到（杀意感知）可以用莫队处理（离线），但是对于区间内符合条件的x的总个数呢？想到可以用莫队和分块有机结合处理，就可以A掉本题了！

看代码，GKD

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
int n,m,q[N],a[N],l=1,r,blo;
int appnum[N],appq[N],tot[N];

struct node
{
    int l,r,a,b,id;
}ask[N];//存储输入 

struct node1
{
    int a1,a2;
}ans[N];//储存答案，有两个输出，一个是种类数，一个是个数

bool cmp(node x,node y)
{
    if(q[x.l]!=q[y.l])
    return q[x.l]<q[y.l];
    else return x.r<y.r;
}

void add(int x)
{
    appnum[x]++;
    appq[q[x]]++;
    if(appnum[x]==1) tot[q[x]]++;
}

void del(int x)
{
    appnum[x]--;
    appq[q[x]]--;
    if(appnum[x]==0) tot[q[x]]--;
}

void getans(int a,int b,int k)//分块找答案 
{
    for(int i=a;i<=min(b,q[a]*blo);i++)
        if(appnum[i]) ans[k].a1+=appnum[i],ans[k].a2++;

    if(q[a]!=q[b])
        for(int i=(q[b]-1)*blo+1;i<=b;i++)
            if(appnum[i]) ans[k].a1+=appnum[i],ans[k].a2++;

    for(int i=q[a]+1;i<=q[b]-1;i++)
    { 
        ans[k].a1+=appq[i];
        ans[k].a2+=tot[i];
    }
}

inline int read()
{
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}

int main()
{
    //freopen("homework.in","r",stdin);
    //freopen("homework.out","w",stdout);

    n=read();m=read();
    blo=sqrt(n);

    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        q[i]=(i-1)/blo+1;//分块
    }

    for(int i=1;i<=m;i++)
    {
        ask[i].l=read();ask[i].r=read();ask[i].a=read();ask[i].b=read();
        ask[i].id=i;//输入数据
    }

    sort(ask+1,ask+m+1,cmp);//对查询区间的排序节约时间，莫队基操

    for(int i=1;i<=m;i++)
    {   //莫队先统计 
        while(r<ask[i].r)   add(a[++r]);
        while(r>ask[i].r)   del(a[r--]);
        while(l>ask[i].l)   add(a[--l]);
        while(l<ask[i].l)   del(a[l++]);

        getans(ask[i].a,ask[i].b,ask[i].id);
    }

    for(int i=1;i<=m;i++)
        printf("%d %d\n",ans[i].a1,ans[i].a2);

    return 0;
}