带修改莫队算法

update in 2017.12.24:

以前写的≈shit,实在看不下去了,重写一遍

pre

很早之前就学习了莫队算法。

老师讲课的时候就提到过带修改莫队在线莫队树上莫队树上带修改莫队……但是一直都没有做到过有关的题,

今天有幸做了一道裸的带修改莫队的题,

那就来分享一下自己的经验

带修改的莫队

首先我们要知道,普通的莫队算法是不资瓷修改操作的,

不过后人对莫队算法加以改进

发明了资瓷修改的莫队算法

思路:

在进行修改操作的时候,修改操作是会对答案产生影响的(废话)

那么我们如何避免修改操作带来的影响呢?

首先我们需要把查询操作和修改操作分别记录下来。

在记录查询操作的时候,需要增加一个变量来记录离本次查询最近的修改的位置

然后套上莫队的板子,与普通莫队不一样的是,你需要用一个变量记录当前已经进行了几次修改

对于查询操作,如果当前改的比本次查询需要改的少,就改过去

反之如果改多了就改回来

说的听绕口的

比如,我们现在已经进行了3次修改,本次查询是在第5次修改之后,那我们就执行第4,5次修改

这样就可以避免修改操作对答案产生的影响了

 code

题目链接

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=2*1e6+10;
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0',c=getchar();}
    return x*f;
}
int N,M;
int a[MAXN],where[MAXN];
struct Query
{
    int x,y,pre,id;
}Q[MAXN];
int Qnum=0;
struct Change
{
    int pos,val;
}C[MAXN];
int Cnum=0;
int color[MAXN],ans=0,base,out[MAXN];
int comp(const Query &a,const Query &b)
{
    if(a.x!=b.x) return where[a.x]<where[b.x];
    if(a.y!=b.y) return where[a.y]<where[b.y];
    return a.pre<b.pre;
}
void Add(int val)
{    
    if(++color[val]==1) ans++;
} 
void Delet(int val)
{
    if(--color[val]==0) ans--;
}
void Work(int now,int i)
{
    if(C[now].pos>=Q[i].x&&C[now].pos<=Q[i].y)//注意:只有修改在查询的区间内才会对查询的结果产生影响 
    {
        if( --color[a[C[now].pos]] == 0 ) ans--;
        if( ++color[C[now].val] == 1)      ans++; 
    }
    swap(C[now].val,a[C[now].pos]);
    //这里有个很巧妙的操作
    //对于一个操作,下一次需要为的颜色是本次被改变的颜色
    //比如,我把颜色3改为了7,那么再进行这次修改的时候就是把7改为3
    //所以直接交换两种颜色就好 
}
void MoQueue()
{
    int l=1,r=0,now=0; 
    for(int i=1;i<=Qnum;i++)
    {
        while(l<Q[i].x)    Delet(a[l++]);
        while(l>Q[i].x) Add(a[--l]);
        while(r<Q[i].y) Add(a[++r]);
        while(r>Q[i].y) Delet(a[r--]);//以上四句为莫队模板 
        while(now<Q[i].pre) Work(++now,i);//改少了,改过去 
        while(now>Q[i].pre) Work(now--,i);//改多了,改回来 
        out[Q[i].id]=ans;//统计答案 
    }
    for(int i=1;i<=Qnum;i++)
        printf("%d\n",out[i]);
}
int main()
{
    N=read();M=read();
    base=sqrt(N);
    for(int i=1;i<=N;i++) a[i]=read(),where[i]=(i-1)/base+1;
    while(M--)
    {
        char opt[5];
        scanf("%s",opt);
        if(opt[0]=='Q')
        {
            Q[++Qnum].x=read();
            Q[Qnum].y=read();
            Q[Qnum].pre=Cnum;//别忘了记录最近的修改位置 
            Q[Qnum].id=Qnum;        
        }
        else if(opt[0]=='R')
        {
            C[++Cnum].pos=read();
            C[Cnum].val=read();
        }
    }
    sort(Q+1,Q+Qnum+1,comp);//玄学排序 
    MoQueue();
    return 0;
}

边界问题

由于刚开始的now=0

所以需要先增后执行

撤销的时候需要将最后一次的修改撤销掉

所以先执行后减

复杂度证明

普通莫队时间复杂度为O\left( n\times \sqrt {n}\right)

证明:

当我们第i个询问转移的第i+1个询问时

  • 如果第i个询问区间和第i+1个询问区间的左端点所在块的编号相同,那么左端点的移动不会超过\sqrt{n}

      也就是说,左端点一直在块内移动的总复杂度为O(n*\sqrt{n})(因为左端点最多转移n次,减去左端点跨越块的部分,不足n)

      同时由于右端点升序,那么若l,l+1,,,r-1,r的询问区间左端点所在块的编号相等,那么右端点的移动不会超过n次。有一位有\sqrt{n}个块,

      所以这一部分的复杂度是O(n*\sqrt{n})的。

  • 考虑左端点跨越块的情况,每次跨越最大是O(2*\sqrt{n})那么左端点跨越块的复杂度O(n*\sqrt{n})的。

       又在这个期间,每次左端点跨越的时候,右端点可能要移动O(n)次,一共左端点跨越\sqrt{n}个块,所以右端点复杂度是O(n*\sqrt{n})的。

综上莫队算法的排序保证时间复杂度是O(n*\sqrt{n})

带修改莫队算法的时间复杂度证明

以下内容借鉴自洛谷题解

原版莫队是将区间(l,r)视为点(l,r),带修改的即加一维时间轴(l,r,t)

对于t轴的移动可以保存每次修改,如果修改在(l,r)间则更新

分块方法可以参照原版莫队,先将l分块,再讲r分块,同一块的按t排序

块大小为\sqrt [3] {nt}可以达到最快的理论复杂度O\left( \sqrt [3] {n^{4}t}\right),证明如下

设分块大小为a,莫队算法时间复杂度主要为t轴移动,同r块l,r移动,l块间的r移动三部分

t轴移动的复杂度为O\left( \dfrac {n^{2}t}{a^{2}}\right),同r块l,r移动复杂度为0\left( na\right),l块间的r移动复杂度为0\left( \dfrac {n}{a}\right)

三个函数max的最小值当a为\sqrt [3] {nt}取得,为O\left( \sqrt [3] {n^{4}t}\right)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏菩提树下的杨过

全世界最短IE判定if(!+[1,])的解释

虽然从司徒先生的博客上看到 全世界最短的IE判定 很长时间了,却一直对于原理没怎么去细看,今天同事(也是一后台程序员,并非前端)又问到这个问题,于是我这个前端外...

23060
来自专栏PPV课数据科学社区

【学习】数据分析之SPSS数据分组案例

当我们的样本量过大,譬如以前讲过的,EXCEL2010最大只支持1048576行、16384列,尤其是当行数大于30万,一般的办公电脑处理都比较吃力,所以推荐做...

53590
来自专栏生信技能树

可能只是一个函数,却要耗费你大半天

好像不少人问过我一个聚类后的树如何根据肉眼观察到的cluster情况来提前指定的树的子集,有点类似于WGCNA分析把几千个基因划分成若干个module后能提取各...

14430
来自专栏AI研习社

NumPy 将停止支持 Python 2,这里有一份给数据科学家的 Python 3 使用指导

Python 已经成为机器学习和数据科学的主要编程语言,同时 Python 2 和 Python 3 共存与 Python 的生态体系内。不过,在 2019 年...

353110
来自专栏开发 & 算法杂谈

Ad-hoc类型同步识别

尽管之前的我们提出的动态数据竞争验证和检测方法能够比较精确地找到数据竞争,但是该方法还是会存在一部分误检,误检主要就是由于ad-hoc类型的同步引起的,下图展示...

30430
来自专栏AI科技大本营的专栏

实操 | 内存占用减少高达90%,还不用升级硬件?没错,这篇文章教你妙用Pandas轻松处理大规模数据

编译 | AI科技大本营(rgznai100) 参与 | 周翔 注:Pandas(Python Data Analysis Library) 是基于 Num...

27940
来自专栏较真的前端

新手们容易在Promise上挖的坑~

25850
来自专栏听雨堂

Python学习笔记(1):列表元组结构

Python的列表元组功能强大,令人印象深刻。一是非常灵活,二是便于集体操作。特别是以元组作为列表项的结构,和数据访问的结果能够对应起来,和习惯的二维表理解上也...

22460
来自专栏java一日一条

Python算法:如何解决回文索引问题

对于这个问题野蛮的解决方案是遍历S中每个单词大小的窗口并检查它们是否是回文,如下所示:

10020
来自专栏令仔很忙

UML之包图

   当对一个比较复杂的软件系统进行建模时,会有大量的类、接口、组件、节点和图需要处理;如果放在同一个地方的话,信息量非常的大,显得很乱,不方便查询,所以就对这...

1.6K10

扫码关注云+社区

领取腾讯云代金券