hdu 1754 I hate it(线段树单点更新)

hdu 1754 I hate it(线段树单点更新)

题意：#include#includeusing namespace std;const int maxn=2e5+5;int sco[maxn];struct node{ int left,right,score;}btree[3*maxn]; // 设置根节点下标是1，则左孩子是2*dex,右孩子下标是2*dex+1.void build(int root,int l,int r){ // 主函数里的数组的下标对应线段树的left,right btree[root].left=l; //root对应树和各种子树的根节点 btree[root].right=r; if(l==r){ btree[root].score=sco[l]; return ; } int mid=(l+r)/2; build(root*2,l,mid); build(root*2+1,mid+1,r); btree[root].score=max(btree[2*root].score,btree[2*root+1].score); //递归回溯赋值给双亲结点}void update(int root,int pos,int val){ if(btree[root].left==btree[root].right){ btree[root].score=val; return ; } int mid=(btree[root].left+btree[root].right)/2; if(pos<=mid)update(2*root,pos,val); else update(2*root+1,pos,val); btree[root].score=max(btree[2*root].score,btree[2*root+1].score);}int query(int root,int L,int R){ if(L<=btree[root].left&&R>=btree[root].right)return btree[root].score; int mid=(btree[root].left+btree[root].right)/2,ans=0; if(L<=mid)ans=max(ans,query(root*2,L,R)); // L,R不要弄错，否则会数组越界 if(R>mid)ans=max(ans,query(root*2+1,L,R)); return ans;}int main(){ //freopen("cin.txt","r",stdin); int i,N,M; while(cin>>N>>M){ for(i=1;i<=N;i++)scanf("%d",&sco[i]); build(1,1,N); for(i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。