xuyunao 的博客

博客

标签

暂无

浅谈莫队的小细节

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-07-20 20:50:18

关于莫队

提起莫队，想必是很多人十分钟爱的暴力算法，毕竟在可以离线的部分区间询问问题当中，只需要花十分钟写一份简单的暴力，就可以获得 $50,80$ 甚至是 $100$ 的分数。

但是在学习简单的莫队的过程中，我也有一些问题以及自己的思考，写在这里分享给大家，希望对热爱或不热爱莫队的你都有帮助。

关于 $l,r$ 的初始值

相信初学莫队，大家都对于 $l = 1,r = 0$ 的写法十分不理解，为什么不能赋值成 $l = 0,r = 0$ 呢？

在这里，我的理解是这样的（欢迎打脸）。

我们先来看莫队过程的代码，我的写法大体长这个样子：

int l = 1,r = 0;
for(int i = 1;i <= m;i++)
{
    int ll = q[i].l;
    int rr = q[i].r;
    while(l < ll) del(a[l]),l++;
    while(l > ll) l--,add(a[l]);
    while(r < rr) r++,add(a[r]);
    while(r > rr) del(a[r]),r--;
    ans[q[i].id] = sum;
}

我们考虑从初始状态需要依次将 $l,r$ 移动到第一个询问处，在这个过程中，假设我们需要将 $l,r$ 均向右移动，那么在这个过程中，我们需要执行下面语句：

    while(l < ll) del(a[l]),l++;
    while(r < rr) r++,add(a[r]);

我们注意观察 $1$ 位置对答案的贡献，当 $l = 1,r = 0$ 时，$1$ 处贡献会由 $l$ 减去一次，由 $r$ 加上一次，不会产生影响。

而如果 $l = 1,r = 1$，就只有 $l$ 减去一次贡献，而没有 $r$ 加上一次贡献。同理，如果 $l = 0,r = 0$，那么就只有 $r$ 加上一次贡献，而没有 $l$ 减去，贡献都会错误。

当然，查询区间端点为 $1$ 的时候自己考虑一下就不难发现时没有影响的。

因此，我们要将莫队初始化为 $l = 1,r = 0$。

关于一些贡献的计算

接下来的问题，并不一定只在莫队中适用，只是恰好最近多次遇到了这个问题，就写在这里，也算是自己一点见解。

先来看个例题。

P4462 [CQOI2018] 异或序列

这道题目，首先一个显然的 trick 是，异或操作是可以类似前缀和去求的，那么我们也就是需要求出区间中有多少对 $x,y$ 满足 $pre_x \oplus pre_y = k$。

我们考虑如何在移动的过程中加入和删除贡献，不难发现，只要我们将一个数对 $x,y$ 的贡献记录在 $x$ 或者 $y$ 其中一个上即可。那么我们每次加入一个数 $x$，直接查询对应的 $y$ 的数量，这样 $x,y$ 的贡献只会在插入 $x$ 时被计算到。

如果还是不太明白，我们以删除操作为例，详细讲解一下。

如果此时我们扫描到了一个数 $x$，想要删除他的贡献。

将 $x$ 对应的 $y$ 分为两类：已经被删除的和未被删除的。

对于已经被删除的，在删除 $y$ 的时候我们会查询到 $x$，因此 $x,y$ 的贡献已经在 $y$ 处被删除过了。对于没有被删除的 $y$，我们查询这些 $y$，并删除贡献，然后从序列中删除 $x$，那么再删到 $y$ 时也不会查询到 $x$，不会重复或遗漏。

所以在做查询数对的题目时，我们就不需要考虑莫队插入和删除的顺序，只需要在插入或删除一个数字的时候，在目前的序列中查询并记录贡献即可，这样可以保证贡献被记录在后加入或删除的元素上，不重不漏。

下面还有一道比较难的题目，也是希望大家知道前面统计贡献方法，嫌麻烦的朋友可以直接跳过。

P12480 [集训队互测 2024] Classical Counting Problem

这道题目只听了做法，还没有写代码。

具体做法大家可以参考这位大神的题解。

最后统计部分，我们需要扫描线扫描 $r$，将 $r_{max} = r$ 的合法 $l,r$ 对统计贡献。

我们考虑将贡献统计在 $l$ 或 $x$ 其中一个，那么我们插入 $x$ 时直接查询 $l$，插入 $l$ 时直接查询 $x$ 计算贡献即可，这样可以做到不重不漏。

这部分主要介绍的是统计数对贡献的一种思路，希望对大家有所帮助。

阅读全文

题解 P3793 由乃救爷爷

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-08-06 14:09:36

题解 P3793 由乃救爷爷

补充一篇其他题解没有出现的做法，思路来自 A_zjzj 老师在 mx 北京最后一天课上的讲解，加上了一些理解，以及来自 Firacode 完善的代码。

题意

题意很简单，给定一个长度为 $n$ 的序列，$m$ 次询问 RMQ。
数据范围：$n,m \le 2 \times 10^7$。

做法

考虑将询问离线下来，按照右端点 $r$ 排序，从前往后扫的过程中维护一个单调栈。由于单调栈维护的是递减序列，当扫描到一个询问时，我们希望对于 $l$ 向后找到第一个位于单调栈内的元素，那么这个元素就是我们希望求出的答案。

具体实现

现在难点就在具体的实现方式上了，我们来考虑每个点。

比较显然的一点，我们不能使用 sort 进行排序，不难想到把每个位置上的询问维护 vector，但实测会 MLE，因此考虑使用计数排序。

接下来的问题就是需要维护出从 $l$ 向后第一个位于单调栈中的元素，其实就是维护一个连续段。

考虑把出栈操作看作删除一个元素，那么我们希望找到从 $l$ 向后第一个没有被删除的元素，这个操作可以使用并查集实现。

具体的，当我们删除掉一个位置 $i$ 时，我们把 $i$ 和 $i + 1$ 合并，想要查询只需要查询 $i + 1$ 的祖先即可，总时间复杂度可以做到 $O(n \lpha)$，记得路径压缩。

虽然跑的比较慢，需要看评测机心情，但也是一种做法。

实现细节

对于一个询问左端点 $l$，我们只需要查询 $l$ 的祖先，而不是 $l + 1$，感性理解一下，最大值是有可能会位于 $l$ 位置的。
注意空间限制。
记得先调用一下 srand 函数。

代码

#include<bits\/stdc++.h>
using namespace std;
const int maxn = 2e7 + 2;
namespace GenHelper
{
    unsigned z1,z2,z3,z4,b;
    unsigned rand_()
    {
    b=((z1<<6)^z1)>>13;
    z1=((z1&4294967294U)<<18)^b;
    b=((z2<<2)^z2)>>27;
    z2=((z2&4294967288U)<<2)^b;
    b=((z3<<13)^z3)>>21;
    z3=((z3&4294967280U)<<7)^b;
    b=((z4<<3)^z4)>>12;
    z4=((z4&4294967168U)<<13)^b;
    return (z1^z2^z3^z4);
    }
}
void srand(unsigned x)
{using namespace GenHelper;
z1=x; z2=(~x)^0x233333333U; z3=x^0x1234598766U; z4=(~x)+51;}
int read()
{
    using namespace GenHelper;
    int a=rand_()&32767;
    int b=rand_()&32767;
    return a*32768+b;
}

int a[maxn],rk[maxn],Max[maxn];
short dep[maxn];
pair<int, int> b[maxn];
int fa[maxn];
stack<int> st;
int getf(int x)
{
    if(fa[x] == x) return x;
    return fa[x] = getf(fa[x]);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    unsigned long long ans = 0;
    int n,m,s;
    cin >> n >> m >> s;
    srand(s);
    for(int i = 1;i <= n;i++) a[i] = read();
    for(int i = 1;i <= m;i++)
    {
        int l = read() % n + 1;
        int r = read() % n + 1;
        if(l > r) swap(l,r);
        b[i] = {l, r};
    }
    for(int i = 1;i <= m;i++) ++fa[b[i].second];
       for(int i = 1;i <= n;i++) fa[i] += fa[i - 1];
       for(int i = m;i >= 1;i--) rk[fa[b[i].second]--] = i;
    for(int i = 1;i <= n;i++) fa[i] = Max[i] = i, dep[i] = 1;
    for(int i = 1, j = 1;i <= n;i++)
    {
        while(st.size() && a[st.top()] <= a[i])
        {
            int k = st.top();
            st.pop();
            int fk = getf(k), ft = getf(k + 1);
            if (dep[fk] < dep[ft]) fa[fk] = ft;
            else if (dep[fk] > dep[ft]) fa[ft] = fk, Max[fk] = Max[ft];
            else fa[fk] = ft, dep[ft]++;
            \/\/ cout << "---" << fk << ' ' << Max[getf(k)] << ' ' << ft << ' ' << Max[ft] << endl;
        }

        st.push(i);
        while(j <= m && b[rk[j]].second == i) ans += a[Max[getf(b[rk[j]].first)]], ++j;
    }
    cout << ans;
    return 0;
}

据说还有链表维护方式，奈何我太菜了不会使用链表，有想法可以私信评论。

希望对你有所帮助。

阅读全文

8.25

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-08-25 09:43:45

CF3D Least Cost Bracket Sequence

首先考虑全是 ? 怎么做，考虑括号序列合法的条件，假设最开始全是 )，在奇数的位置选择一个变成 (。

或者把 ( 看作 $1$，) 看作 $-1$，对于每个位置前缀和非负。

假设最初全都是左括号，用堆维护出从右括号变成左括号的贡献，也就是 $a_i - b_i$ 的最小值，每次加上即可。

CF911G Mass Change Queries

考虑对操作换维，从按照时间维度进行操作变为按照序列维度或按照颜色维度。

按照序列维度，考虑维护 $100$ 个 tag，每次 $O(100)$ 维护线段树，最后查询，复杂度 $O(n \log n)$。

按照颜色维度，对于每个颜色维护，维护颜色为该颜色的位置，维护成 $0/1$，每次线段树分裂合并，复杂度 $O(n \log n)$。

阅读全文

南外 DP 补题记录

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-02 21:03:46

题单

T1

考虑贪心的去做，从子树向上合并，每次肯定把子树内耗时最长的先拨打，排序向上合并即可

T2

Caves

设 $f_{u,i,0/1}$ 表示以 $u$ 为根的子树，走过 $i$ 个点，最后是否会回到 $u$，所需要的最小步数。

树形背包，考虑如何转移，首先 $f_{u,i,0}$ 如果最后走到 $v$ 的子树内，则

$f_{u,i,0} = \min f_{u,i - j,1} + f_{v,j,0} + w$。

如果从 $v$ 子树内绕一圈，最终停留在其他子树，则

$f_{u,i,0} = \min f_{u,i - j,0} + f_{v,j,1} + 2 \times w$。

转移 $f_{u,i,1}$，有

$f_{u,i,1} = \min f_{u,i - j,1} + f_{v,j,1} + 2 \times w$。

最终答案，二分 $i$，判断 $f_{1,i,0/1}$ 是否 $\le x$ 即可。

T3

CF633F

感觉有点难写，还不会。

T4

Bombing plan 题解

消防局的设立加强版，考虑设 $f_{u,i}$ 表示从 $u$ 点向上额外覆盖完 $i$ 层需要选的最少点的数量，考虑如何转移。

记 $sum_{u,i}$ 表示 $\sum_{v \in son_u} f_{v,i}$，转移分三种。

当 $i < 0$ 时，$u$ 向下覆盖 $i$ 层，相当于所有儿子都向下覆盖 $i - 1$ 层，所以从 $\min sum_{u,i + 1(i < 0)}$ 转移。

当 $i > 0$ 时，此时相当于 $u$ 的一个儿子向上覆盖了 $i + 1$ 层，那么其他儿子就只需要向下覆盖 $i - 1$ 层即可，注意正负号细节。

使用 $w_u$ 转移，此时相当于所有儿子只需要向下覆盖 $u$ 层即可。

注意如果向上覆盖更大层数更有，则可以转移给下面的层数。

最后输出答案即可。

T5

购物 The Prices

发现商品很少，考虑状压。

设 $f_S$ 表示购买了 $S$ 集合内的商品需要的最小代价，每次枚举商店，先将所有新的 $f_S = f_S + d_i$，随后枚举购买了哪个商品，即可从同一层转移，具体的

$f_S = \min(f_S,f_{S - (1 << (j - 1))} + c_{i,j})$

最后将没有转移的重新赋值为上一层，这样是避免多加了到达这个商店的花费，最后输出 $f_{(1 << n) - 1}$ 即可。

阅读全文

2024.7.5集训总结

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-05 15:25:23

2024.7.5集训总结

今日收获

模拟赛喜提倒二（day1）
map（字典）
字符串处理
归并排序
逆序对

今日练习题目

今日练习问题

基础语法使用不熟练（太久了过于生疏，以至于字符串的使用都忘了）
基本算法未掌握或使用不熟练
思路不清晰，审题未完全搞懂
未看清数据范围
基础不牢！！！！！

明日计划

深入浅出前三章节复习巩固
学习OI Wiki 2.1 — 2.3
继续做模拟题

阅读全文

2024.7.6比赛总结

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-06 14:25:03

2024.7.6比赛总结

主要问题：

审题！！！（看清题目数据范围）传送门 例如这道T1，数据范围是0 ~ 75，倒序查找时不要写成1 ~ 75（容易爆0）
结合数据范围选择合适的数据类型存储 （例如T3，x、y单个很大，但乘积很小，若使用数组容易爆栈，此时应该使用vector存储）
模板一定要背熟！！！简单搜索的使用
巩固基础！！！
注意变量的使用

题目思路：

通过排序并逆序查找找出第三位的分数并输出分数及人数
不要忘记从0~75

注意读题，阅读题目中隐藏信息（例如数不会再出现）
注意通过题目描述思考判断方式

注意搜索数据范围，根据范围选择合适的数据结构存储
注意搜索过程中标记的使用

未完待续

知识补充：

树状数组
二分查找
归并排序
堆的使用

阅读全文

2024.7.6集训总结

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-06 17:27:04

2024.7.6集训总结

今日收获

堆的使用
归并排序及逆序对
CSP初赛汇总
树状数组
二分查找

练习题目及比赛

比赛总结

ABC361

明日计划

进步亿点点，AC*10；

阅读全文

ABC361 B题解

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-07 06:51:25

ABC361 B题解

原题要解出这道题，首先需要明确判断是否有正体积

根据题意不难得出，没有正体积有两种情况：
1. 两个长方体不接触（第一个长方体最小的>第二个长方体最大的）
2. 两个长方体接触在一个面上（有一个坐标相等）
因此只需要分别判断三个点，只要有一个点不符合就可以：

#include<bits\/stdc++.h>
using namespace std;
int main()
{
	int a,b,c,d,e,f,g,h,i,j,k,l,m;
	cin >> a >> b >> c >> d >> e >> f >> g >> h >> i >> j >> k >> l >> m;
    if (a >= j || g >= d) puts("No");
    else if (b >= k || h >= e) puts("No");
    else if (c >= l || i >= f) puts("No");
    else puts("Yes");
    return 0;

}

阅读全文

ABC361 C题解

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-07 07:31:00

ABC361 C题解

原题题目要求删除几个元素后使数组的极差最小

那么怎么样求最小的极差呢？

众所周知，极差 = 最大值 - 最小值

因此想要使极差最小，就要尽可能的增加最小值或减少最大值；因此删除的K个数要从有序数组中删除头尾，并查找出极差最小情况

首先我们需要输入这个数组并对他进行排序

bool cmp(int a,int b)
{
	return a < b;
}

int n,k;
cin >> n >> k;
for(int i = 0;i < n;i++)
{
	cin >> a[i];
}
sort(a,a+n,cmp);

然后枚举K种情况：

设开头删除i个数，则剩余极差=a[i + n - k - 1] - a[i]
接下来求取最小值即可

阅读全文

【MX-J2】梦熊周赛 · 入门组 2（同步赛）T

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-04 16:31:21

一道简单的水题！（蒟蒻做法勿喷）

原题地址

先来看题意：给三个数a b c，先对a，b运算，再把结果对c进行运算，求有没有一种计算方法使得结果为d

可以直接使用枚举

外层循环枚举a与b运算的符号，内层循环枚举结果与c运算的符号，最后判断如果能够得到答案d输出Yes，否则输出No

下面是AC代码（不喜勿喷）

#include<bits\/stdc++.h>
using namespace std;
char fuh[4] = {'+','-','*','\/'};
int js(int a,int b,char x)
{
	if(x == '+') return a + b;
	else if(x == '-') return a - b;
	else if(x == '*') return a * b;
	else return a \/ b;
}
int main()
{
	int a,b,c;
	cin >> a >> b >> c;
	int d;
	cin >> d;
	for(int i = 0;i < 4;i++)
	{
		char x = fuh[i];
		int m = js(a,b,x);
		for(int j = 0;j < 4;j++)
		{
			char y = fuh[j];
			int n = js(m,c,y);
			if(n == d)
			{
				cout << "Yes";
				return 0;
			}
		}
	}
	cout << "No";
	return 0;
}

感谢各位大佬们的观看，不吝赐赞！！！

阅读全文

共 36 篇博客