首页 > 代码库 > Uva 12299 带循环移动的RMQ（线段树）
Uva 12299 带循环移动的RMQ（线段树）
题目链接：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 IntervalTree12 {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 else21 {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 else70 {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\n", tree.query(1, 1, n));80 }81 else82 {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\n", 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 }
Uva 12299 带循环移动的RMQ（线段树）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。