首页 > 其他分享 >[LOJ6698] 一键挖矿

[LOJ6698] 一键挖矿

时间:2023-10-26 21:00:13浏览次数:41  
标签:int 挖矿 一键 long ren vv include ql LOJ6698

一键挖矿
弱化版(?):CF562F
将矩阵扩展一个单位(长宽均加1),把当前存在的格子染色。
可以发现当且仅当恰好存在4个有1个格子被染色,不存在有3个格子被染色的2x2矩阵时满足题意。
枚举右端点 r,设 g(l) 表示选择 [l,r] 时有多少个上述矩阵。
可以发现 g(r)=4,且对于 x\(\in\)[l,r],g(x)$\geq$4。
也就是我们维护区间最小值和其个数,判断值是否为4即可。
新增1个 r 会影响其周围4个2x2的矩阵,考虑 r 的贡献,这个根据它在某个矩阵中的大小位置判断。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<bitset>
using namespace std;
#define db double
#define ll long long
#define ull unsigned long long
#define ld long double
#define ls p<<1
#define rs p<<1|1
const int MAXN=5e5+5;
const int INF=0x3f3f3f3f;
void read(int &x){
	x=0;int f=1;char s=getchar();
	while(s<'0'||s>'9'){
		if(s=='-') f=-1;s=getchar();
	}
	while(s>='0'&&s<='9'){
		x=(x<<3)+(x<<1)+(s^48);s=getchar();
	}
	x*=f;
}
int n,m,ta[MAXN<<2],up,wz[MAXN][2];
vector<vector<int> >va;
ll Ans;
struct ren{
	int mi,con;
	ren(){};
	ren(int M,int C){mi=M;con=C;}
}t[MAXN<<2];	
ren operator+(ren a,ren b){
	if(a.mi<b.mi) return a;
	if(b.mi<a.mi) return b;
	return (ren){a.mi,a.con+b.con};
}
void pup(int p){t[p]=t[ls]+t[rs];}
void pdo(int p){
	if(ta[p]==0) return;
	t[ls].mi+=ta[p];t[rs].mi+=ta[p];
	ta[ls]+=ta[p];ta[rs]+=ta[p];
	ta[p]=0;return;
}
void bui(int p,int l,int r){
	t[p]=(ren){0,r-l+1};
	if(l==r) return;
	int mid=(l+r)>>1;
	bui(ls,l,mid);bui(rs,mid+1,r);
}
void modi(int p,int l,int r,int ql,int qr,int x){
	if(l>=ql&&r<=qr){
		ta[p]+=x;t[p].mi+=x;return;
	}
	pdo(p);
	int mid=(l+r)>>1;
	if(ql<=mid) modi(ls,l,mid,ql,qr,x);
	if(qr>mid) modi(rs,mid+1,r,ql,qr,x);
	pup(p);
}
ren que(int p,int l,int r,int ql,int qr){
	if(l>=ql&&r<=qr) return t[p];
	pdo(p);
	int mid=(l+r)>>1;ren tmp=(ren){INF,0};
	if(ql<=mid) tmp=tmp+que(ls,l,mid,ql,qr);
	if(qr>mid) tmp=tmp+que(rs,mid+1,r,ql,qr);
	return tmp;
}
void calc(int x,int y,int z,int zz){
	vector<int> vv;vv.push_back(x);vv.push_back(y);vv.push_back(z);vv.push_back(zz);
	int wz=0;
	sort(vv.begin(),vv.end());
	for(int i=0;i<4;i++){
		if(vv[i]==x){
			wz=i;break;
		}
	}
	for(int i=0;i<4;i++){
		int op=(wz-i+1)&1;
		if(op&1){
			if(i==0) modi(1,1,up,1,vv[i],1);
			else modi(1,1,up,vv[i-1]+1,vv[i],1);
		}
		else{
			if(i==0) modi(1,1,up,1,vv[i],-1);
			else modi(1,1,up,vv[i-1]+1,vv[i],-1);
		}
		if(i==wz) break;
	}
}
int main(){
	read(n);read(m);up=n*m;
	va.resize(n+5);	
	for(int i=0;i<=n+1;i++){
		va[i].resize(m+5);
		for(int j=0;j<=m+1;j++){
			if(i==0||i==n+1||j==0||j==m+1){
				va[i][j]=up+1;continue;
			}
			read(va[i][j]);wz[va[i][j]][0]=i;wz[va[i][j]][1]=j;
		}
	}
	bui(1,1,up);
	for(int i=1;i<=up;i++){
		int x=wz[i][0],y=wz[i][1];
		calc(va[x][y],va[x-1][y],va[x-1][y-1],va[x][y-1]);
		calc(va[x][y],va[x][y+1],va[x-1][y],va[x-1][y+1]);
		calc(va[x][y],va[x][y-1],va[x+1][y-1],va[x+1][y]);
		calc(va[x][y],va[x][y+1],va[x+1][y],va[x+1][y+1]);
		ren op=que(1,1,up,1,i);
		if(op.mi==4) Ans+=op.con;
	}
	printf("%lld",Ans);return 0;
}

标签:int,挖矿,一键,long,ren,vv,include,ql,LOJ6698
From: https://www.cnblogs.com/StranGePants/p/17790343.html

相关文章

  • SPSS 25 汉化版下载「IBM spss statistics」中文一键安装
    SPSS是一款非常专业的数据统计分析软件。它的功能十分强大,集数据录入、资料编辑、数据管理、统计分析、报表制作、图形绘制为一体,提供描述性统计、数据准备、绘图、二元统计过程、因子和聚类分析以及线性和顺序回归等实用功能。软件地址:看置顶贴软件特点:1、操作简单它的界面很友好,......
  • 一键解决WARNING: This is a development server. Do not use it in a production dep
    WARNING:Thisisadevelopmentserver.Donotuseitinaproductiondeployment.UseaproductionWSGIserverinstead.文章目录问题描述解决思路解决方法问题描述WARNING:Thisisadevelopmentserver.Donotuseitinaproductiondeployment.UseaproductionWS......
  • 一键解决json.decoder.JSONDecodeError: Expecting value: line 1 column 1 (char 0)
    json.decoder.JSONDecodeError:Expectingvalue:line1column1(char0)文章目录问题描述解决思路解决方法问题描述json.decoder.JSONDecodeError:Expectingvalue:line1column1(char0)解决思路JSONDecodeError是指在使用json.loads()方法时,解析JSONJSONDecodeError是......
  • 一键解决TypeError: Descriptors cannot not be created directly.
    TypeError:Descriptorscannotnotbecreateddirectly.文章目录问题描述解决思路解决方法问题描述TypeError:Descriptorscannotnotbecreateddirectly.解决思路这个错误提示是关于Protobuf的,可能是因为你的代码中使用了过时的Protobuf版本导致的。下滑查看解决方法解......
  • 一键解决[notice] A new release of pip available: 22.2 -> 22.2.2 [notice] To updat
    [notice]Anewreleaseofpipavailable:22.2->22.2.2[notice]Toupdate,run:python.exe-mpipinstall--upgradepip文章目录问题描述解决思路解决方法问题描述[notice]Anewreleaseofpipavailable:22.2->22.2.2[notice]Toupdate,run:python.exe-mpip......
  • Adobe InDesign CC2021 for Mac「ID」汉化版 一键安装 永久使用
    AdobeInDesign2021中文直装版是专业的版面设计和桌面出版软件,使用旨在为用户提供设计、预检、发布等一体化的功能,为宣传册、海报以及其他印刷或数字媒体制作完美的布局。软件地址:看置顶贴AdobeInDesign2021Mac版的软件亮点:1、设计任何材料:信笺,传单,海报,小册子,年度报告,杂志和书......
  • 如何一键私有化部署 Laf ?
    太长不看:Laf上架了Sealos的模板市场,通过Laf应用模板即可一键部署!Laf是一个完全开源的项目,除了使用公有云之外,还有大量的用户选择私有化部署Laf。然而,私有化部署通常伴随着更多的复杂性和门槛。例如,用户首先需要准备一台或多台服务器,然后在服务器上下载Laf的镜像,进行域......
  • 如何使用 GoGoCode 一键 Vue2 转换 Vue3
    前言从今年年初开始,项目开始升级优化,将之前的Vue2旧版本整体升级到Vue3版本。在重写了几个Vue文件后,我发现做的都是一些机械性的工作,效率低且重复性大。于是就试着搜索了一下有没有什么能够批量转换代码格式的工具,发现了阿里的这个基于AST的JavaScript/Typescript/HTML......
  • 使用Chocolatey包管理器一键搭建windows开发环境
    最近腾讯开放内测的微信小程序火了,而官方支持IDE只有windows版和Mac版的,稍微研究了一下这个IDE发现是node-webkit开发的,理论上应该是跨平台的,但不知为何这个IDE并没有支持Linux环境。喜欢折腾的我当然是要尝试一下的,奈何是使用Ubuntu作为主力开发环境,所以只能重做一个windows系统了......
  • PyTorch大更新,编译代码速度暴增35倍!视觉模型一键部署,头显Quest 3可用
    前言 最近,在Pytorch发布会上,发布移动端Pytorch解决方案ExecuTorch,实现在移动端设备上大范围地部署AI工具,并推出最新版本Pytorch2.1,推理速度大幅提升。本文转载自新智元仅用于学术分享,若侵权请联系删除欢迎关注公众号CV技术指南,专注于计算机视觉的技术总结、最新技术跟踪、经典......