正文

[luogup1816]忠诚（rmq||线段树）

蒟蒻zht的博客  蒟蒻zht的博客  2022-09-04  434

关键词：

传送门

其实我就是想练练 rmq

本以为学了线段树可以省点事不学 rmq 了

但是后缀数组中用 rmq 貌似很方便

所以还是学了吧，反正也不难

——代码

 1 #include <cstdio>
 2 #define N 100001
 3 #define min(x, y) ((x) < (y) ? (x) : (y))
 4 
 5 int n, m;
 6 int a[N], d[N][21];
 7 
 8 int main()
 9 {
10     int i, j, k, x, y;
11     scanf("%d %d", &n, &m);
12     for(i = 1; i <= n; i++) scanf("%d", &a[i]);
13     for(i = 1; i <= n; i++) d[i][0] = a[i];
14     for(j = 1; (1 << j) <= n; j++)
15         for(i = 1; i + (1 << j) - 1 <= n; i++)
16             d[i][j] = min(d[i][j - 1], d[i + (1 << (j - 1))][j - 1]);
17     for(i = 1; i <= m; i++)
18     {
19         scanf("%d %d", &x, &y);
20         k = 0;
21         while((1 << (k + 1)) <= y - x + 1) k++;
22         printf("%d ", min(d[x][k], d[y - (1 << k) + 1][k]));
23     }
24     return 0;
25 }

View Code

洛谷p1816忠诚

P1816忠诚569通过1.5K提交题目提供者该用户不存在标签云端难度普及+/提高时空限制1s/128MB 提交讨论题解最新讨论更多讨论主席树的常数貌似大于线段树…TLE70分怎么破样例都re竟然90震惊！史上最无... 查看详情

忠诚——洛谷——1816——rmq

知道了RMQ后，随便打打就好了。其实我是来复习RMQ的。#include<iostream>#include<cstdio>#include<cmath>usingnamespacestd;inlineintread(){intt=1,num=0;charc=getchar();while(c>‘9‘||c<‘0‘){if(c==‘-‘)t=-1;c 查看详情

线段树＋rmq问题第二弹

线段树＋RMQ问题第二弹上篇文章讲到了基于SparseTable解决RMQ问题，不知道大家还有没有印象，今天我们会从线段树的方法对RMQ问题再一次讨论。正式介绍今天解决RMQ问题的方法之前，我先对RMQ问题的概念再... 查看详情

rmq类问题利器：线段树(代码片段)

文章目录线段树一、问题引入二、线段树的构建三、线段树的单点修改与查询1、修改2、查询四、线段树的区间修改与查询1、修改2、查询五、离散化线段树六、算法练习[LeetCode307单点修改问题](https://leetcode.cn/problems/range-sum-query-... 查看详情

rmq类问题利器：线段树(代码片段)

文章目录线段树一、问题引入二、线段树的构建三、线段树的单点修改与查询1、修改2、查询四、线段树的区间修改与查询1、修改2、查询五、算法练习[LeetCode307单点修改问题](https://leetcode.cn/problems/range-sum-query-mutable/)[LeetCode732区... 查看详情

#rmq，动态开点线段树#cf803gperiodicrmqproblem(代码片段)

RMQ，动态开点线段树题目给定\$n\$个数，将这个数列复制\$k\$次得到数列\$a\$，对\$a\$满足区间赋值操作和区间最小值询问\$n\\leq10^5,q\\leq10^5,k\\leq10^4即|a|\\leq10^9\$分析先考虑线段树的区间赋值和区间最小值询问，如果没有复... 查看详情

uva11235frequentvalues线段树/rmq

　　vjudge上题目链接：UVA11235*******************************************************大白书上解释************************************************************　　题目大意：给出一个非降序排列的整数数组a1,a2,a3,...,an，你的任务是对于一系列询问(i,j)，回... 查看详情

[拆位线段树]rmq(代码片段)

[拆位线段树]RMQ题目https://ac.nowcoder.com/acm/problem/21414思路区间或，区间求和对于区间或，异或这种位运算，没法之间打懒标记。但是如果我们按位拆分，可以发现对于原数组都为01的线段树来说，或运算等效于... 查看详情

uva12299带循环移动的rmq（线段树）

...循环移动（往前移动）。分析：求区间问题，很容易想到线段树，西东就相当于单点更新。建树，有两种方案，第一种是nlogn，就是不断的更新，更新logn，有n个数。1#include<bits/stdc++.h>23usingnamespace 查看详情

洛谷——rmq

1.P1816忠诚题目描述老管家是一个聪明能干的人。他为财主工作了整整10年，财主为了让自已账目更加清楚。要求管家每天记k次账，由于管家聪明能干，因而管家总是让财主十分满意。但是由于一些人的挑拨，财主还是对管... 查看详情

pku2823slidingwindow(线段树||rmq||单调队列)

#include<cstdio>#include<algorithm>#definemaxn1000005#defineinf0x3f3f3f3fusingnamespacestd;intSegtree_min[maxn<<2],Segtree_max[maxn<<2];intn,k,value;intbegin,end;//每个结点保存该区间线段的查看详情

11-3-2017星期五

...】树状数组1;15:12洛谷P3368【模板】树状数组2;16:09洛谷P1816忠诚(线段树,st表应该会更快,可我不会);16:19CodeVS2174忠诚S(线段树);17:03POJ3321AppleTree(玄学AC...树状数组莫名其妙打对了....)17:21洛谷P1090合并果子(堆+贪心,水题);&n 查看详情

lca欧拉序+rmq(st)欧拉序+rmq(线段树)离线dfs(代码片段)

https://www.luogu.org/problemnew/show/P3379 1.欧拉序+rmq(st) 1/*2在这里，对于一个数，选择最左边的3选择任意一个都可以，[left_index,right_index]，深度都大于等于这个数的深度4*/5#include<cstdio>6#include<cstdlib>7#include< 查看详情

luogup3372模板线段树1(代码片段)

思路线段树1是一道线段树的经典模板题，所涉及的线段树基础知识也比较全面，作为线段树初学者（比如我）的练手题就非常合适。这道题想让我们完成的是对一个序列的区间修改和区间查询。关于这两个操作，我们要引入一... 查看详情

luogup3359改造异或树线段树合并(代码片段)

删边转化为加边然后每次用线段树合并就行.....确确实实很简单然而为什么线段树合并跑不过$splay$的启发式合并，常数稍大了点...复杂度$O(nlogn)$#include<vector>#include<cstdio>#include<cstring>#include<iostream>#include<algorit... 查看详情

luogup3372线段树1模板(代码片段)

线段树的模板题update区间修改，query区间求和1#include<iostream>2#include<cstdio>3#include<algorithm>4#definelllonglong5#definelsonleft,mid,rt<<16#definersonmid+1,right,rt<<1|17usingnamesp 查看详情

[luogup3960]列队（动态开点线段树）

传送门有splay的做法，有树状数组的做法。。。最好理解的还是线段树的做法。一开始我是这样想的，如果移动某一个人，只有当前行和最后一列会受到影响，感觉就像是个线段树，树状数组什么的。然而接下来就想歪... 查看详情

poj2763(lca/rmq+线段树)

题目链接:http://poj.org/problem?id=2763 题意:第一行输入n,q,s分别为树的顶点个数,询问/修改个数,初始位置.接下来n-1行形如x,y,w的输入为点x,y之间连边且边权为w.接下来q行输入,若输入形式为1xy则为将点x的权值修改为y,若输入形式为0... 查看详情