首页 > 其他分享 >RMQ问题

RMQ问题

时间:2023-03-31 09:00:10浏览次数:38  
标签:10 RMQ int 2e6 问题 logn include

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

//这里要开2e6 + 10因为我们用到了Ai当下表,Ai是1 << 20 > 1e6 + 10,在这被卡了好久
const int N = 2e6 + 10;
int last[N], g[N], a[N];
int f[N][30], logn[N];
int n, m, x;
void prework()
{
    logn[1] = 0;
    //预处理出来log方便后来直接查表
    for(int i = 2; i <= n; ++ i)    logn[i] = logn[i / 2] + 1;
    //初始化递推条件,即从第i个元素开始长度为1的区间内的最大值就是这个数本身
    for(int i = 1; i <= n; ++ i)    f[i][0] = g[i];
    //长度为一个已经初始化过了,直接从长度为2的地方开始递推

    for(int j = 1; j <= 20; ++ j)
        for(int i = 1; i + (1 << j) - 1 <= n; ++ i)
        {
            // cout << i << ' ' << j << ' ' << f[i][j] << endl;
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);

        }
}

//查询操作,查询区间l,r的最大值
int query(int l, int r)
{
    int k = logn[r - l + 1];
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}
int main()
{
    cin >> n >> m >> x;
    for(int i = 1; i <= n; ++ i) scanf("%d", &a[i]);
    //从前往后找到每个数和他配对并且离他最近的那个数的下表
    for(int i = 1; i <= n; ++ i)
    {
        g[i] = last[x ^ a[i]];
        last[a[i]] = i;
    }
    prework();
    while(m --)
    {
        int l ,r;
        scanf("%d%d",&l, &r);
        if(query(l, r) < l) puts("no");
        else    puts("yes");
    }
    return 0;
}

标签:10,RMQ,int,2e6,问题,logn,include
From: https://www.cnblogs.com/cxy8/p/17275097.html

相关文章

  • vue3+vite+ts 配置@时vscode报找不到__dirname的问题
    vue3+vite+ts配置@时vscode报找不到__dirname的问题-CSDN博客  原因:path模块是node.js的内置模块,而node.js默认不支持ts文件的解决:安装@type/node依赖包 npminstall@types/node--save-dev......
  • 四个常见的Linux面试问题。
    刚毕业要找工作了,只要是你找工作就会有面试这个环节,那么在面试环节中,有哪些注意事项值得我的关注呢?特别是专业技术岗位,这样的岗位询问一般都是在职的工程师,如何在面试环节更好地理解面试官的问题,我们一起往下看吧。在学校学习也好,在培训机构或者网络在线学习也好,无论是通过那种途径......
  • 四个常见的Linux面试问题。
    刚毕业要找工作了,只要是你找工作就会有面试这个环节,那么在面试环节中,有哪些注意事项值得我的关注呢?特别是专业技术岗位,这样的岗位询问一般都是在职的工程师,如何在面试环节更好地理解面试官的问题,我们一起往下看吧。在学校学习也好,在培训机构或者网络在线学习也好,无论是通过那种途径......
  • 经典图论遍历问题:传递信息
    小朋友A在和ta的小伙伴们玩传信息游戏,游戏规则如下:有n名玩家,所有玩家编号分别为0~n-1,其中小朋友A的编号为0每个玩家都有固定的若干个可传信息的其他玩家(也可能没有)。传信息的关系是单向的(比如A可以向B传信息,但B不能向A传信息)。每轮信息必须需要传递给另一......
  • P2774 方格取数问题
    有一个m行n列的方格图,每个方格中都有一个正整数。现要从方格中取数,使任意两个数所在方格没有公共边,且取出的数的总和最大,请求出最大的和。  相邻格子连边,形成一个二分图,现在要删去一些边(边权和最小),使得S-T不连通,即最小割 SUM-最小割  #include<iostream>......
  • 基本背包问题复习(01背包,完全背包,多重背包,分组背包)
    背包问题,本质上就是给几种物品,每个物品有体积有价值,可能有个数限制有一个容量有限的背包,在背包能装下的前提下,能装的最大价值是多少 背包问题一般分为这几种:01背包:每件物品只有一个完全背包:每件物品有无限个多重背包:每件物品有Si个(有限个)分组背包:所有物品被分为多个组,每一组......
  • 5 个最常见的 Linux故障问题
    导读了解如何解决 Linux 桌面用户遇到的最常见的问题尽管绝大多数用户如预期地成功安装和操作了Linux,但不可避免地仍会有一些用户遇到问题。作为今年任务队列里的最后一篇文章,我认为在即将进入2016年时,总结一下人们所遇到的最常见的技术性的Linux问题会很有趣。我把这......
  • Beego查数据库数据panic问题
    一开始没发现问题所在,请了位大佬帮忙排查错误逐步确定问题所在。问题起源于我查数据库没有得到正确的数据开始。一开始发现是数据类型问题,改过之后还是存在问题,于是debug一下,一步一步看问题出在哪里,结果走进了锁,就没仔细看,哪知在这中间出现了一个panic问题。但是这个panic没有打......
  • 缓存行与伪共享问题
    局部性原理时间局部性:如果数据正在被访问,那么在近期它很可能还会被再次访问。比如循环、方法的反复调用等。空间局部性:如果存储器的位置被引用,那么将来他附近的位置也会被引用。比如顺序结构、数组。CPU缓存执行程序是靠CPU执行主存中代码,但是CPU和主存的速度差异是非常大的,为......
  • 视频融合平台EasyCVR设备录像因时间导致播放异常问题的排查与解决
    EasyCVR视频融合平台可提供丰富的视频能力,支持视频直播、录像、回放、检索、云存储、告警上报、语音对讲、集群、电子地图、智能分析以及平台级联等。平台可支持多协议、多类型设备接入,包括国标GB28181、RTMP、RTSP/Onvif、海康SDK、大华SDK、海康Ehome等,近期我们又拓展了更多SDK......