BZOJ 2120: 数颜色 分块

时间：2021-09-08 22:27:27

2120: 数颜色

Time Limit: 20 Sec

Memory Limit: 256 MB

题目连接

http://www.lydsy.com/JudgeOnline/problem.php?id=2120

Description

墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会像你发布如下指令： 1、 Q L R代表询问你从第L支画笔到第R支画笔*有几种不同颜色的画笔。 2、 R P Col 把第P支画笔替换为颜色Col。为了满足墨墨的要求，你知道你需要干什么了吗？

Input

第1行两个整数N，M，分别代表初始画笔的数量以及墨墨会做的事情的个数。第2行N个整数，分别代表初始画笔排中第i支画笔的颜色。第3行到第2+M行，每行分别代表墨墨会做的一件事情，格式见题*分。

Output

对于每一个Query的询问，你需要在对应的行中给出一个数字，代表第L支画笔到第R支画笔*有几种不同颜色的画笔。

Sample Input

6 5
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6

Sample Output

4
4
3
4

HINT

对于100%的数据，N≤10000，M≤10000，修改操作不多于1000次，所有的输入数据中出现的所有整数均大于等于1且不超过10^6。

题意

两个操作，单点修改，以及查询区间有多少个数不一样

题解：

很显然，我们记录每个数他的前一个数的位置在哪儿，如果不存在就记录为-1

那么我们查询的时候，就只用查询[l,r]区间中小于l的数有多少个就好了，这个用平衡树解决就好了

下面是分块的代码，修改是o(n),查询是sqrt(n)*logn的，由于题目说了，修改操作很少，所以算是水过去了……

代码来自hzwer

代码：

//qscqesze

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

#include <stack>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define maxn 2000051

#define mod 10007

#define eps 1e-9

int Num;

//const int inf=0x7fffffff;   //нчоч╢С

const int inf=0x3f3f3f3f;

inline ll read()

{

    ll x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

//**************************************************************************************

int n,q,m,block;

int c[maxn],pos[maxn],pre[maxn],b[maxn],last[maxn];

void reset(int x)

{

    int l=(x-)*block+,r=min(x*block,n);

    for(int i=l;i<=r;i++)pre[i]=b[i];

    sort(pre+l,pre+r+);

}

void build()

{

    for(int i=;i<=n;i++)

    {

        b[i]=last[c[i]];

        last[c[i]]=i;

        pos[i]=(i-)/block+;

    }

    for(int i=;i<=m;i++)

        reset(i);

}

int find(int x,int v)

{

    int l = (x-)*block+,r=min(x*block,n);

    int first=l;

    while(l<=r)

    {

        int mid=(l+r)>>;

        if(pre[mid]<v)l=mid+;

        else r=mid-;

    }

    return l-first;

}

int ask(int l,int r)

{

    int ans=;

    if(pos[l]==pos[r])

    {

        for(int i=l;i<=r;i++)

            if(b[i]<l)

                ans++;

    }

    else

    {

        for(int i=l;i<=block*pos[l];i++)

            if(b[i]<l)

                ans++;

        for(int i=block*(pos[r]-)+;i<=r;i++)

            if(b[i]<l)

                ans++;

    }

    for(int i=pos[l]+;i<pos[r];i++)

        ans+=find(i,l);

    return ans;

}

void change(int x,int v)

{

    for(int i=;i<=n;i++)

        last[c[i]]=;

    c[x]=v;

    for(int i=;i<=n;i++)

    {

        int t=b[i];

        b[i]=last[c[i]];

        if(t!=b[i])reset(pos[i]);

        last[c[i]]=i;

    }

}

int main()

{

    n=read(),q=read();

    for(int i=;i<=n;i++)

        c[i]=read();

    block = int(sqrt(n));

    if(n%block)m=n/block+;

    else m = n/block;

    build();

    char ch[];int x,y;

    for(int i=;i<=q;i++)

    {

        scanf("%s%d%d",ch,&x,&y);

        if(ch[]=='Q')

            printf("%d\n",ask(x,y));

        else

            change(x,y);

    }

    return ;

}

相关文章