[关闭]
@lunar 2016-04-04T20:31:01.000000Z 字数 1572 阅读 1261

HiHo一下 Week18 Week19 动态RMQ

HiHo


输入

每个测试点(输入文件)有且仅有一组测试数据。

每组测试数据的第1行为一个整数N,意义如前文所述。

每组测试数据的第2行为N个整数,分别描述每种商品的重量,其中第i个整数表示标号为i的商品的重量weight_i。

每组测试数据的第3行为一个整数Q,表示小Hi总共询问的次数与商品的重量被更改的次数之和。

每组测试数据的第N+4~N+Q+3行,每行分别描述一次操作,每行的开头均为一个属于0或1的数字,分别表示该行描述一个询问和描述一次商品的重量的更改两种情况。对于第N+i+3行,如果该行描述一个询问,则接下来为两个整数Li, Ri,表示小Hi询问的一个区间[Li, Ri];如果该行描述一次商品的重量的更改,则接下来为两个整数Pi,Wi,表示位置编号为Pi的商品的重量变更为Wi

对于100%的数据,满足N<=10^6,Q<=10^6, 1<=Li<=Ri<=N,1<=Pi<=N, 0< weight_i, Wi< =10^4。

输出

对于每组测试数据,对于每个小Hi的询问,按照在输入中出现的顺序,各输出一行,表示查询的结果:标号在区间[Li, Ri]中的所有商品中重量最轻的商品的重量。

样例

  1. 10
  2. 3655 5246 8991 5933 7474 7603 6098 6654 2414 884
  3. 6
  4. 0 4 9
  5. 0 2 10
  6. 1 4 7009
  7. 0 5 6
  8. 1 3 7949
  9. 1 3 1227
  1. 2414
  2. 884
  3. 7474

思路

这里用的是线段树的方法(segment tree),线段树的教程有这个

代码

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<vector>
  4. using namespace std;
  5. const int MAX=1000005;
  6. std::vector<int> items;
  7. int tree[2*MAX];
  8. int min(int a,int b){
  9. if (a<b) return a;
  10. else return b;
  11. }
  12. int buildTree(int l,int r,int p){
  13. if (l==r) {
  14. tree[p] = items[l];
  15. return tree[p];
  16. }
  17. int m = (l+r)/2;
  18. tree[p] = min(buildTree(l,m,p<<1),buildTree(m+1,r,p<<1|1));
  19. return tree[p];
  20. }
  21. void update(int x,int y,int l,int r,int t){
  22. if(l==r) {
  23. tree[t] = y;return;
  24. }
  25. int m = (l+r)/2;
  26. if(x<=m) {
  27. update(x,y,l,m,t<<1);}
  28. else update(x,y,m+1,r,t<<1|1);
  29. tree[t] = min(tree[t<<1],tree[t<<1|1]);
  30. }
  31. int query(int x,int y,int l,int r,int t){
  32. if(x<=l&&y>=r) return tree[t];
  33. int m = (l+r)/2;
  34. int val = 1e5;
  35. if(x<=m) val = min(val,query(x,y,l,m,t<<1));
  36. if(y>m) val = min(val,query(x,y,m+1,r,t<<1|1));
  37. return val;
  38. }
  39. int main(){
  40. int n,q,f,t,a,b;
  41. scanf("%d",&n);
  42. items.push_back(-1);
  43. for(int i=0;i<n;i++) {
  44. scanf("%d",&t);
  45. items.push_back(t);
  46. }
  47. buildTree(1,n,1);
  48. scanf("%d",&q);
  49. while(q--){
  50. scanf("%d%d%d",&f,&a,&b);
  51. if(f) update(a,b,1,n,1);
  52. else printf("%d\n",query(a,b,1,n,1));
  53. }
  54. return 0;
  55. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注