关键词:
题目链接:https://vjudge.net/contest/147973#problem/C
题意:传统的RMQ是一个不变的数组a求区间最值。现在要循环移动(往前移动)。
分析:求区间问题,很容易想到线段树,西东就相当于单点更新。
建树,有两种方案,第一种是nlogn,就是不断的更新,更新logn,有n个数。
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 6 const int INF = 1000000000; 7 const int maxnode = 1<<18; 8 9 int op, qL, qR, p, v; //qL,qR询问区间,p修改点,v修改值 10 11 struct IntervalTree 12 { 13 int minv[maxnode]; 14 15 //修改:A[p] = v; 16 void update (int o,int L,int R) 17 { 18 int M = L + (R-L)/2; 19 if(L==R) minv[o] = v; 20 else 21 { 22 if(p<=M) update(o*2,L,M); 23 else update(o*2+1,M+1,R); 24 minv[o] = min(minv[o*2],minv[o*2+1]); 25 } 26 } 27 28 //询问[ql,qr]中的最小值 29 int query(int o,int L,int R) 30 { 31 int M = L+(R-L)/2,ans = INF; 32 if(qL<=L&&R<=qR) return minv[o]; 33 if(qL<=M) ans = min(ans,query(o*2,L,M)); 34 if(M<qR) ans = min(ans,query(o*2+1,M+1,R)); 35 return ans; 36 } 37 38 }; 39 40 IntervalTree tree; 41 const int maxn = 100000 + 10; 42 int A[maxn]; 43 44 int main() 45 { 46 int n,q; 47 memset(&tree,0,sizeof(tree)); 48 49 scanf("%d%d",&n,&q); 50 51 for(p=1; p<=n; p++) 52 { 53 scanf("%d",&v); 54 A[p] = v; 55 tree.update(1,1,n); 56 } 57 58 int k,args[20],original[20]; 59 char cmd[100]; 60 while(q--) 61 { 62 scanf("%s", cmd); 63 int len = strlen(cmd); 64 k = 0; 65 args[k] = 0; 66 for(int i = 6; i < len; i++) 67 { 68 if(isdigit(cmd[i])) args[k] = args[k] * 10 + cmd[i] - ‘0‘; 69 else 70 { 71 k++; 72 args[k] = 0; 73 } 74 } 75 if(cmd[0] == ‘q‘) 76 { 77 qL = args[0]; 78 qR = args[1]; 79 printf("%d ", tree.query(1, 1, n)); 80 } 81 else 82 { 83 for(int i = 0; i < k; i++) original[i] = A[args[i]]; 84 for(int i = 0; i < k; i++) 85 { 86 p = args[i]; 87 v = A[p] = original[(i+1)%k]; 88 tree.update(1, 1, n); 89 } 90 } 91 } 92 return 0; 93 }
第二种是有一个build的过程,先将数组存起来,然后build,应用到要维护的信息上去。
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 6 const int INF = 1000000000; 7 const int maxnode = 1<<18; 8 9 const int maxn = 100000 + 10; 10 int A[maxn]; 11 int op, qL, qR, p, v; 12 13 struct IntervalTree 14 { 15 int minv[maxnode]; 16 17 18 void build(int o,int L,int R) 19 { 20 int M = L + (R-L)/2; 21 if(L==R) minv[o] = A[L]; 22 else 23 { 24 build(o*2,L,M); 25 build(o*2+1,M+1,R); 26 minv[o] = min(minv[o*2],minv[o*2+1]); 27 } 28 } 29 30 //点修改 d[p] =v; 31 void update(int o,int L,int R) 32 { 33 int M = L + (R-L)/2; 34 if(L==R) minv[o] = v; 35 else 36 { 37 if(p<=M) update(o*2,L,M); 38 else update(o*2+1,M+1,R); 39 minv[o] = min(minv[o*2],minv[o*2+1]); 40 } 41 } 42 43 int query(int o,int L,int R) 44 { 45 46 int M = L + (R-L)/2,ans=INF; 47 if(qL<=L&&R<=qR) 48 return minv[o]; 49 50 if(qL<=M) ans = min(ans,query(o*2,L,M)); 51 if(M<qR) ans = min(ans,query(o*2+1,M+1,R)); 52 53 return ans; 54 } 55 56 }; 57 58 IntervalTree tree; 59 60 int main() 61 { 62 int n,q; 63 scanf("%d%d",&n,&q); 64 memset(&tree,0,sizeof(tree)); 65 for(int i=1; i<=n; i++) 66 scanf("%d",&A[i]); 67 tree.build(1,1,n); 68 69 int k,args[20],original[20]; 70 char cmd[100]; 71 while(q--) 72 { 73 scanf("%s", cmd); 74 int len = strlen(cmd); 75 k = 0; 76 args[k] = 0; 77 for(int i = 6; i < len; i++) 78 { 79 if(isdigit(cmd[i])) args[k] = args[k] * 10 + cmd[i] - ‘0‘; 80 else 81 { 82 k++; 83 args[k] = 0; 84 } 85 } 86 if(cmd[0] == ‘q‘) 87 { 88 qL = args[0]; 89 qR = args[1]; 90 printf("%d ", tree.query(1, 1, n)); 91 } 92 else 93 { 94 for(int i = 0; i < k; i++) original[i] = A[args[i]]; 95 for(int i = 0; i < k; i++) 96 { 97 p = args[i]; 98 v = A[p] = original[(i+1)%k]; 99 tree.update(1, 1, n); 100 } 101 } 102 } 103 return 0; 104 }
hdu1754-ihateit & uva12299-rmqwithshifts - [单点/区间修改区间查询线段树]
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1754TimeLimit:9000/3000MS(Java/Others)MemoryLimit:32768/32768K(Java/Others)ProblemDescription很多学校流行一种比较的习惯。老师们很喜欢询问,从某某到某某当中,分数最高的是多少。这让很多学生很反感... 查看详情
uva11235frequentvalues线段树/rmq
vjudge上题目链接:UVA11235*******************************************************大白书上解释************************************************************ 题目大意:给出一个非降序排列的整数数组a1,a2,a3,...,an,你的任务是对于一系列询问(i,j),回... 查看详情
题解uva12299rmqwithshifts(代码片段)
...a1......,第an个数赋给an-1,第a0个数赋给an主要思路:三叉线段树(单点修改,区间求最值)其实就是一道比较裸的线段树模板题,因为题目中shift操作的字符长不超过30char,也就是说没几个数,我们完全可以直接暴力的每个操作... 查看详情
[uva11235]frequentvalues
...的。本题可用RMQ做,但是我不会啊。其实这题可以直接用线段树做(什么?RMQ可以用线段树做?我还是不会啊),不过需要保存三个东西,该区间出现最多的数出现的次数,该区间最左边的数出现的次数,该区间最右边出现的次数... 查看详情
线段树+rmq问题第二弹
线段树+RMQ问题第二弹 上篇文章讲到了基于SparseTable解决RMQ问题,不知道大家还有没有印象,今天我们会从线段树的方法对RMQ问题再一次讨论。正式介绍今天解决RMQ问题的方法之前,我先对RMQ问题的概念再... 查看详情
暑假集训day8
...个就不介绍了,应该都知道RMQwithshift(UVa12299)这题就简单线段树跑一下就好了,本人巨弱不会zkw。#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>usingnamespacestd;co 查看详情
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\\)分析先考虑线段树的区间赋值和区间最小值询问,如果没有复... 查看详情
[拆位线段树]rmq(代码片段)
[拆位线段树]RMQ题目https://ac.nowcoder.com/acm/problem/21414思路区间或,区间求和对于区间或,异或这种位运算,没法之间打懒标记。但是如果我们按位拆分,可以发现对于原数组都为01的线段树来说,或运算等效于... 查看详情
[luogup1816]忠诚(rmq||线段树)
传送门 其实我就是想练练rmq本以为学了线段树可以省点事不学rmq了但是后缀数组中用rmq貌似很方便所以还是学了吧,反正也不难 ——代码1#include<cstdio>2#defineN1000013#definemin(x,y)((x)<(y)?(x):(y))45intn,m;6inta[N],d[N][21]... 查看详情
pku2823slidingwindow(线段树||rmq||单调队列)
#include<cstdio>#include<algorithm>#definemaxn1000005#defineinf0x3f3f3f3fusingnamespacestd;intSegtree_min[maxn<<2],Segtree_max[maxn<<2];intn,k,value;intbegin,end;//每个结点保存该区间线段的 查看详情
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< 查看详情
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... 查看详情
uva11990”dynamic“inversion(线段树+树状数组)
...计出现的逆序对数量 对于每个删去的数,我们可以用线段树求出它在原序列中的逆序对贡献 在线段树的每个区间有序化数据,就可以二分查找出这个数在每个区间的位置, 这样就处理出了划分出的区间的贡献,先用... 查看详情
uva11297census——二维线段树
【题目分析】 二维线段树模板题目。 简直就是无比的暴力。时间复杂度为两个log。 标记的更新方式比较奇特,空间复杂度为N^2。 模板题目。【代码】#include<cstdio>#include<cstring>//#include&l... 查看详情
nyoj119士兵杀敌(线段树区间最值查询,rmq算法)
题目119题目信息执行结果本题排行讨论区士兵杀敌(三)时间限制:2000 ms | 内存限制:65535 KB难度:5描写叙述南将军统率着N个士兵,士兵分别编号为1~N,南将军常常爱拿某一段编号内杀敌数最高的人与杀敌数最低... 查看详情
uva11297census(二维线段树)
...查询qx1y1x2y2查询这个矩形内的最大值和最小值。析:二维线段树裸板。代码如下:#pragmacomment(linker,"/STACK:1024000000,1024000000")#include<cstdio>#include<string>#include<cstd 查看详情