裸裸的线段树(hdu 1754)
HDU 线段
2023-09-11 14:14:59 时间
线段树的第一发。
哪天忘了还能够让自己找找回顾。
线段树操作:
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 3308 线段树,单点更新 求最长连续上升序列长度
- hdu 4745 Two Rabbits 区间dp
- hdu 1556 涂气球 线段树(区间更新~对区间[x,y]更新,求任意节点被更新的次数)
- hdu 1241 Oil Deposits (一次dfs搞定有某有)
- 【hdu 6396】Swordsman
- 【47.63%】【hdu 1532】Drainage Ditches
- 【42.49%】【hdu 1542】Atlantis(线段树扫描线简析)
- 【2017中国大学生程序设计竞赛 - 网络选拔赛 hdu 6150】Vertex Cover
- 当前插入的线段能完整覆盖存在的几条线段 树状数组 HDU 5372 Segment Game
- HDU 4362 Dragon Ball 线段树
- [ACM] HDU 2295 Radar (二分法+DLX 重复覆盖)
- HDU 3954 Level up(线段树)
- HDU 4907 Task schedule
- 【HDU 4763】Theme Section(KMP)
- hdu-2066 一个人的旅行
- HDU 3265 Posters(线段树)
- hdu 2795-Billboard
- HDU 3639 Hawk-and-Chicken(良好的沟通)
- (hdu step 7.1.2)You can Solve a Geometry Problem too(乞讨n条线段,相交两者之间的段数)
- HDU 4864Task(更多的联合培训学校1)(贪婪)