首页 > 编程语言 >分块+莫队算法

分块+莫队算法

时间:2023-04-29 15:33:26浏览次数:59  
标签:分块 int sum 算法 tag lastR 操作 莫队 block

分块

复杂度\(O(n \sqrt n)\)
主要目的是解决一些区间操作问题

把区间拆分成 \(\sqrt{n}\) 大小的块
每次碰到修改的操作,对于散块,直接暴力操作,对于整块,那么用一个 \(tag\) 进行标记即可

也就是说对于一个操作 \([l,r]\) 来说
我们需要进行操作主要分三步:

  1. 暴力操作头散块,即 \([l, k1*block-1]\),在操作的同时,处理 \([(k1-1) * block, k1 * block - 1]\) 这一整块的 \(tag\)
  2. 中间所有的整块,对 \(tag\) 进行标记
  3. 暴力操作尾散块,即 \([k2*block, r]\),在操作的同时,处理 \([k2 * block, (k2+1) * block - 1]\) 这一整块的 \(tag\)

对于查询操作来说

  1. 暴力查询头散块,即 \([l, k1*block-1]\),在操作的同时,处理 \([(k1-1) * block, k1 * block - 1]\) 这一整块的 \(tag\)
  2. 查询中间所有的整块,拿一个数组 \(sum\) 记录每一整块现在的信息
  3. 暴力查询尾散块,即 \([k2*block, r]\),在操作的同时,处理 \([k2 * block, (k2+1) * block - 1]\) 这一整块的 \(tag\)

P2357 守墓人

题目描述

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int maxn=2e5+10;
int n,m,block,op,l,r,id[maxn];
ll a[maxn],sum[1005],tag[1005],x,res=0;

void change(int l,int r,ll x){
  //1.左散块 
  for(int i=l;i<=min(id[l]*block,r);i++)
    a[i]+=x,sum[id[i]]+=x;
  if(id[l]==id[r]) return ;
  //2.中间的整块
  for(int i=id[l]+1;i<id[r];i++)
    sum[i]+=1ll*x*block,tag[i]+=x; 
  //3.右散块 
  for(int i=(id[r]-1)*block+1;i<=r;i++)
    a[i]+=x,sum[id[i]]+=x;
}

ll query(int l,int r){
  res=0;
  //1.左散块
  for(int i=l;i<=min(id[l]*block,r);i++)
    res+=a[i]+tag[id[i]];
  if(id[l]==id[r]) return res;
  //2.中间的整块
  for(int i=id[l]+1;i<id[r];i++) res+=sum[i];
  //3.右散块 
  for(int i=(id[r]-1)*block+1;i<=r;i++)
    res+=a[i]+tag[id[i]];
  return res;
}

int main(){
  /*2023.4.8 hewanying P2357 守墓人 分块*/ 
  scanf("%d%d",&n,&m);
  block=(int)floor(sqrt(n));
  for(int i=1;i<=n;i++){
  	scanf("%lld",&a[i]);
  	id[i]=(i-1)/block+1;
  	sum[id[i]]+=a[i];
  }
  for(int i=1;i<=m;i++){
  	scanf("%d",&op);
  	if(op==1){
  	  scanf("%d%d%lld",&l,&r,&x);
	  change(l,r,x);	
	}
	else if(op==2){
	  scanf("%lld",&x);
	  change(1,1,x);
	}
	else if(op==3){
	  scanf("%lld",&x);
	  change(1,1,-x);
	}
	else if(op==4){
	  scanf("%d%d",&l,&r);
	  printf("%lld\n",query(l,r));
	}
	else if(op==5){
	  printf("%lld\n",query(1,1));
	}
  }
  return 0;
} 

P.S:写代码的过程中要注意左右散块的两端

P3870 [TJOI2009] 开关

题目描述
\(tag[i]\) 用于记录 \(i\) 这整块被异或的次数
\(sum[i]\) 用于记录 \(i\) 这整块开着灯的数量
整块操作:
tag[i] ^=1, sum[i] = block - sum[i];

#include <bits/stdc++.h>
using namespace std;

const int maxn=1e5+10;
int n,m,block,op,l,r;
int sum[1005],tag[1005],a[maxn],id[maxn];

void change(int l,int r){
  //1.左散块
  for(int i=l;i<=min(r,id[l]*block);i++)
    a[i]^=1,sum[id[i]]+=(a[i]^tag[id[i]])?1:-1;
  if(id[l]==id[r]) return;
  //2.中间的整块
  for(int i=id[l]+1;i<id[r];i++)
    tag[i]^=1,sum[i]=block-sum[i];
  //3.右散块 
  for(int i=(id[r]-1)*block+1;i<=r;i++)
    a[i]^=1,sum[id[i]]+=(a[i]^tag[id[i]])?1:-1;
}

int query(int l,int r){
  int res=0;
  //1.左散块
  for(int i=l;i<=min(r,id[l]*block);i++)
    res+=(a[i]^tag[id[i]]);
  if(id[l]==id[r]) return res;
  //2.中间的整块
  for(int i=id[l]+1;i<id[r];i++)
    res+=sum[i];
  //3.右散块 
  for(int i=(id[r]-1)*block+1;i<=r;i++)
    res+=(a[i]^tag[id[i]]);
  return res;
}

int main(){
  /*2023.4.8 hewanying P3870 [TJOI2009] 开关 分块*/ 
  scanf("%d%d",&n,&m);
  block=(int)floor(sqrt(n));
  for(int i=1;i<=n;i++) id[i]=(i-1)/block+1,sum[id[i]]=0;
  for(int i=1;i<=m;i++){
  	scanf("%d%d%d",&op,&l,&r);
  	if(op==0) change(l,r);
  	else printf("%d\n",query(l,r));
  }
  return 0;
}

莫队算法

利用分块的思想,是一种对于离线区间询问问题的暴力方法

判断能否使用莫队的因素

  1. 离线区间询问
  2. \(add\) 和 \(del\) 操作的复杂度必须是 \(O(1)\)

复杂度\(O(n\sqrt{n})\)

  1. 读取所有区间进行排序(按照 \(x,y\) 所在块的 \(id\) 进行从小到大的排序)
  2. 按照排序以后的顺序,对每个区间进行求解
  3. 按照原顺序输出答案

对于上一组操作 \([L1,R1]\),下一组操作是 \([L2,R2]\) 的话

(1,100),(2,2),(3,99),(4,4)
区间位移次数:\(99+98+96\)

(2,2),(4,4),(3,99)(1,100)
区间位移次数:\(4+96+3\)

bool cmp(const Node&a, const Node&b){
	if ((a.x - 1) / block == (b.x - 1) / block) return a.y < b.y;
	return a.x < b.x;
}
void add(int x){
	vis[a[x]]++;
	if (vis[a[x] == 1){
		ans++;
	}
}
void del(int x){
	vis[a[x]]--;
	if (vis[a[x]] == 0){
		ans--;	
	}
}
int book[MAXN];
int main(){
	int lastL, lastR, L, R;
	scanf("%d%d", &n, &m);
	block = sqrt(n);
	for (int i = 1; i <= n; ++i){
		scanf("%d", &a[i]);	
	}
	for (int i = 1; i <= m; ++i){
		scanf("%d%d", &Q[i].x, &Q[i].y);
		Q[i].id = i;	
	}
	sort(Q + 1, Q + n + 1, cmp);
	int lastL = 0;
	int lastR = 0;
	for (int i = 1; i <= m; ++i){
		int L = Q[i].x;
		int R = Q[i].y;
		// add 是先挪再改
		// del 是先改再挪
		while (lastL < L) del(lastL), lastL++;
		while (lastL > L) lastL--, add(lastL);
		while (lastR < R) lastR++, add(lastR);
		while (lastR > R) del(lastR), lastR--;
		if (ans == R - L + 1){
			book[Q[i].id] = 1;
		} else {
			book[Q[i].id] = 0;
		}
	}
	for (int i = 1; i <= m; ++i){
		if (book[i])){
			printf("YES\n");	
		} else {
			printf("NO\n");	
		}
	}
	return 0;
}

标签:分块,int,sum,算法,tag,lastR,操作,莫队,block
From: https://www.cnblogs.com/hewanying0622/p/17364057.html

相关文章

  • SPFA 算法:实现原理及其应用
    一、前言SPFA算法,全称为ShortestPathFasterAlgorithm,是求解单源最短路径问题的一种常用算法,它可以处理有向图或者无向图,边权可以是正数、负数,但是不能有负环。二、SPFA算法1、SPFA算法的基本流程1.初始化首先我们需要起点s到其他顶点的距离初始化为一个很大的值(比如99......
  • 模拟退火算法
    访问【WRITE-BUG数字空间】_[内附完整源码和文档]该项目主要是利用局部搜索算法(LS)和模拟退火算法(SA)解决TSP问题。先是使用LS求解TSP问题,再尝试SA问题,比较两者,在效率上SA更占有。最后再在LS的基础上使用SA,再优化SA部分算法,尝试求解TSP问题。选用的TSP测例为eil1......
  • 三维重建原理和算法
    原理采集深度图像:使用深度相机采集场景深度信息,并将其转换为深度图像。点云生成:根据深度图像,将场景中的点云数据进行生成。点云滤波:对于采集到的点云数据进行滤波处理,去除无效数据点。点云配准:如果需要将多个点云数据融合为一个完整的点云模型,需要进行点云配准操作,使得各个点......
  • 1.ORB-SLAM3论文重点导读及整体算法流程梳理
    摘要ORB-SLAM3是第一个能够执行纯视觉、视觉-惯导以及多地图的SLAM系统,可以在单目,双目以及RGB-D相机上使用针孔以及鱼眼模型。本文主要新颖之处在于基于特征的VIO紧耦合系统,该系统完全依赖于最大后验估计,即使在IMU初始化阶段也是如此。本系统在小型和大型、室内和室外环境中实时稳......
  • jQuery轮播图(模仿滑动窗口算法)
    conststatus=["left:0px;","left:10px;","left:20px;","left:30px;","left:40px;",];constlist=$("#carousel>ul>li");constlen=lis......
  • 【数据挖掘&机器学习】招聘网站的职位招聘数据的分位数图、分位数-分位数图以及散点图
    一.本次需求背景本文主题:招聘网站的职位招聘数据的分位数图、分位数-分位数图以及散点图、使用线性回归算法拟合散点图处理详解之前的文章我们已经对爬取的数据做了清洗处理,然后又对其数据做了一个薪资数据的倾斜情况以及盒图离群点的探究。我们这次的需求是:使用散点图、使用......
  • 非对称加密算法的两种应用:签名与加密
    非对称加密的特点在于:首先:有一对私钥和公钥,其中私钥加密的东西,只能对应公钥解密。反之,公钥加密的东西,只能对应私钥解密。换种角度讲,私钥可以用来加密、用来解密(与之相对的公钥可以用来解密、用来加密)。其次:公钥可以公开传播,私钥需要私密保存。利用这两点我们可以实现加密通信......
  • VC中实现哈希Hash算法
       Hash函数我们可以自己用C来编写,但是如果在VC中就不必了,因为在VC中有实现hash算法的函数可以调用,就是CryptAcquireContext函数,这个函数的定义在wincrypt.h头文件中。下面是我在MFC中实现的,因为想要结果输出到messagebox中,所以就在视类里定义和实现了GetHash函数来计算哈希值......
  • JAVA AES 加密算法实现
    importjavax.crypto.Cipher;importjavax.crypto.spec.IvParameterSpec;importjavax.crypto.spec.SecretKeySpec;importjava.nio.charset.StandardCharsets;importjava.util.Base64;publicclassAESUtil{privatestaticfinalStringDEFAULT_KEY="hj7x......
  • 二分查找算法讲解及其C++代码实现
    二分查找算法是一种常用的查找算法,也被称为折半查找。它可以在有序的数组或列表中快速查找需要的元素。算法描述:首先确定数组的中间位置mid=(left+right)/2;然后将要查找的值key与中间位置的值进行比较;如果key等于中间位置的值,则查找成功,返回mid;如果key小于中间位置的值,则在......