首页 > 代码库 > 裸裸的线段树(hdu 1754)
裸裸的线段树(hdu 1754)
线段树的第一发。
哪天忘了还能够让自己找找回顾。
线段树操作:
build : 建树。
update:点改动:
query:查询
Input
在每一个測试的第一行,有两个正整数 N 和 M ( 0<N<=200000,0<M<5000 ),分别代表学生的数目和操作的数目。
学生ID编号分别从1编到N。
第二行包括N个整数,代表这N个学生的初始成绩,当中第i个数代表ID为i的学生的成绩。
接下来有M行。每一行有一个字符 C (仅仅取‘Q‘或‘U‘) 。和两个正整数A。B。
当C为‘Q‘的时候。表示这是一条询问操作,它询问ID从A到B(包含A,B)的学生其中,成绩最高的是多少。
当C为‘U‘的时候,表示这是一条更新操作。要求把ID为A的学生的成绩更改为B。
5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5
Output
对于每一次询问操作,在一行里面输出最高成绩。
5
6
5
9
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> #define INF 0x3fffffff #define bug(a) cout<<a<<" ----->\n" using namespace std; const int N=200010; int maxt[4*N]; int a[N]; int n,q; void build(int o,int L,int R) { int m; if(L==R) { maxt[o]=a[L];return;} m=(L+R)/2;//bug(o); build(2*o,L,m); build(2*o+1,m+1,R); maxt[o]=max(maxt[2*o],maxt[2*o+1]); } int query(int ql,int qr,int o,int L,int R) { int m=(L+R)/2,ans=-INF; if(ql<=L&&R<=qr) return maxt[o]; if(ql<=m) ans=max(ans,query(ql,qr,2*o,L,m)); if(m<qr) ans=max(ans,query(ql,qr,2*o+1,m+1,R)); return ans; } void update(int p,int v,int o,int L,int R) { if(L==R){maxt[o]=v;return;} int m=(L+R)>>1; if(p<=m) update(p,v,2*o,L,m); else update(p,v,2*o+1,m+1,R); maxt[o]=max(maxt[2*o],maxt[2*o+1]); } int main() { char c[2]; int d,b; while(scanf("%d%d",&n,&q)!=EOF) { for(int i=1;i<=n;i++) scanf("%d",a+i); //bug(1); build(1,1,n); for(int i=1;i<=q;i++) { scanf("%s%d%d",c,&d,&b); if(c[0]=='Q') printf("%d\n",query(d,b,1,1,n)); else update(d,b,1,1,n); } } return 0; }
裸裸的线段树(hdu 1754)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。