[BZOJ1878/Luogu1972][SDOI2009]HH的项链(莫队算法,离线,分块)

发布于 2018-01-28  200 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1878/Luogu1972][SDOI2009]HH的项链(莫队算法,离线,分块)

Description

HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运,所以每次散步 完后,他都会随意取出一段贝壳,思考它们所表达的含义。HH不断地收集新的贝壳,因此他的项链变得越来越长。有一天,他突然提出了一个问题:某一段贝壳中,包含了多少种不同的贝壳?这个问题很难回答。。。因为项链实在是太长了。于是,他只好求助睿智的你,来解决这个问题。

Http

BZOJ
Luogu

Tag

莫队算法,离线,分块

解决思路

类似这一题的方法,分块排序后移动端点构造答案

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=50010;
const int maxM=200100;
const int maxColor=1000100;
const int inf=2147483647;

class Data
{
public:
    int l,r,id;
    int Ans;
};

int n,m,Ans;
int Belong[maxN];
Data Q[maxM];
int Color[maxN],Sum[maxColor];

bool cmp1(Data A,Data B);
bool cmp2(Data A,Data B);
void Move(int pos,int opt);

int main()
{
    scanf("%d",&n);int size=sqrt(n);//这里块的大小取sqrt(n)为最佳
    for (int i=1;i<=n;i++) scanf("%d",&Color[i]),Belong[i]=(i-1)/size+1;
    scanf("%d",&m);
    for (int i=1;i<=m;i++) scanf("%d%d",&Q[i].l,&Q[i].r),Q[i].id=i;
    sort(&Q[1],&Q[m+1],cmp1);
    int l=1,r=0;
    for (int i=1;i<=m;i++)
    {
        while (l<Q[i].l) Move(l,-1),l++;
        while (l>Q[i].l) Move(l-1,1),l--;
        while (r<Q[i].r) Move(r+1,1),r++;
        while (r>Q[i].r) Move(r,-1),r--;
        Q[i].Ans=Ans;
    }
    sort(&Q[1],&Q[m+1],cmp2);
    for (int i=1;i<=m;i++) printf("%d\n",Q[i].Ans);
    return 0;
}

bool cmp1(Data A,Data B)
{
    if (Belong[A.l]==Belong[B.l]) return A.r<B.r;
    return A.l<B.l;
}


bool cmp2(Data A,Data B)
{
    return A.id<B.id;
}

void Move(int pos,int opt)
{
    if (Sum[Color[pos]]) Ans--;
    Sum[Color[pos]]+=opt;
    if (Sum[Color[pos]]) Ans++;
    return;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1878/Luogu1972][SDOI2009]HH的项链(莫队算法,离线,分块)


HNCJ OIer