当前位置： 首页 > 编程日记 > 正文

洛谷 P1816 忠诚

编程日记 2024-09-14 15:30:00

题目描述

老管家是一个聪明能干的人。他为财主工作了整整10年，财主为了让自已账目更加清楚。要求管家每天记k次账，由于管家聪明能干，因而管家总是让财主十分满意。但是由于一些人的挑拨，财主还是对管家产生了怀疑。于是他决定用一种特别的方法来判断管家的忠诚，他把每次的账目按1，2，3…编号，然后不定时的问管家问题，问题是这样的：在a到b号账中最少的一笔是多少？为了让管家没时间作假他总是一次问多个问题。

输入输出格式

输入格式：

输入中第一行有两个数m,n表示有m(m<=100000)笔账,n表示有n个问题，n<=100000。

第二行为m个数,分别是账目的钱数

后面n行分别是n个问题,每行有2个数字说明开始结束的账目编号。

输出格式：

输出文件中为每个问题的答案。具体查看样例。

输入输出样例

输入样例#1： 
10 3
1 2 3 4 5 6 7 8 9 10
2 7
3 9
1 10
输出样例#1： 
2 3 1

感慨

又一年的CTSC&APIO结束了，这周我就参加了第三次市统测，其他没啥事。听说今年CCF出了不小的问题啊#滑稽（知乎，如何评价CTSC/APIO 2018）。

能力退化太多了……这道简单到不能再简单的线段树，甚至连修改、lazy都没有，我写、调了差不多2h……其他解法，我完全写不来了……

解题思路

一串序列，询问区间最小值，裸的RMQ。我想到的可以用线段树、树状数组、zkw线段树、ST表/DP/倍增(都指一个东西，有人把这叫RMQ，其实是错的)、单调队列、莫队、分块、整体二分，或者乱搞(雾)——先按钱数快排一下(可以加个离散化)，每次询问时，从小到大扫一遍，看看哪个的序号在区间内，那答案就是它。百度上还提到一种RMQ标准算法——

————————————分割线————————————

RMQ标准算法：先规约成LCA（Lowest Common Ancestor），再规约成约束RMQ，O(n)-O(q) online。
首先根据原数列，建立笛卡尔树，从而将问题在线性时间内规约为LCA问题。LCA问题可以在线性时间内规约为约束RMQ，也就是数列中任意两个相邻的数的差都是+1或-1的RMQ问题。约束RMQ有O(n)-O(1)的在线解法，故整个算法的时间复杂度为O(n)-O(1)。
————————————分割线————————————
不明觉厉……

下面的代码是线段树的。

//一定一定要小心#define的危险性——[JSOI2008]最大数

源代码

#include<cstdio>inline int MIN(int a,int b)
{return a<b?a:b;
}int n,m;
int a[100010]={0};struct s_tree
{int l,r,min;
}s[500010];#define skl s[k].l
#define skr s[k].r
#define skm s[k].min
int maketree(int k,int l,int r)
{skl=l;skr=r;if(l==r){skm=a[l];return a[l];}int mid=l+r>>1;skm=MIN(maketree(k<<1,l,mid),maketree(k<<1|1,mid+1,r));return skm;
}int ask(int k,int l,int r)
{if(skl>r||skr<l||r<l) return 0x7fffffff;if(l<=skl&&skr<=r) return skm;return MIN(ask(k<<1,l,r),ask(k<<1|1,l,r));
}int main()
{scanf("%d%d",&m,&n);for(int i=1;i<=m;i++)scanf("%d",a+i);maketree(1,1,m);while(n--){int ll,rr;scanf("%d%d",&ll,&rr);printf("%d ",ask(1,ll,rr));}return 0;
}


https://www.dkcj.cn/info/18706.html

相关文章：

电子学会青少年编程等级考试Python案例08

「青少年编程竞赛交流群」已成立&#xff08;适合6至18周岁的青少年&#xff09;&#xff0c;公众号后台回复【Scratch】或【Python】&#xff0c;即可进入。如果加入了之前的社群不需要重复加入。 案例&#xff1a;绘制兔子时钟 代码 import turtlet turtle.Pen()# 表盘 t.p…

编程日记2024/09/14 15:20:00

Python组合数据类型之序列类型

单元概述 主要解决问题&#xff1a;让程序更好地处理一组数据 三类重要组合数据类型&#xff1a;集合类型、序列类型和字典类型 学完本章&#xff0c;我们能够在头脑中建立集合、序列和字典的模式来表达对一组数据的表达和处理 1. 定义 序列是具有先后关系的一组元素 -序列是…

编程日记2024/09/14 15:10:00

hdu-3071 Gcd Lcm game---质因数分解+状态压缩+线段树

题目链接&#xff1a; http://acm.hdu.edu.cn/showproblem.php?pid3071 题目大意&#xff1a; 给定一个长度为n的序列m次操作&#xff0c;操作的种类一共有三种 查询 L :查询一个区间的所有的数的最小公倍数modpG :查询一个区间的所有的数的最大公约数modp修改 C :将给定位置…

编程日记2024/09/14 15:00:00

一个比较保守的404页面

<HTML><HEAD><TITLE>您访问的页面不存在 请转到首页进入</TITLE> <META http-equivContent-Type content"text/html; charsetGB2312"> <META http-equivrefresh content"5;URL /"> <STYLE typetext/css></S…

编程日记2024/09/14 14:50:00

【组队学习】【34期】组队学习内容详情

第34期 Datawhale 组队学习活动马上就要开始啦&#xff01; 02月09日&#xff08;星期三&#xff09;&#xff0c;宣发&#xff0c;2月组队学习计划&#xff01;。02月12日&#xff08;星期六&#xff09;&#xff0c;进入学习群、开营仪式。 本次组队学习的内容为&#xff1a…

编程日记2024/09/14 14:40:00

Python组合数据类型之字典类型

单元概述 主要解决问题&#xff1a;让程序更好地处理一组数据 三类重要组合数据类型&#xff1a;集合类型、序列类型和字典类型 学完本章&#xff0c;我们能够在头脑中建立集合、序列和字典的模式来表达对一组数据的表达和处理 1. 定义 首先理解“映射”的概念 -映射是一种键…

编程日记2024/09/14 14:30:00

maven 插件：Tomcat7

配置 Tocmat 用户 > vim $TOMCAT_PATH%/conf/tomcat-users.xml <tomcat-users><role rolename"manager-gui"/><role rolename"manager-script"/><user username"tomcat" password"linuxmint" roles"mana…

编程日记2024/09/14 14:20:00

电子学会 软件编程（图形化）二级训练营

电子学会 软件编程&#xff08;图形化&#xff09;二级训练营 试题来源 青少年软件编程&#xff08;Scratch&#xff09;等级考试试卷&#xff08;二级&#xff09;【2019.09】青少年软件编程&#xff08;Scratch&#xff09;等级考试试卷&#xff08;二级&#xff09;【2019…

编程日记2024/09/14 14:10:00

MacOS无法登录App Store修复

MacOS无法登录App Store修复 2017-03-10 21:13:39 by&#xff1a;SemiconductorKING 先上图&#xff1a; 惨红色的提示信息&#xff0c;把你拒之App Store门外&#xff0c;但是对之放弃、不与之斗争不是我们的节奏&#xff0c;请看破敌攻略&#xff1a; 1.查看你的“关于本机”…

编程日记2024/09/14 14:00:00

Python文件的使用

本章导言 什么是数据格式化 前言&#xff1a; -学完本章&#xff0c;看待数据会有一种规范/格式化的视角 -方法论:从Python角度理解文件和数据表示 -实践能力:学会编写带有文件输入输出的程序 1. 文件的使用 文件的类型 -文件是数据的抽象和集合&#xff0c;可理解为存储在…

编程日记2024/09/14 13:50:00

datagridview 点击列标题排序

开发winform中&#xff0c;平时经常用到数据列表&#xff0c;我们大多选用datagridview&#xff0c;但是此控件本身没有排序的功能。参阅网上资料。留下标记&#xff0c;以后备用。 datagridview的数据显示一般是通过数据绑定来实现&#xff0c; 即&#xff1a;this.datagridvi…

编程日记2024/09/14 13:40:00

围绕圆心形旋转

2019独角兽企业重金招聘Python工程师标准>>> 实现了围绕圆心旋转功能 using System.Collections; using System.Collections.Generic; using UnityEngine;public class Roation : MonoBehaviour {public float range 10;void Update () {float x Mathf.Sin(Mathf.…

编程日记2024/09/14 13:30:00

【组队学习】【34期】阿里云天池在线编程训练营

阿里云天池在线编程训练营 航路开辟者&#xff1a;陈信达、杨世超、赵子一、马燕鹏领航员&#xff1a;武帅、初晓宇、叶前坤、邱广坤、朱松青航海士&#xff1a;宁彦吉、肖桐、汪超、陈信达、杨世超、赵子一、武帅、初晓宇、叶前坤、邱广坤、朱松青、马燕鹏 基本信息 学习平…

编程日记2024/09/14 13:20:00

Python一维二维数据的格式化和处理

本章导言 什么是数据格式化 前言&#xff1a; -学完本章&#xff0c;看待数据会有一种规范/格式化的视角 -方法论:从Python角度理解文件和数据表示 -实践能力:学会编写带有文件输入输出的程序 1. 数据组织的维度 维度&#xff1a;一组数据的组织形式-线性还是二维或更高维…

编程日记2024/09/14 13:10:00

让你的网站提速：图片优化网站推荐

页面的加载时间是每一个设计师都担心的数据&#xff0c;或者至少是每个设计师都应该担心的问题。图片的大小肯定是一个需要留意的问题。这就是为什么在这里写了几个有助于优化页面中的图片的小技巧&#xff0c;这些小技巧将有助于大家解决这个问题&#xff0c;这些小技巧也可以…

编程日记2024/09/14 13:00:00

JAVA对图片的任意角度旋转，以及镜像操作

package relevantTest;/* * 该代码实现了对图像的水平镜像变换&#xff0c;垂直镜像变换&#xff0c;任意角度旋转&#xff0c;jtf的实时监控&#xff0c;以及对图像的缩放变换&#xff0c;以及按钮的若隐若现效果。 * 在对图像进行任意角度旋转时最好是在原始图片未进行任何操…

编程日记2024/09/14 12:50:00

【组队学习】【34期】百度飞桨AI达人创造营

百度飞桨AI达人创造营 航路开辟者&#xff1a;百度飞桨领航员&#xff1a;六一航海士&#xff1a;阿水、颜鑫、宋泽山、刘洋、张文恺 基本信息 内容属性&#xff1a;合作课程练习平台&#xff1a;https://aistudio.baidu.com/aistudio/course/introduce/25259?ad-frompdg-1…

编程日记2024/09/14 12:40:00

安装Python第三方库的三个方法

方法一: (cmd命令行) pip 方法【主要方法&#xff0c;适用于99%的情况】【依赖网络状况】 在命令行输入pip -h 可查看该命令帮助信息 常用pip命令 ① pip install <第三方库名> 安装指定第三方库 参数 -U :update对已经安装的进行版本更新 ② pip uninstall <第三方…

编程日记2024/09/14 12:30:00

java 基础---继承

继承 一&#xff0c;概述 a) 使用extends关键字可以让一个类继承另一个类&#xff0c;继承的类为子类&#xff0c;被继承的类是父类&#xff0c;子类会自动继承父类的所有方法和属性。 b) 继承使得类和类之间产生了关系 c) 子类可以使用super调用父类成员…

编程日记2024/09/14 12:20:00

建立CentOS 6.9 的Yum本地源

1、建立一个本地Yum的软件仓库1mkdir /media/cdrom2、把CentOS6.9光盘装载到/media/cdrom1mount /dev/cdrom /media/cdrom3、安装createrepo1 rpm -ivh /media/cdrom/Packages/createrepo-[按tab键] deltarpm-[按tab键] python-deltarpm-[按tab键] createrepo-0.9.9-26.…

编程日记2024/09/14 12:10:00

【组队学习】【34期】零基础学python编程思维

零基础学python编程思维 航路开辟者&#xff1a;邓林权领航员&#xff1a;沈一航海士&#xff1a;覃嘉俊、马子阳、左凯文 基本信息 开源内容&#xff1a;https://linklearner.com/datawhale-homepage/index.html#/learn/detail/6内容属性&#xff1a;公测课程内容说明&…

编程日记2024/09/14 12:00:00

Python wordcloud库使用说明

1. 介绍 wordcloud是优秀的词云展示第三方库 -词云以词语为基本单位&#xff0c;更加直观和艺术地展示文本 通过词云&#xff0c;我们可以快速提取大段文本的重要信息 2. 安装 (cmd命令行) pip install wordcloud 3. 使用 w wordcloud.WordCloud()代表一个文本对应的词云…

编程日记2024/09/14 11:50:00

resin-pro-4.0.34 服務器在windows环境下的配置

resin-pro-4.0.34 服務器在windows环境下的配置(轉載请注明作者:icelong) 到caucho網站上http://www.caucho.com/download/下載resin-pro-4.0.34 Windows下載zip版&#xff0c;Linux下載tgz版 Install JDK 1.4 or later. On Unix, set the JAVA_HOME variable or link /usr/jav…

编程日记2024/09/14 11:40:00

【组队学习】【34期】Python（一级）

Python&#xff08;一级&#xff09; 航路开辟者&#xff1a;王思齐、马燕鹏领航员&#xff1a;马燕鹏航海士&#xff1a;马燕鹏 基本信息 开源内容&#xff1a;https://github.com/datawhalechina/team-learning-program/tree/master/PythonTest内容属性&#xff1a;公测课…

编程日记2024/09/14 11:30:00

matlab处理txt文件数据

read_txtfile.,m clear close all clc %load函数一般将用来导入纯数字的文件&#xff0c;可以是文本格式的文件或者是matlab保存的mat格式的文件 positionload(坐标点.txt); %将.txt数据读入到matlab工作空间[m,n]size(position); %获得数据矩阵的大小 j1; sumx0; sumy0; …

编程日记2024/09/14 11:20:00

Python os库的使用

1. 基本介绍 os提供通用的、基本的操作系统交互功能 os库是Python的标准库&#xff0c;提供几百个处理函数 常用有路径操作、进程管理、环境参数等几类 路径操作&#xff1a;os.path子库&#xff0c;处理文件路径及信息 进程管理&#xff1a;启动系统中其他程序 环境参数&…

编程日记2024/09/14 11:10:00

(U3D)Time的使用

Time类包含了一个重要的类变量deltaTime&#xff0c;它表示距上一次调用Update或FixedUpdate所用的时间。 因此通过它可以让游戏对象按照一个常速进行旋转&#xff0c;而不是依赖于它的帧频&#xff1a; function Update() { tranform.Rotate(0, 5 * Time.deltaTime, 0); } …

编程日记2024/09/14 11:00:00

【组队学习】【34期】Scratch（二级）

Scratch&#xff08;二级&#xff09; 航路开辟者&#xff1a;王思齐、马燕鹏领航员&#xff1a;马燕鹏航海士&#xff1a;马燕鹏 基本信息 开源内容&#xff1a;https://github.com/datawhalechina/team-learning-program/tree/master/Scratch内容属性&#xff1a;公测课程…

编程日记2024/09/14 10:50:00

文件操作示例脚本 tcl

linux 下&#xff0c;经常会对用到文件操作&#xff0c;下面是一个用 tcl 写的文件操作示例脚本&#xff1a; 其中 set f01 [open "fix.tcl" w] 命令表示 打开或者新建一个文件“fix.tcl”&#xff0c;并将其 file ID 设置为 f01&#xff0c;后续就以这个 file ID 来…

编程日记2024/09/14 10:40:00

Python 第三方库自动安装脚本

需求&#xff1a;批量安装第三方库需要人工干预&#xff0c;能否自动安装&#xff1f; 现假设我们要安装以下库 #BatchInstall.py import os libs {"numpy","matplotlib","pillow","sklearn","requests",\ "jie…

编程日记2024/09/14 10:30:00