首页 > 其他分享 >[bzoj2120]数颜色/维护队列 (分块)

[bzoj2120]数颜色/维护队列 (分块)

时间：2024-03-16 16:14:27浏览次数：19  
标签：cnt 分块 队列 len int getnum bzoj2120 vx --

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

此生第一道不贺题解\(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<=n;i++)  a[i]=c[i];
    sort(a+1,a+n+1);
    m=unique(a+1,a+n+1)-a-1;
    for(int i=1;i<=m;i++)
        t[a[i]]=i;
    for(int i=1;i<=n;i++)
        c[i]=t[c[i]];
    //一般都是用lower_bound查找位置，但是1e6的数组我们开得起，干脆直接O(1)，加上后面会提到的一些原因，所以我们这样进行nb的离散化
    return;
}
  • \(spx[i][j]\) 表示第 \(i\) 到 \(j\) 块中不同的数的数量（这个还是挺好想的）。空间 \(O(M^2)\)。
  • \(vis[i]\) 记录数 \(i\) 被访问的状态，用于预处理和查询操作。空间 \(O(10^6)\)。

接下来是预处理。

  • 处理\(cnt\)
for(int i=1;i<=tot;++i)
{
    for(int j=L[i];j<=R[i];++j)
    {
        v[j]=i;//这相当于belong数组，个人马蜂
        cnt[i][c[j]]++;
    }
    for(int j=1;j<=m;++j)
        cnt[i][j]+=cnt[i-1][j];
}
  • 处理\(spx\)
#define getnum(A,B,C) (cnt[B][C]-cnt[A-1][C])//块A至块B中C的数量
for(int i=1;i<=tot;++i)
{
    for(int j=i;j<=tot;++j)
    {
        spx[i][j]=spx[i][j-1];
        for(int k=L[j];k<=R[j];++k)
        {
            if((!getnum(i,j-1,c[k]))&&(!vis[c[k]]))//这很好理解
            {
                vis[c[k]]=1;
                spx[i][j]++;
            }
        }
        for(int k=L[j];k<=R[j];++k)  vis[c[k]]=0;//O(len)清零
    }
}
  • 所以总的预处理
#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<=tot;++i)
    {
        L[i]=R[i-1]+1;
        R[i]=L[i]+len-1;
    }
    R[tot]=n;
    for(int i=1;i<=tot;++i)
    {
        for(int j=L[i];j<=R[i];++j)
        {
            v[j]=i;
            cnt[i][c[j]]++;
        }
        for(int j=1;j<=m;++j)
            cnt[i][j]+=cnt[i-1][j];
    }
    for(int i=1;i<=tot;++i)
    {
        for(int j=i;j<=tot;++j)
        {
            spx[i][j]=spx[i][j-1];
            for(int k=L[j];k<=R[j];k++)
            {
                if((!getnum(i,j-1,c[k]))&&(!vis[c[k]]))
                {
                    vis[c[k]]=1;
                    spx[i][j]++;
                }
            }
            for(int k=L[j];k<=R[j];k++)  vis[c[k]]=0;
        }
    }
}

重头戏来喽！单点修改，将位置 \(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<=tot;++j)
        {
            if(getnum(i,j,k))  break;
            spx[i][j]++;
        }
if(getnum(vx,vx,cx)==1)
    for(int i=vx;i>=1;--i)
        for(int j=vx;j<=tot;++j)
        {
            if(getnum(i,j,cx)!=1)  break;
            spx[i][j]--;
        }

最后改一下 \(cnt\) 就好了

for(int i=vx;i<=tot;i++)
    cnt[i][k]++,cnt[i][cx]--;
  • 最终的 \(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<=tot;j++)
            {
                if(getnum(i,j,k))  break;
                spx[i][j]++;
            }
        }
    }  
    if(getnum(vx,vx,cx)==1)
    {
        for(int i=vx;i>=1;--i)
        {
            for(int j=vx;j<=tot;j++)
            {
                if(getnum(i,j,cx)!=1)  break;
                spx[i][j]--;
            }
        } 
    }
    for(int i=vx;i<=tot;i++)
        cnt[i][k]++,cnt[i][cx]--;

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

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

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

\(AC \ \ code\)

具体注释见上文

#include<bits/stdc++.h>
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<'0'||c>'9') {if(c=='-')  f=-1;c=getchar();}
    while(c>='0'&&c<='9')   x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f*x;
}
void write(int x)
{
    if(x<0)  putchar('-'),x=-x;
    if(x>9)  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<=n;i++)  a[i]=c[i];
    sort(a+1,a+n+1);
    m=unique(a+1,a+n+1)-a-1;
    for(int i=1;i<=m;i++)
        t[a[i]]=i;
    for(int i=1;i<=n;i++)
        c[i]=t[c[i]];
    return;
}

void init()
{
    LSH();
    len=1000;
    //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<=tot;i++)
    {
        L[i]=R[i-1]+1;
        R[i]=L[i]+len-1;
    }
    R[tot]=n;
    for(int i=1;i<=tot;i++)
    {
        for(int j=L[i];j<=R[i];j++)
        {
            v[j]=i;
            cnt[i][c[j]]++;
        }
        for(int j=1;j<=m;j++)
            cnt[i][j]+=cnt[i-1][j];
    }
    for(int i=1;i<=tot;i++)
    {
        for(int j=i;j<=tot;j++)
        {
            spx[i][j]=spx[i][j-1];
            for(int k=L[j];k<=R[j];k++)
            {
                if(cnt[j-1][c[k]]-cnt[i-1][c[k]]==0&&vis[c[k]]==0)
                {
                    vis[c[k]]=1;
                    spx[i][j]++;
                }
            }
            for(int k=L[j];k<=R[j];k++)  vis[c[k]]=0;
        }
    }
}

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<=tot;j++)
            {
                if(getnum(i,j,k))  break;
                spx[i][j]++;
            }
        }
    }  
    if(getnum(vx,vx,cx)==1)
    {
        for(int i=vx;i>=1;--i)
        {
            for(int j=vx;j<=tot;j++)
            {
                if(getnum(i,j,cx)!=1)  break;
                spx[i][j]--;
            }
        } 
    }
    for(int i=vx;i<=tot;i++)
        cnt[i][k]++,cnt[i][cx]--;
}

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

signed main()
{
    n=read,T=read;
    for(int i=1;i<=n;i++)  c[i]=read;
    init();
    char op;int x,y;
    while(T--)
    {
        cin>>op;x=read,y=read;
        if(op=='Q')
            write(query(x,y)),pt;
        else
            modify(x,y);
    }
    return 0;
}

推荐一下呗~

标签：cnt,分块,队列,len,int,getnum,bzoj2120,vx,--
From： https://www.cnblogs.com/lty-ylzsx/p/18077027

相关文章

  • 分块学习笔记
    学了分块，感觉这玩意好难啊，怎么听起来这么简单？【】【】分块！先推荐一个东西：loj分块全家桶！首先，把一整个数组劈成\(\sqrtn\)块是最优的！（当然如果你想写一个\(114514\)块的分块也没问题但他不优啊！）长这样：这样它的复杂度是：预处理：\(O(n\sqrtn+q)\)在线处理：\(O(q\sqrtn+n)\)......
  • 数论分块
    数论分块分块整除例题G-几番烟雾，只有花难护向上取整注意相减时要加上模数再取模#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'#defineintlonglong#definedb(x)cout<<x<<""<<endl;#define_db(a,n)for(inti=1;i<=n;i++)......
  • 【linux system V 消息队列】
    #简介消息队列就是一些消息的列表，或者说是一些消息组成的队列。消息队列与管道有些类似，消息队列可以认为是管道的改进版。相较于管道的先进先出准则，消息队列在读取时可以按照消息的类型进行读取，这也是消息队列的特点，它可以实现消息随机查询。消息发送时,需要将消息封装，然......
  • 单调队列
    题目1点击查看代码#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#definepiipair<int,int>#defineinf0x3f3f3f3fsignedmain(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);intn,m;cin>>n>>m;......
  • leedcode-用队列实现栈
    利用内置的listclassMyStack:def__init__(self):#初始化一个空列表用于存储栈的元素self.li=list()defpush(self,x:int)->None:#向栈中压入元素xself.li.append(x)defpop(self)->int:#从栈顶弹......
  • 代码随想录算法训练营第十天| 232. 用栈实现队列 225. 用队列实现栈
    232.用栈实现队列https://leetcode.cn/problems/implement-queue-using-stacks/description/classMyQueue{Stack<Integer>stackIn;Stack<Integer>stackOut;publicMyQueue(){stackIn=newStack<>();stackOut=new......
  • Python使用RocketMQ(消息队列)
    消息队列在日常开发中比较常用的开发中间件，每家大厂一般都会具有自己的消息队列服务器。本文主要讲述Python中如何使用RocketMQ的相关SDK。希望大家在阅读本文前可以先了解一下RocketMQ的基本知识。使用 pipinstallrocketmq-ihttps://pypi.tuna.tsinghua.edu.cn/sim......
  • LeetCode232.栈实现队列
    ques:用两个栈实现队列功能ans:与225一样的思路，看完225大佬们的题解之后能很轻松的想出思路，用s1来实现真正模拟队列中的元素顺序，借助s2辅助完成这一排序代码实现#include<iostream>#include<stack>usingnamespacestd;classMyQueue{private:stack<int>s1;/......
  • 多线程(代码案例: 单例模式, 阻塞队列, 生产者消费者模型,定时器)
    设计模式是什么类似于棋谱一样的东西计算机圈子里的大佬为了能让小菜鸡的代码不要写的太差针对一些典型的场景,给出了一些典型的解决方案这样小菜鸡们可以根据这些方案(ACM里面叫板子,象棋五子棋里叫棋谱,咱这里叫设计模式),略加修改,这样代码再差也差不到哪里去......
  • JS 队列（数据结构）- 笔记
    【队列】代码：/***链表队列*/classLinkedListQueue{/**@type{ListNode}*/#head;/**@type{ListNode}*/#tail;/**@type{number}*/#size;constructor(){this.#head=null;this.#tail=null;this......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99