P4396 [AHOI2013]作业

本质和这道题P4867是一样的，先看一看这篇博客的代码，魔改一下就可以 $A$ 了。

魔改也非常简单，只要再开一个分块，有数加进来就加进分块的数组里面，不用判重。

然后，更加简单的是，这题竟然不用离散化也能 $A$ ，数据过水。

#include <bits/stdc++.h>
#define MAXN 1000005
#define MAXM 1000005
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
int a[MAXN],Size;
static int pos[MAXN],cnt[MAXN],val1[MAXN];//块内所有数之和
static int val2[MAXN];//只要出现过就加上
namespace Divide_Into_Blocks{
    inline int Calc1(int l,int r){
        int ans=0;
        for (register int i=l;i<=r;++i) ans+=cnt[i]>0;
        return ans;
    }
    inline int GetAns1(int a,int b){
        int L=pos[a],R=pos[b];
        if (L==R) return Calc1(a,b);
        int ans=0;
        for (register int i=L+1;i<=R-1;++i) ans+=val1[i];
        return ans+Calc1(a,L*Size)+Calc1((R-1)*Size+1,b);
    }
    inline int Calc2(int l,int r){
        int ans=0;
        for (register int i=l;i<=r;++i) ans+=cnt[i];//只要来一个就加上
        return ans;
    }
    inline int GetAns2(int a,int b){
        int L=pos[a],R=pos[b];
        if (L==R) return Calc2(a,b);
        int ans=0;
        for (register int i=L+1;i<=R-1;++i) ans+=val2[i];
        return ans+Calc2(a,L*Size)+Calc2((R-1)*Size+1,b);
    }
}
using namespace Divide_Into_Blocks;
struct Query{
    int l,r,a,b,id;
}q[MAXM];
inline bool operator < (const Query &a,const Query &b){
    return pos[a.l]<pos[b.l]||(pos[a.l]==pos[b.l]&&((pos[a.l]&1)?a.r<b.r:a.r>b.r));
}
int ans;
inline void Add(int x){
    ++val2[pos[x]];//不进行判重
    if (++cnt[x]==1) ++val1[pos[x]];
}
inline void Del(int x){
    --val2[pos[x]];
    if (--cnt[x]==0) --val1[pos[x]];
}
int Ans1[MAXM],Ans2[MAXN];
int main(){
    int n=read(),m=read();
    Size=sqrt(n);
    for (register int i=1;i<=n;++i){
        a[i]=read();
        pos[i]=(i-1)/Size+1;
    }
    for (register int i=1;i<=m;++i){
        q[i].l=read(),q[i].r=read(),q[i].a=read(),q[i].b=read(),q[i].id=i;
    }
    sort(q+1,q+1+m);
    int l=1,r=0;
    for (register int i=1;i<=m;++i){
        while (l<q[i].l) Del(a[l++]);
        while (l>q[i].l) Add(a[--l]);
        while (r<q[i].r) Add(a[++r]);
        while (r>q[i].r) Del(a[r--]);
        Ans1[q[i].id]=GetAns1(q[i].a,q[i].b);
        Ans2[q[i].id]=GetAns2(q[i].a,q[i].b);
    }
    for (register int i=1;i<=m;++i){
        printf("%d %d\n",Ans2[i],Ans1[i]);
    }
}