首页 > 其他分享 >牛可乐与魔法封印----(二分)

牛可乐与魔法封印----(二分)

时间:2024-07-25 15:27:10浏览次数:11  
标签:yi 10 xi 魔法 整数 ---- 封印 序列


 

题目描述

牛可乐得到了一个长度为 n 且非严格单调递增的序列 a,然而这个序列被 q 层魔法封印了,其中第 i 层封印的问题包含两个整数 xi,yi(xi≤yi),牛可乐必须正确回答序列中大于等于 xi且小于等于 yi​ 的数字个数才能够解开该层封印。

牛可乐觉得这个问题太难了,于是他想请你帮助他解开序列的 qqq 层封印。

输入描述:

第一行包含一个整数 n(1≤n≤10^5),表示序列的长度。

第二行包含 n 个整数,其中 −10^9≤ai≤10^9。

第三行包含一个整数 q(1≤q≤10^5),代表封印层数。

之后 q 行,每行两个整数 xi,yi(−10^9≤xi≤yi≤10^9),代表该层封印的询问。

输出描述:

对于每层封印,输出一行一个整数,代表在范围内的数字个数。

示例1

输入

5
1 2 3 4 5
3
2 6
1 5
3 3

输出

4
5
1

说明

对于第一层封印,2,3,4,5 在范围内,答案为 4。

对于第二层封印,1,2,3,4,5 在范围内,答案为 5。

对于第三层封印,3在范围内,答案为 1。

示例2

输入

5
1 1 2 3 3
3
1 1
2 3
1 3

输出

2
3
5

思路:

运用STL中的二分函数求解

AC代码:

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

int main()
{
    int n,i,x,y,q,a[1000005],ans=0;
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>a[i];
    }
    cin>>q;
    while(q--){
        cin>>x>>y;
        ans=upper_bound(a+1,a+n+1,y)-lower_bound(a+1,a+n+1,x);
        cout<<ans<<endl;
    }
    return 0;
}

标签:yi,10,xi,魔法,整数,----,封印,序列
From: https://blog.csdn.net/2302_80983064/article/details/140691213

相关文章

  • Mysql常用函数
    1、FIND_IN_SETFIND_IN_SET()是一个MySQL中的字符串函数,用于在一个由逗号分隔的字符串列表中查找指定字符串的位置。如果找到了指定的字符串,FIND_IN_SET()将返回该字符串在列表中的位置(索引值)。如果没有找到,它将返回0。其语法如下:FIND_IN_SET(str,strlist)str:......
  • CTFHUB-SQL注入-1
    对于sql注入类型的题,首先判断注入点尝试发现注入点为?id=1'发现联合注入无法回显,尝试使用sqlmap先进行扫描sqlmap-u"http://challenge-1559e706c24187fa.sandbox.ctfhub.com:10800/?id=1'" 查询dbssqlmap-u"http://challenge-1559e706c24187fa.sandbox.ctfhub.co......
  • Mybatis常用动态标签
    MyBatis动态SQL标签指南MyBatis提供了一组动态SQL处理功能,允许在运行时构建SQL语句。这非常有用,因为你可以根据不同的条件组合查询。下面是常用的动态SQL标签及其使用方法。<if>标签作用:根据表达式的结果决定是否包含某个SQL片段。属性:test属性用于设置判......
  • python cobs协议编解码算法demo
    1.SummaryCOBS(ConsistentOverheadByteStuffing)是一种算法,直译为一致的开销字节填充。简而言之,无论数据包的内容如何,都能通过产生高效可靠明确的数据包帧,从而使接受端能够从损坏的包中恢复。通常使用0x00来作为数据包的分隔符,即切割数据包的片分隔符。当使用0x00作为......
  • leetcode 1555 银行账号概要(postgresql)
    需求用户表:Users±-------------±--------+|ColumnName|Type|±-------------±--------+|user_id|int||user_name|varchar||credit|int|±-------------±--------+user_id是这个表的主键。表中的每一列包含每一个用户当前的额度信息。交易......
  • MongoDB流量分析
    MongoDB流量分析通常指的是对MongoDB数据库的网络通信量、操作频率、性能指标和资源利用情况进行监控和分析的过程。这有助于理解数据库的负载、性能、潜在的瓶颈和安全状况,以便进行优化和维护。MongoDB流量分析可以涵盖以下几个方面:网络流量监控:监控MongoDB服务器的网络带......
  • SAP-MM-供应商对账平台(功能集合)
    *&---------------------------------------------------------------------**&ReportZMMD001*&*&---------------------------------------------------------------------**&抬头:供应商对账平台**&模块:......
  • leetcode 1549 每件商品的最新订单(postgresql)
    需求表:Customers±--------------±--------+|ColumnName|Type|±--------------±--------+|customer_id|int||name|varchar|±--------------±--------+customer_id是该表主键.该表包含消费者的信息.表:Orders±--------------±--------+|......
  • SAP-PP-生产订单批量报工-2
    *&---------------------------------------------------------------------**&IncludeZPP001_FORM*&---------------------------------------------------------------------**&---------------------------------------------------------......
  • 如何将unicode编码为字节,以便可以检索到原始字符串?在Python 3.11中
    在python3.11中,我们可以对字符串进行编码,如:string.encode('ascii','backslashreplace')这对于说:hellö=>hell\\xf6但是当我插入时hellöw\\xf6rldIgethell\\xf6w\\xf6rld(注意第二个有一个看起来像字符转义序列的文字部分)......