CodeForces - 220B 离散化+莫队算法

莫队算法链接：传送门

题意：

有n个数，m个区间。问区间内有多少个x，x满足x的个数等于x的值的个数（如果x是3，区间内要存在3个3）。

题解：

因为a[i]太大，所以要离散化一下，但是不能用map容器，因为map容器多一个log

莫队就是离线问题+区间的移动。复杂度是O（(N+M)*√N）

莫队代码还要分块要不然还会TLE，分块大小为sqrt(n)

未分块-TLE代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <set>
#include <map>
#include <string>
#include <queue>
#include <stack>
#include <string>
using namespace std;
typedef long long ll;
using namespace std;
const int maxn=1e5+7;
int unit,n,m;
struct Node
{
    int l,r,id,result;
}node[maxn];
bool mmp1(Node x,Node y)
{
    if(x.l==y.l)
        return x.r<y.r;
    return x.l<y.l;
}
bool mmp2(Node x,Node y)
{
    return x.id<y.id;
}
int a[maxn],b[maxn],num[maxn],pr[maxn],ans;
int add(int i)
{
    num[a[i]]++;
    if(num[a[i]]==b[a[i]]) ans++;
    else if(num[a[i]]==b[a[i]]+1) ans--;
}
void del(int i)
{
    num[a[i]]--;
    if(num[a[i]]==b[a[i]]) ans++;
    else if(num[a[i]]==b[a[i]]-1) ans--;
}
int main()
{
    scanf("%d%d",&n,&m);
    unit=(int)sqrt(n);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]),b[i]=a[i];
    sort(b+1,b+n+1);
    int cnt=unique(b+1,b+1+n)-(b+1);
    for(int i=1;i<=n;++i)
    {
        a[i]=lower_bound(b+1,b+1+cnt,a[i])-b;
    }
    for(int i=1;i<=m;++i)
        scanf("%d%d",&node[i].l,&node[i].r),node[i].id=i;
    sort(node+1,node+1+m,mmp1);
    int lpos=node[1].l,rpos=lpos-1;
    for(int i=1;i<=m;++i)
    {
        while(lpos>node[i].l) add(--lpos);
        while(rpos<node[i].r) add(++rpos);
        while(lpos<node[i].l) del(lpos++);
        while(rpos>node[i].r) del(rpos--);
        node[i].result=ans;
    }
    sort(node+1,node+1+m,mmp2);
    for(int i=1;i<=m;++i)
        printf("%d\n",node[i].result);
    return 0;
}

分块-正确代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <set>
#include <map>
#include <string>
#include <queue>
#include <stack>
#include <string>
using namespace std;
typedef long long ll;
using namespace std;
const int maxn=1e5+7;
int unit,n,m;
struct Node
{
    int l,r,id,result;
    bool operator < (const Node x)const
    {
        return l/unit==x.l/unit?r<x.r:l<x.l;
    }
}node[maxn];
//bool mmp1(Node x,Node y)
//{
//    if(x.l==y.l)
//        return x.r<y.r;
//    return x.l<y.l;
//}
bool mmp2(Node x,Node y)
{
    return x.id<y.id;
}
int a[maxn],b[maxn],num[maxn],pr[maxn],ans;
int add(int i)
{
    num[a[i]]++;
    if(num[a[i]]==b[a[i]]) ans++;
    else if(num[a[i]]==b[a[i]]+1) ans--;
}
void del(int i)
{
    num[a[i]]--;
    if(num[a[i]]==b[a[i]]) ans++;
    else if(num[a[i]]==b[a[i]]-1) ans--;
}
int main()
{
    scanf("%d%d",&n,&m);
    unit=(int)sqrt(n);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]),b[i]=a[i];
    sort(b+1,b+n+1);
    int cnt=unique(b+1,b+1+n)-(b+1);
    for(int i=1;i<=n;++i)
    {
        a[i]=lower_bound(b+1,b+1+cnt,a[i])-b;
    }
    for(int i=1;i<=m;++i)
        scanf("%d%d",&node[i].l,&node[i].r),node[i].id=i;
    sort(node+1,node+1+m);
    int lpos=node[1].l,rpos=lpos-1;
    for(int i=1;i<=m;++i)
    {
        while(lpos>node[i].l) add(--lpos);
        while(rpos<node[i].r) add(++rpos);
        while(lpos<node[i].l) del(lpos++);
        while(rpos>node[i].r) del(rpos--);
        node[i].result=ans;
    }
    sort(node+1,node+1+m,mmp2);
    for(int i=1;i<=m;++i)
        printf("%d\n",node[i].result);
    return 0;
}