大致题意:
给出一个数组,在线更新点的值,查询区间的极值。
大致思路:
简单线段树。
#include<iostream> #include<cstring> #include<cstdio> using namespace std; const int Max = 250005; struct data{ int l, r, num; }node[4*Max]; // 线段树节点的数据结构。 int num[Max]; void BuildTree(int left, int right, int u){ // 建树。 node[u].l = left; node[u].r = right; if(left == right) node[u].num = num[left]; else{ BuildTree(left, (left+right)/2, 2*u); BuildTree((left+right)/2+1, right, 2*u+1); node[u].num = max(node[2*u].num , node[2*u+1].num); } } int updata(int loc, int w, int u){ // 修改。 if(node[u].l == node[u].r ){ node[u].num = w; return 0; } if(loc <= node[2*u].r){ updata(loc , w, u*2); }else{ updata(loc , w, u*2+1); } node[u].num = max(node[2*u].num , node[2*u+1].num); return 0; } int query(int left, int right, int u){ // 查询。 if(node[u].l == left && node[u].r == right) return node[u].num; if(right <= node[2*u].r) return query(left, right, 2*u); if(left >= node[2*u+1].l) return query(left, right, 2*u+1); int a = query(left, (node[u].l+node[u].r)/2, 2*u); int b = query((node[u].l+node[u].r)/2+1, right, 2*u+1); return max(a,b); } int main() { char str[10]; int cas,i,j,a,b,c,n,m,t=0; while(scanf("%d%d",&n,&m)!=EOF) { for(i=1;i<=n;i++) { scanf("%d",&num[i]); } BuildTree(1,n,1); while(m--) { scanf("%s",str); scanf("%d%d",&a,&b); if(str[0]=='Q'){ a=query(a,b,1); printf("%d\n",a); } if(str[0]=='U'){ updata(a,b,1); } } } return 0; }
相关推荐
HDOJ题目分类HDOJ题目分类HDOJ题目分类
ACM ICPC HDOJ1002
ACM ICPC HDOJ1001
hdoj1001标程
hdoj上的资源,代码有注释,很不错的哦
hdoj1004,解题代码,答案代码,欢迎下载
ACM ICPC HDOJ1008
ACM ICPC HDOJ1003
杭州电子科技大学hdoj1002,大整数相加问题
杭州电子科大HDOJ
ACM ICPC HDOJ1000
hdoj解题代码,题目为1000-1050
c语言 最短路 是hdoj上的一个最短路问题,写的很牛
一些HDOJ上的DP题目的小总结,但愿能帮到那些想专攻DP的人吧
codj,hdoj的源码(50-60题)
hdoj 2013 多校训练3标程+解题报告
HDOJ 源代码 包含几百道HDOJ题目源码
hdoj1005 Number Sequence, 杭州电子科技大学oj题目代码
Problem Description Calculate A + B. Input Each line will contain two integers A and B....HDOJ 代码: #include int main() { int a,b; while(scanf("%d %d",&a,&b)!=EOF) printf("%d\n",a+b); }
杭电OJ(1000-1099) AC 代码