博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
蓝桥杯 算法提高 上帝造题五分钟(线段树)
阅读量:4139 次
发布时间:2019-05-25

本文共 1361 字,大约阅读时间需要 4 分钟。

算法提高 上帝造题五分钟  
时间限制:1.0s   内存限制:256.0MB
    
问题描述
  第一分钟,上帝说:要有题。于是就有了L,Y,M,C

  第二分钟,LYC说:要有向量。于是就有了长度为n写满随机整数的向量

  第三分钟,YUHCH说:要有查询。于是就有了Q个查询,查询向量的一段区间内元素的最小值

  第四分钟,MZC说:要有限。于是就有了数据范围

  第五分钟,CS说:要有做题的。说完众神一哄而散,留你来收拾此题
输入格式
  第一行两个正整数n和Q,表示向量长度和查询个数

  接下来一行n个整数,依次对应向量中元素:a[0],a[1],…,a[n-1]

  接下来Q行,每行两个正整数lo,hi,表示查询区间[lo, hi]中的最小值,即min(a[lo],a[lo+1],…,a[hi])。
输出格式
  共Q行,依次对应每个查询的结果,即向量在对应查询区间中的最小值。
样例输入
7 4

1 -1 -4 8 1 2 -7

0 0

1 3

4 5

0 6
样例输出
1

-4

1

-7
样例说明
  第一个查询[0,0]表示求min{a[0]}=min{1}=1

  第二个查询[1,3]表示求min{a[1],a[2],a[3]}=min{-1,-4,8}=-4

  第三个查询[4,5]表示求min{a[4],a[5]}=min{1,2}=1

  第四个查询[0,6]表示查询整个向量,求min{a[0..6]}=min{1,-1,-4,8,1,2,-7}=-7
数据规模和约定
  1<=n<=1984,1<=Q<=1988,向量中随机整数的绝对值不超过1,000
#include 
#include
using namespace std;const int N=2000;struct Node{ int l,r,v;}node[N*4];void InitTree(int now,int l,int r){ if(l==r){ cin>>node[now].v; node[now].l=l; node[now].r=l; return; } int mid=(l+r)/2; int ne=now<<1; InitTree(ne,l,mid); InitTree(ne+1,mid+1,r); node[now].l=l; node[now].r=r; node[now].v=min(node[ne].v,node[ne+1].v);}int find(int now,int l,int r){ if(node[now].l==l&&node[now].r==r) return node[now].v; int mid=(node[now].l+node[now].r)/2; int ne=now<<1; if(mid>=r){ return find(ne,l,r); } else if(mid
>n>>q){ InitTree(1,1,n); for(int i=0;i
>l>>r; cout<
<

转载地址:http://fbmvi.baihongyu.com/

你可能感兴趣的文章
apache和tomcat整合
查看>>
java虚拟机错误问题
查看>>
oracle建立表空间
查看>>
oracle分区表的性能提升
查看>>
"Cannot allocate memory" OutofMemory when call Ant to build Polish project in Tomcat
查看>>
dumpcap抓包(python)
查看>>
查看文件是否被其他进程访问
查看>>
字符编码详解
查看>>
python使用dpkt分析wireshak报文(Modbus规约)
查看>>
css中的IFC
查看>>
CentOS 6.5下 mysql用户root登录不了
查看>>
windows + tomcat 部署web服务 http 改为https访问方法
查看>>
Windows系统下Apache 服务器启动以及过程中产生问题的解决办法
查看>>
Oracle服务说明
查看>>
异常收集(三):Missing artifact com.oracle:ojdbc6:jar:1.0 两种解决方案
查看>>
异常收集(四):Plugin execution not covered by lifecycle configuration
查看>>
异常收集(五):Io 异常: The Network Adapter could not establish the connection
查看>>
JSP中的转义字符
查看>>
SQLException: The user specified as a definer ('root'@'%') does not exist
查看>>
Linux 操作指令收集
查看>>