题解 P4396 【[AHOI2013]作业】

· · 题解

我的博客

暴力77分就不用讲了

正解：

做法不唯一，常见做法为莫队+分块或者莫队+树状数组，但是网上也有一些奇奇怪怪的方法。

求任意一段区间内在[a,b]的数字个数，很容易想到分块；但是题目有要求该区间内在[a,b]的数值种数，这又很容易联想到莫队。所以正解就是莫队+分块。例如样例的第一个询问，莫队增加在这个区间内每个数字出现的次数、该数字所在的块的元素个数（包括重复的数字）、该数所在块的不重复元素个数。然后分块询问[a,b]之间在规定区间的答案。

正解很巧妙地一点在于分块分的不仅仅是有多少个数（即n），还是数值（即color[ ]）。这也就存在一个问题，假设n很小，但是color[ ]很大又要另做处理。

如果不能理解代码的建议自行模拟样例。

更新：针对hack数据改了一波，之前的问题是如果l或r超出了color[]的最大值，posi[l]或者posi[r]会 变成0，那么对答案的统计就会出现问题

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,m,L,R,block,num,posi[N],lll[N],rrr[N],sum[N],skuai[N],change[N],color[N],ans1[N],ans2[N],anss1,anss2;
struct node{
    int l,r,x,y,id;
}a[N];
bool cmp(node aa,node bb)
{
    if(posi[aa.l]==posi[bb.l]) return aa.r<bb.r;
    else return aa.l<bb.l;
}
void build()//预处理出每个块的边界
{
    block=sqrt(n);num=n/block;
    if(n%block) num++;
    for(int i=1;i<=num;i++) 
    lll[i]=(i-1)*block+1,rrr[i]=i*block;
    rrr[num]=n;
    for(int i=1;i<=n;i++) posi[i]=(i-1)/block+1;
}
void add(int col)
{
    sum[col]++;skuai[posi[col]]++;
    if(sum[col]==1) change[posi[col]]++;
}
void del(int col)
{
    sum[col]--;skuai[posi[col]]--;
    if(!sum[col]) change[posi[col]]--;
}
void find(int l,int r,int id)
{
    if(posi[l]==posi[r]) 
    {
        for(int i=l;i<=r;i++) if(sum[i]) ans1[id]+=sum[i],ans2[id]++;
        return;
    }
    /*改动*/
    if(posi[l]!=0) 
    for(int i=l;i<=rrr[posi[l]];i++) if(sum[i]) ans1[id]+=sum[i],ans2[id]++;
    if(posi[r]!=0)
    for(int i=lll[posi[r]];i<=r;i++) if(sum[i]) ans1[id]+=sum[i],ans2[id]++;
    if(posi[l]!=0&&posi[r]!=0)
    for(int i=posi[l]+1;i<posi[r];i++) ans1[id]+=skuai[i],ans2[id]+=change[i];
    if(posi[l]!=0&&posi[r]==0) 
    for(int i=posi[l]+1;i<=num;i++) ans1[id]+=skuai[i],ans2[id]+=change[i];
}
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&color[i]);
    build();
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d%d",&a[i].l,&a[i].r,&a[i].x,&a[i].y);
        a[i].id=i;
    }
    L=1,R=0;
    sort(a+1,a+1+m,cmp);
    for(int i=1;i<=m;i++)
    {
        while(R<a[i].r) add(color[++R]);
        while(R>a[i].r) del(color[R--]);
        while(L<a[i].l) del(color[L++]);
        while(L>a[i].l) add(color[--L]);
        find(a[i].x,a[i].y,a[i].id);
    }
    for(int i=1;i<=m;i++)
        printf("%d %d\n",ans1[i],ans2[i]);
    return 0;
}