首页 > 其他分享 >20240923 分块莫队专题

20240923 分块莫队专题

时间:2024-11-08 15:20:06浏览次数:1  
标签:分块 int 询问 pos 20240923 端点 ans 莫队

20240923 分块莫队专题

回滚莫队

回滚莫队适用于添加与删除中有一种较为困难的情况。大致思想如下:

对原序列分块,将询问按左端点所在块编号排序,同一块内按右端点排序。对每个块,视情况初始化左右指针,扫一遍询问。先移动右指针到询问右端点,记录当前状态的答案,再将左指针移到询问左端点,计算询问的答案,最后把左指针撤回块的左端点,答案撤销,撤销对某些状态的影响。这样每一块中右指针移动 \(O(n)\) 次,对于每个询问左端点最多移动 \(O(\sqrt n)\) 次,于是可以保证时间复杂度。

注意:在不删除的回滚莫队中,询问左右端点在同一块中时需要暴力求解。

[1.历史研究](歴史の研究 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)) (不删除莫队)

给你一个数组 \(a\) 和 \(m\) 个询问 \((1\leq n,m\leq10^5)\),每次询问一个区间内重要度最大的数字,输出其重要度。一个数字 \(i\) 的重要度的定义为 \(i\) 乘上 \(i\) 在区间内出现的次数。

这个题目提添加很好实现,因为如果添加影响答案,那么新答案一定是刚刚添加的数字的重要度,但是删除很难实现。所以使用回滚莫队。

struct Query{
	int l, r, ans, idx;
}q[N];

int n, Q, a[N], b[N], T, pos[N], L[N], R[N], cnt[N];

void init(){
	map<int, int> mp;
	sort(b + 1, b + n + 1);
	int m = unique(b + 1, b + n + 1) - b - 1;
	for (int i = 1; i <= m; i++) mp[b[i]] = i;
	for (int i = 1; i <= n; i++) a[i] = mp[a[i]]; //离散化
	int K = sqrt(n); T = n / K + (bool)(n % K); //对原序列分块
	for (int i = 1; i <= T; i++){
		L[i] = R[i - 1] + 1;
		R[i] = min(L[i] + K - 1, n);
		for (int j = L[i]; j <= R[i]; j++) pos[j] = i;
	}
	sort(q + 1, q + Q + 1, [&](Query a, Query b){
		return pos[a.l] != pos[b.l] ? pos[a.l] < pos[b.l] : a.r < b.r;
	}); //对询问排序
}

void add(int p, int &maxn){
	maxn = max(maxn, ++cnt[a[p]] * b[a[p]]);
}

signed main(){
	n = read(), Q = read();
	for (int i = 1; i <= n; i++) a[i] = b[i] = read();
	for (int i = 1; i <= Q; i++) q[i] = {read(), read(), 0, i};
	init();
	for (int i = 1, p = 1; i <= T; i++){
		int ans = 0, l = R[i] + 1, r = R[i];
		while (pos[q[p].l] == i){
            if (pos[q[p].l] == pos[q[p].r]){ //暴力求解
                for (int i = q[p].l; i <= q[p].r; i++){
                    q[p].ans = max(q[p].ans, ++cnt[a[i]] * b[a[i]]);
                }
                for (int i = q[p].l; i <= q[p].r; i++) --cnt[a[i]];
                p++;
                continue;
            }
			while (r < q[p].r) add(++r, ans); //移动右指针
			int tmp = ans; //记录状态
			while (l > q[p].l) add(--l, ans); //移动左指针
			q[p].ans = ans; ans = tmp;
			while (l < R[i] + 1) cnt[a[l++]]--; //回滚
			p++;
		}
        while (l <= r) cnt[a[l++]]--; //清空
	}
	sort(q + 1, q + Q + 1, [&](Query a, Query b){
		return a.idx < b.idx;
	});
	for (int i = 1; i <= Q; i++) printf("%lld\n", q[i].ans);
	return 0;
}
[2.秃子酋长]([[P8078 WC2022] 秃子酋长 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)) (不添加莫队)

给一个排列 \(a\),有 \(m\) 次询问,每次询问区间内,排序后相邻的数在原序列中的位置的差的绝对值之和。\(1\leq n,m\leq 5\times10^5\)。

容易想到 set 维护当前集合,更新方式显然,设 \(n,m\) 同阶,那么这样是 \(O(n\sqrt{n\log n})\) 的。

注意到删除操作可以用链表做到 \(O(1)\),但链表难以添加,于是使用回滚莫队。

这题时限较紧,常数较小才能通过。

#define fi first
#define se second

int n, Q, T, a[N], L[N], R[N], pos[N], dlt[N], _[N];
long long ans[M], res;

struct Query{
	int l, r, idx;
}q[M];

struct Node{
	int pre, nxt, val;
}lst[N];

inline bool cmp(const Query &a, const Query &b){
	return pos[a.l] != pos[b.l] ? pos[a.l] < pos[b.l] : a.r > b.r;
}

inline void init(){
	int K = sqrt(2 * n); T = n / K + (bool)(n % K);
	for (int i = 1; i <= T; i++){
		L[i] = R[i - 1] + 1;
		R[i] = min(L[i] + K - 1, n);
		for (int j = L[i]; j <= R[i]; j++) pos[j] = i;
	}
	sort(q + 1, q + Q + 1, cmp);
    for (int i = 1; i <= n; i++) _[a[i]] = i;
	for (int i = 1; i <= n; i++) lst[i] = {i - 1, i + 1, _[i]};
	lst[1].pre = 0, lst[n].nxt = 0;
    for (int i = 1 + 1; i <= n; i++) res += abs(lst[i].val - lst[lst[i].pre].val);
}

inline int del(const int &p){
	int nxt = lst[p].nxt, pre = lst[p].pre, res = 0;
	lst[pre].nxt = nxt, lst[nxt].pre = pre;
	if (pre && nxt) res += labs(lst[nxt].val - lst[pre].val);
	if (nxt) res -= labs(lst[nxt].val - lst[p].val);
	if (pre) res -= labs(lst[p].val - lst[pre].val);
	return dlt[p] = res; //这里用数组记录下删数时的贡献,回滚时直接调用,减小常数
}

inline int ret(const int &p){
	int nxt = lst[p].nxt, pre = lst[p].pre;
	lst[pre].nxt = lst[nxt].pre = p;
	return -dlt[p];
}

int main(){
	n = read(), Q = read();
	for (int i = 1; i <= n; i++) a[i] = read();
	for (int i = 1; i <= Q; i++) q[i] = {read(), read(), i};
	init();
	for (int i = 1, p = 1, l = 1, r = n; i <= T; i++){
		if (pos[q[p].l] != i) continue; 
		for (; r < n; ) res += ret(a[++r]);
		for (; l < L[i]; ) res += del(a[l++]);
		for (; pos[q[p].l] == i; ){
			for (; r > q[p].r; ) res += del(a[r--]);
			for (; l < q[p].l; ) res += del(a[l++]);
			ans[q[p].idx] = res;
			for (; l > L[i]; ) res += ret(a[--l]);
			p++;
		}
	}
	for (int i = 1; i <= Q; i++) printf("%lld\n", ans[i]);
	return 0;
}

这题还有一个版本,就是将求和改为求最小值,仍然用链表维护。查询最值可以用值域分块 \(O(1)\) 修改,\(O(\sqrt n)\) 查询。块长取 \(\sqrt{\frac{n^2}{m}}\) 时最优理论复杂度 \(O(n\sqrt m)\),但是常数过大,无法通过原题。

未完待续。。。

标签:分块,int,询问,pos,20240923,端点,ans,莫队
From: https://www.cnblogs.com/luyuyang/p/18535163

相关文章

  • markdown矩阵分块和latex中矩阵分块记录
    1.markdown中常见的符号附件\hat{X}\widehat{X}\check{X}\breve{X}\tilde{X}\dot{X}\ddot{X}\overline{X}\underline{X}2.markdown中矩阵由\left[ right],\begin{array}{ccc}\end{array}包围,分行由\\实现,分列通过ccc固定列数,列与列间用&分割代码:\left[\begin......
  • 408数据结构-折半查找,分块查找 自学知识点整理
    前置知识:查找的基本概念折半查找折半查找又称二分查找,它仅适用于有序的顺序表。因个人习惯,下文均用二分代替折半。二分查找的基本思想:首先将给定值ke......
  • 数论分块
    数论分块讲解先咕咕,做杜教筛做错题了做了个数论分块,下次再讲。题目示例P3327[SDOI2015]约数个数和设\(d(x)\)为\(x\)的约数个数,给定\(n,m\),求\[\sum_{i=1}^n\sum_{j=1}^md(ij)\]对于\(100\%\)的数据,\(1\leT,n,m\le50000\)。\[\sum_{i=1}^n\sum_{j=1}^md(ij)=......
  • 【算法】莫队
    1.算法简介莫队算法有很多种:普通莫队,带修莫队,回滚莫队,树上莫队,二维莫队,莫队二次离线。莫队算法主要用于解决支持快速插入,删除贡献的区间优化问题。具体的,对于要求解贡献的区间\([l,r]\)来说,我们可以把以前求解过的区间\([L,R]\)的贡献保留下来,并通过移动\(L,R\),同时插入,......
  • LOJ 数列分块入门2
    算法考虑求小于给定值的数的个数,可以给每个块再维护一个已经排好序的数组,整块加法对于这个块排好序的数组没有影响,零散块加法直接在原序列上加,再将零散块所处的整块从新排序。查询时零散块暴力查找,整块二分查找代码#include<bits/stdc++.h>#defineintlonglongconstintM......
  • 洛谷P4074糖果公园(带修莫队)
    [WC2013]糖果公园题目描述Candyland有一座糖果公园,公园里不仅有美丽的风景、好玩的游乐项目,还有许多免费糖果的发放点,这引来了许多贪吃的小朋友来糖果公园游玩。糖果公园的结构十分奇特,它由\(n\)个游览点构成,每个游览点都有一个糖果发放处,我们可以依次将游览点编号为\(1\)......
  • 【JS】requestIdleCallback实现分块执行
    点击按钮后,执行一个耗时较长的dom操作,页面很长时间没有响应,给用户一种卡死的现象<!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><metaname="viewport"content="width=device-width,initial-scale=1.0">&......
  • 张量矩阵乘法分块乘法概述
    张量矩阵乘法分块乘法概述介绍一下矩阵计算相关的内容,从最基本的算法,到Cutlass这些线性代数模版库,特别是Layout代数相关的内容,再逐渐细化到一些硬件实现访存优化和一些算子融合。6.3.1GEMM概述1.GEMM定义对于一个矩阵乘法,定义如下: (6-1)一个矩阵乘法定义,如图6-26......
  • 矩阵分块乘法
    矩阵分块乘法通常可以把一个矩阵分成多个块,例如, (6-4)可以将其划分为4个块:   (6-5)   (6-6)分块后的矩阵记为:(6-7)分块矩阵乘法如下所示:(6-7)划分不一定需要完全等间隔,只需要满足子矩阵乘法规则即可,如图6-27所示。图6-27子矩阵划分不一定需要完全......
  • 20240923
    Bouquet我们可以设计一个状态\(dp_i\)表示前\(i\)朵花内最多可以选多少朵花,如果第\(j\)朵花和第\(i\)多花不冲突,要满足以下条件\[r_j<i且l_i>i\]那么我们可以在\(r_j\)时再让\(j\)的转移合法,那么只用\(1\lej\ler_i\)那么带修的区间查询是什么数据结......