题解 P4396 【[AHOI2013]作业】

· · 题解

莫队（块状暴力）。
首先这道题的数据略水，没有规定 a_i 的范围（实际上不超过 2\times 10^5？），不过如果在 10^9 范围内只要离散化一下就可以了。
然后这个长得就很像莫队（块状暴力），可以直接莫队（块状暴力）套上去，然后考虑怎么加点减点，显然可以用先用套路维护 \text{cnt}_ i 代表 i 的出现次数，然后再考虑怎么维护题目要求那两个东西，那么我们可以用 区间加 和 区间查询 来记录区间出现数的次数和数的个数，这东西可以用树状数组维护，然后这题就可以轻松地过掉了。
（感觉可以奇偶性优化或者回滚莫队？有没有神仙加强一下数据啊）

#include<bits/stdc++.h>
#define MAXN 200005
#define reg register
#define inl inline
using namespace std;
struct Qry
{
    int l,r,pos,x,y,id;
    friend bool operator < (const Qry &x,const Qry &y)
    {
        return x.pos==y.pos?x.r<y.r:x.l<y.l;
    }
}q[MAXN];
int n,m,a[MAXN],cnt[MAXN],ans1[MAXN],ans2[MAXN];
struct BIT
{
    int c[MAXN];
    inl int lowbit(reg int x)
    {
        return x&-x;
    }
    inl void Modify(reg int x,reg int val)
    {
        for(;x<=n;x+=lowbit(x)) c[x]+=val;
    }
    inl int Query(reg int x)
    {
        reg int res=0;
        for(;x;x-=lowbit(x)) res+=c[x];
        return res;
    }
}A,B;
inl void Add(reg int x)
{
    if(!cnt[x]) B.Modify(x,1);
    A.Modify(x,1);
    cnt[x]++;
}
inl void Del(reg int x)
{
    A.Modify(x,-1);
    cnt[x]--;
    if(!cnt[x]) B.Modify(x,-1);
}
int main()
{
    scanf("%d %d",&n,&m);
    for(reg int i=1;i<=n;i++) scanf("%d",&a[i]);
    reg int unt=sqrt(n);
    for(reg int i=1;i<=m;i++)
    {
        scanf("%d %d %d %d",&q[i].l,&q[i].r,&q[i].x,&q[i].y);
        q[i].id=i;
        q[i].pos=(q[i].l-1)/unt+1;
    }
    sort(q+1,q+m+1);
    reg int L=1,R=0;
    for(reg int i=1;i<=m;i++)
    {
        while(L>q[i].l) Add(a[--L]);
        while(R<q[i].r) Add(a[++R]);
        while(L<q[i].l) Del(a[L++]);
        while(R>q[i].r) Del(a[R--]);
        ans1[q[i].id]=A.Query(q[i].y)-A.Query(q[i].x-1);
        ans2[q[i].id]=B.Query(q[i].y)-B.Query(q[i].x-1);
    }
    for(reg int i=1;i<=m;i++) printf("%d %d\n",ans1[i],ans2[i]);
    return 0;
}