数颜色/维护队列 [做题笔记]

此生第一道不贺题解(AC)的分块蓝题！！！

题目描述

墨墨@hs_mo购买了一套 (N) 支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会向你发布如下指令：

1. (Q L R) 代表询问你从第 (L) 支画笔到第 (R) 支画笔中共有几种不同颜色的画笔。

2. (R P C) 把第 (P) 支画笔替换为颜色 (C)。

为了满足墨墨的要求，你知道你需要干什么了吗？

输入

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

输出

4
4
3
4

(n,m leq 10000)

所有的输入数据中出现的所有整数均大于等于 (1) 且不超过 (10^6)。

---

一句话概括，给定序列 (a) ，要查询 ([l,r]) 中共有多少个不一样的数，可以修改位置 (x) 的值。

做题历程 废话可忽略

学校(OJ)数据水，但是luogu ……

一开始想贺题解，全是带修莫队，正当我想要颓题解学莫队时，@xrlong跟我说分块可过，于是推了十几分钟，发现分块确实可做，虽然当时思路有很多纰漏，于是拍了好几(w)组数据，狂调一下午，终于擦着边在学校(OJ)过了，接着疯狂优化…… (（time–;)可读性(–;）)

最为难绷的是：

1. 我把块长 (len) 开成 (sqrt{n}) ，会 (TLE 8,9,10) 三个点；
2. 我把块长 (len) 开成 (n^{frac{2}{3}}) ，会 (TLE 11,12,13) 三个点；
3. 于是我一怒之下怒了一下，把 (len) 开成 (frac{sqrt{n}+n^{frac{2}{3}}}{2})，也就是取个平均，然后就…… (AC)了。

然后就从@CuFeO4口中得知，某些可爱的出题人会卡块长，然后他把我的块长改成(1000)，它也过了……

上述皆为废话

思路分析

---

下面进入正题，我们要求区间内有几种不同的数，可以类比P4168蒲公英求区间众数，我们维护两个数组：

• (cnt[i][j]) 表示前 (i) 块数 (j) 出现的次数 (类似于前缀和) ，于是可以 (O(1)) 查询两个块之间某个数出现过的次数。空间复杂度 (O(M times 10^6)) ，他们说可过，但是我的码不行，于是一波去重，再用一个(t)数组，(t[x]) 表示数 (x) 映射的结果（这很显然是离散化）。然后空间就降到了 (O(M times N),M) 是块的数量。

int t[MAXN],a[N],m;
void LSH()
{
    for(int i=1;i

• (spx[i][j]) 表示第 (i) 到 (j) 块中不同的数的数量（这个还是挺好想的）。空间 (O(M^2))。
• (vis[i]) 记录数 (i) 被访问的状态，用于预处理和查询操作。空间 (O(10^6))。

---

接下来是预处理。

• 处理(cnt)

for(int i=1;i

• 处理(spx)

#define getnum(A,B,C) (cnt[B][C]-cnt[A-1][C])//块A至块B中C的数量
for(int i=1;i

• 所以总的预处理

#define getnum(A,B,C) (cnt[B][C]-cnt[A-1][C])
int c[N],v[N],L[M],R[M],tot,len;
int cnt[M][N],spx[M][M];
void init()
{
    LSH();
    len=1000;//为啥是这个nb的块长，废话中已提到。。。
    //len=(sqrt(n)+pow(n,2.0/3))/2;
    // len=sqrt(n);
    // len=pow(n,2.0/3);
    tot=(n-1)/len+1;
    for(int i=1;i

---

重头戏来喽！单点修改，将位置 (x) 改为 (k)

首先肯定要将 (k) 离散化，但是——原序列里不一定有 (k) ,此乃本题坑人之处。因此我们上文的离散化方法就很香了。

if(!t[k])//k没有出现过
    t[k]=++m;//k离散化为m+1
k=t[k];

下一步，修改 (spx) 数组，这是精髓。

如图设要修改的 (x) 所在块为 (vx) ，如果存在：

1. (getnum(i,j,k)=0,i leq vx leq j leq tot) ，显然此时(i,j)中没有 (k) ,则 (spx[i][j]++)
2. 修改前原数为 (cx) ，当 (getnum(i,j,cx)=1,i leq vx leq j leq tot) 时，显然此时 (i,j)中删去 (cx) 就没有了，则 (spx[i][j]–)

很好想吧？这是我的 优化.max.plus

int vx=v[x],cx=c[x];
c[x]=k;
if(!getnum(vx,vx,k))
    for(int i=vx;i>=1;--i)
        for(int j=vx;j=1;--i)
        for(int j=vx;j

最后改一下 (cnt) 就好了

for(int i=vx;i

• 最终的 (modify())

void modify(int x,int k)
{
    if(!t[k])    t[k]=++m;
    k=t[k];
    if(c[x]==k)  return;
    int vx=v[x],cx=c[x];
    c[x]=k;
    if(!getnum(vx,vx,k))
    {
        for(int i=vx;i>=1;--i)
        {
            for(int j=vx;j=1;--i)
        {
            for(int j=vx;j

---

然后就是很水的 (query())

int query(int l,int r)
{
    int res=0;
    int vl=v[l],vr=v[r];
    if(vr-vl=L[vr];--i)
        if((!getnum(vl+1,vr-1,c[i])) && (!vis[c[i]]))
            res++,vis[c[i]]=1;
    for(int i=l;i

---

最后吐槽一下，洛谷数据真的麻，本题轻微卡常(谷上卡常严重，对分块做法及其不友好)

(AC code)

具体注释见上文

#include
using namespace std;
#define getnum(A,B,C) (cnt[B][C]-cnt[A-1][C])
const int MAXN=1e6+10;
#define N 200000
#define M 1100
#define read read()
#define pt puts("")
inline int read
{
    int x=0,f=1;char c=getchar();
    while(c'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c9)  write(x/10);
    putchar(x%10+'0');
    return;
}
int n,T;
int c[N],v[N],L[M],R[M],tot,len;
int cnt[M][N],spx[M][M];
int t[MAXN],a[N],m;
bool vis[N];

void LSH()
{
    for(int i=1;i=1;--i)
        {
            for(int j=vx;j=1;--i)
        {
            for(int j=vx;j=L[vr];--i)
        if((!getnum(vl+1,vr-1,c[i])) && (!vis[c[i]]))
            res++,vis[c[i]]=1;
    for(int i=l;i>op;x=read,y=read;
        if(op=='Q')
            write(query(x,y)),pt;
        else
            modify(x,y);
    }
    return 0;
}

推荐一下呗~

服务器托管，北京服务器托管，服务器租用 http://www服务器托管网.fwqtg服务器托管网.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net

相关推荐: HTML选择题试题——附答案

单选题 HTML的缩写是什么？ A) Hyper Tool Markup Language B) Hyperlinks and Text Markup Language C) Hyper Text Markup Language D) Home Tool Ma…