首页 > 其他分享 >浅谈莫队

浅谈莫队

时间:2024-01-01 14:11:38浏览次数:36  
标签:cnt 浅谈 get int res 端点 rint 莫队

莫队

基础莫队

[SDOI2009] HH的项链

这道题是卡莫队的,但是确实练习莫队的好题。

首先想一下暴力:
直接暴力枚举询问,然后再枚举区间,这样是O(n^2)的;

想一下优化:
如果说询问是按照 左端点递增 && 右端点递增 的;
那么我们就可以离线排序,用线性的时间扫过去所有询问,用桶记录一下就行,同时记录答案;

但是可能没有这种好情况...可能是两个端点不能同时递增的,最多保证一个递增。
那么在这种情况下要怎么优化呢?

我们可以折中一下:(莫队思想:离线 + 分块 + 双指针)
把询问的左端点按照分块的思想分成sqrt(n)块,然后每一块里面的询问[l,r]按照右端点递增排序!!!

!!!这里我们暂停一下!!!理清楚一个关键点:
在块中:我们询问区间右端点是递增的,但是我们区间左端点不是递增的!!!
在块间:则相反,左端点是递增的,而右端点不是递增的!!!
(正因为这样才需要指针的移动 和 回滚,才有了下面的奇偶优化!)

然后我们定义两个指针i(向r靠齐),j(向l靠齐)
然后开始遍历排好序的询问,每个询问[l,r]我们的i,j就移动,分别向l,r靠齐;
同时用一个桶记录一下数字出现的个数,并更新答案就行!
#include <bits/stdc++.h>

#define int unsigned
#define rint register int
#define endl '\n'

using namespace std;

const int N = 1e6 + 5;
const int M = 3e6 + 5;

struct node
{
    int id, l, r;
} q[N];

int n, m, len = 1;
int a[N], ans[M];
int cnt[M];

int get(int i){return i / len;}

bool cmp(node a, node b)
{
    int l = get(a.l), r = get(b.l);
    if (l != r) return l < r;
    return a.r > b.r;
}

void add(int w, int &res)
{
    if (++cnt[w] == 1) res++;
}

void del(int w, int &res)
{
    if (--cnt[w] == 0) res--;
}

int read() 
{
    register int x = 0,f = 1;
	register char ch;
    ch = getchar();
    while(ch > '9' || ch < '0'){if(ch == '-') f = -f;ch = getchar();}
    while(ch <= '9' && ch >= '0'){x = x * 10 + ch - 48;ch = getchar();}
    return x * f;
}


signed main()
{
    n = read();
    
    for (rint i = 1; i <= n; i++)
    {
		a[i] = read();
	}
    
    m = read();
    unsigned lll = 1;
    len = max(lll, (int)sqrt((double)n * n / m));
    
	for (rint i = 1; i <= m; i++)
    {
        int l = read(), r = read();
        q[i] = {i, l, r};
    }
    
    sort(q + 1, q + m + 1, cmp);
    
    int res = 0;
	for (rint k = 1, i = 1, j = 0; k <= m; k++)
    {
        int id = q[k].id, l = q[k].l, r = q[k].r;
        while (j < r) add(a[++j], res);
        while (j > r) del(a[j--], res);
        while (i < l) del(a[i++], res);
        while (i > l) add(a[--i], res);
        ans[id] = res;
    }
    
    for (rint i = 1; i <= m; i++)
    {
		cout << ans[i] << endl;
	}
        
    return 0;
}

带修改的莫队

[国家集训队] 数颜色

由于增加修改操作,考虑给每一个修改操作按先后顺序编号

将一维改为二维,纵坐标为时间 $time$ ,横坐标为位置 $l,r$

当时间为 $k$ 时,表示已经经过了前 $k$ 个修改操作

若序列长度为 $n$ ,分块后每段长度为 $a$ ,共有 $\frac{n}{a}$ 块, $m$ 次询问, $t$ 次修改(根据数据范围,取合适的 $len$ )

$i$ 表示左指针, $j$ 表示右指针, $time$ 表示时间戳

排序标准为:
1. 比较左端点所在的块,从左到右排序
2. 若左端点所在块相同,则比较右端点所在块,从从左到右排序
3. 若右端点所在块也相同,则比较时间 $times$ ,从左到右排序

指针 $time$ 移动次数: $\frac{n^2t}{a^2}$
指针 $i$ 移动次数: $am+n$
指针 $j$ 移动次数: $am+\frac{n^2}{a}$

#include <bits/stdc++.h>

#define rint register int
#define int long long
#define endl '\n'

using namespace std;

const int N = 1e6 + 5;
const int M = 1e7 + 5;

int n, m;
int times, idx, len;
int a[N], ans[N], cnt[M];

struct node
{
    int l, r, t, id;
} q[N];

struct Modify
{
    int p, c;
} f[N];

int get(int i){return i / len;}

bool cmp(node a, node b)
{
    int al = get(a.l), bl = get(b.l);
    int ar = get(a.r), br = get(b.r);
    if (al != bl) return al < bl;
    if (ar != br) return ar < br;
    return a.t < b.t;
}

void add(int w, int &res)
{
    if (++cnt[w] == 1) res++;
}

void del(int w, int &res)
{
    if (--cnt[w] == 0) res--;
}

signed main()
{
    cin >> n >> m;
    
    for (rint i = 1; i <= n; i++)
    {
		cin >> a[i];
	}
        
    for (rint i = 1; i <= m; i++)
    {
        char op[2];
        int a, b;
        scanf("%s%lld%lld", op, &a, &b);
        if (*op == 'Q') idx++, q[idx] = {a, b, times, idx};
        else f[++times] = {a, b};
    }
    
    len = cbrt((double)n * max(times, 1ll)) + 1;
    
    sort(q + 1, q + idx + 1, cmp);
    
    for (int k = 1, i = 1, j = 0, t = 0, res = 0; k <= idx; k++)
    {
        int l = q[k].l, r = q[k].r, tim = q[k].t, id = q[k].id;
        while (t < tim)
        {
            t++;
            if (f[t].p >= i && f[t].p <= j)
            {
                add(f[t].c, res);
                del(a[f[t].p], res);
            }
            swap(a[f[t].p], f[t].c);
        }
        while (t > tim)
        {
            if (f[t].p >= i && f[t].p <= j)
            {
                add(f[t].c, res);
                del(a[f[t].p], res);
            }
            swap(a[f[t].p], f[t].c);
            t--;
        }
        while (i < l) del(a[i++], res);
        while (i > l) add(a[--i], res);
        while (j < r) add(a[++j], res);
        while (j > r) del(a[j--], res);
        ans[id] = res;
    }
    
    for (rint i = 1; i <= idx; i++)
    {
		cout << ans[i] << endl;
	}
        
    return 0;
}

回滚莫队

AcWing 2523. 历史研究

回滚莫队又称不删除莫队

用于维护一些不删除属性的操作

例如最大值,加入一个数后只需取一次max,删除一个数却很难维护

设序列长度为$n$,每块长度为$a$,共有$\frac{n}{a}$块,$m$次询问

  1. 循环$1\leq i \leq \frac{n}{a}$,找到所有左端点在第$i$块的询问$l$,$r$
  2. 若$r$也在第$i$块,那么就暴力求,时间复杂度$O(am)$
  3. 否则,右端点用指针$j$维护,左端点每次回到第i块的右端,暴力求,时间复杂度$O(am+\frac{n^2}{a})$
  4. #include <bits/stdc++.h>
    
    #define rint register int
    #define int long long
    #define endl '\n'
    
    using namespace std;
    
    const int N = 1e6 + 5;
    
    int n, m, len;
    int w[N], cnt[N];
    int ans[N];
    vector<int> nums;
    
    struct node
    {
        int id, l, r;
    } q[N];
    
    int get(int i){return i / len;}
    
    bool cmp(node a, node b)
    {
        int l = get(a.l), r = get(b.l);
        if (l != r) return l < r;
        return a.r < b.r;
    }
    
    void add(int x, int &res)
    {
        cnt[x]++;
        res = max(res, nums[x] * cnt[x]);
    }
    
    signed main()
    {
        cin >> n >> m;
        
        len = sqrt(n);
    
        for (rint i = 1; i <= n; i++)
        {
    		cin >> w[i];
    		nums.push_back(w[i]);
    	}
            
        sort(nums.begin(), nums.end());
        nums.erase(unique(nums.begin(), nums.end()), nums.end());
        
        for (rint i = 1; i <= n; i++)
        {
            w[i] = lower_bound(nums.begin(), nums.end(), w[i]) - nums.begin();		
    	}
    
        for (rint i = 0; i < m; i++)
        {
            int l, r;
    		cin >> l >> r;
            q[i] = {i, l, r};
        }
    
        sort(q, q + m, cmp);
    
        for (rint x = 0; x < m;)
        {
            int y = x;
            while (y < m && get(q[x].l) == get(q[y].l)) y++;
            int right = get(q[x].l) * len + len - 1;
            while (x < y && q[x].r <= right)
            {
                int res = 0;
                int id = q[x].id, l = q[x].l, r = q[x].r;
                for (rint i = l; i <= r; i++) add(w[i], res);
                ans[id] = res;
                for (rint i = l; i <= r; i++) cnt[w[i]]--;
                x++;
            }
            int res = 0;
            int i = right + 1, j = right;
            while (x < y)
            {
                int id = q[x].id, l = q[x].l, r = q[x].r;
                while (j < r) add(w[++j], res);
                int backup = res;
                while (i > l) add(w[--i], res);
                ans[id] = res;
                while (i < right + 1) cnt[w[i++]]--;
                res = backup;
                x++;
            }
            memset(cnt, 0, sizeof cnt);
        }
    
        for (rint i = 0; i < m; i++)
        {
    		cout << ans[i] << endl;
    	}
    
        return 0;
    }  
    

标签:cnt,浅谈,get,int,res,端点,rint,莫队
From: https://www.cnblogs.com/spaceswalker/p/17938658

相关文章

  • 浅谈一类状态转移依赖邻项的排列计数问题 - 连续段 dp
    UPD2023.12.31:失手把原来的博文删掉了,这篇是补档。引入在一类序列计数问题中,状态转移的过程可能与相邻的已插入元素的具体信息相关(e.g.插入一个新元素时,需要知道与其插入位置相邻的两个元素的值是多少,才可进行状态转移,如「JOIOpen2016」摩天大楼)。这类问题通常的特点是,如......
  • 从《老鼠进洞》开始,浅谈模拟费用流
    部分内容来自WC2018PPT。另外,我真的是浅谈。前置知识在学习一下的内容之前,你需要至少学会费用流相关概念,反悔贪心相关概念和堆。当然了,你还要有足够学会模拟费用流的OI基础,因为本文会略去一部分比较trivial的道理。老鼠进洞(其一)有\(n\)个老鼠\(n\)个洞,每只老鼠向......
  • 浅谈网络流
    浅谈网络流最近网络流做了一堆,感觉有微弱的进步!记录一些好的套路,好的错误,以便以后再错板子根据地方法律法规,最大流中\(Dinic\)以及费用流中\(EK\)不应当被卡,望周知下面并没有出现\(HLPP\)的任何板子因为这个东西十分的难调并理论时间复杂度很对(一定不是指上界......
  • 6 浅谈XILINX FIFO的基本使用
    软件版本:VIVADO2021.1操作系统:WIN1064bit硬件平台:适用XILINXA7/K7/Z7/ZU/KU系列FPGA登录米联客(MiLianKe)FPGA社区-www.uisrc.com观看免费视频课程、在线答疑解惑!1概述首先来大概了解下什么是FIFO,FIFO(FirstInputFirstOutput)简单说就是指先进先出。FIFO也是缓存机......
  • 27 浅谈XILINX BRAM的基本使用
    软件版本:VIVADO2021.1操作系统:WIN1064bit硬件平台:适用XILINXA7/K7/Z7/ZU/KU系列FPGA登录米联客(MiLianKe)FPGA社区-www.uisrc.com观看免费视频课程、在线答疑解惑!1概述对于BRAM详细的说明在XILINX官方文档,pg058中有说明,我们这里仅对课程涉及的内容讲解。Xlinx系列FPGA......
  • 浅谈10kV站所柜内运行状态及环境指标监测管理平台分析
    安科瑞张田田摘要:在整个电能管理系统中,配电室综合监控占据着重要的位置。现阶段,配电室通常均运用无人值守、定时巡查制度,此方式不仅需要投入诸多的物力与人力,同时也不能实时监控配电室的安全与环境。而配电室环境的可靠性与稳定性直接影响着变压器等设备的正常运行。对此,主要对10kV......
  • 浅谈居民小区配电房动力环境监控系统研究与应用
    安科瑞张田田摘要:智配电站动力环境监控系统通过构建三级监控网络,基于TCP/IP网络协议作为通讯构架,组建IP网络与监控中心进行传输。实现对配电站房的远程监控管理。同时采用了集中式管理模式,快速实现区域内配电站房的有效覆盖,为用户提供配电站所的配变电压、电流、有功功率、无功......
  • 浅谈医院基于配电能效管理系统节能减排的实施
    摘要:随着国家节能减排力度的加大,医院作为用能单位,能源的消耗量很大,节能工作势在必行。医院如何实现能源降低20%的目标,节能减排工作面临怎样的困难,有什么样的优势,节能减排应该采用哪些手段与方法实现,针对这些问题进行了探讨。关键词:医院;节能;实施0引言党的十七大报告指出“加强能源资......
  • 浅谈医院电气能源管理与节能措施分析
    安科瑞张田田摘要:医院建筑工程的电气设计比其他行业的电气设计难度大,因为医院是公共场所,人数较多。医院拥有诊疗设备,电学要求因科室的职能而有所不同。本文对医院电气能源管理与节能措施及存在的问题进行了分析,并提出了相应的管理方法和节能对策,从而满足医院可持续发展需求。关键词......
  • 浅谈WPF之ToolTip工具提示
    在日常应用中,当鼠标放置在某些控件上时,都会有相应的信息提示,从软件易用性上来说,这是一个非常友好的功能设计。那在WPF中,如何进行控件信息提示呢?这就是本文需要介绍的ToolTip【工具提示】内容,本文以一些简单的小例子,简述如何在WPF开发中,应用工具提示,仅供学习分享使用,如有不足之处,还......