首页 > 代码库 > HDU 1754 I Hate It(线段树,单点更新,线段查询)
HDU 1754 I Hate It(线段树,单点更新,线段查询)
这道题是线段树入门题,其问题是单点更新,线段查询。
这里本来还打算用lazy标记做一下,但是不行,必须更新到单点
#include <map> #include <set> #include <queue> #include <cmath> #include <cmath> #include <vector> #include <bitset> #include <vector> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define inf 0x3fffffff #define mid ((l+r)>>1) #define LSON(x) (x) << 1 #define RSON(x) (x) << 1 | 1 #define mem(x) memset(x,0,sizeof(x)) #define max(a,b) ((a)>(b)?(a):(b)) const int maxn=100+200000; const double eps=1e-6; typedef unsigned __int64 ull; vector< vector<int> > edge; /*struct P { int v,next; }p[maxn<<2]; int head[maxn];//st from 1 */ int N,M,T; typedef struct { int l,r,mas; }P; P tt[maxn<<3]; /* int push_up(int p,int l,int r) { } int push_down(int p,int l,int r) { } */ void build(int p,int l,int r) { tt[p].l=l;tt[p].r=r;tt[p].mas=0; if(l==r) return; build(p<<1,l,mid); build(p<<1 |1,mid+1,r); } int update(int p,int l,int r,int d) { if(tt[p].l==l && tt[p].r==r) {tt[p].mas=d;return d;} int m=(tt[p].l+tt[p].r)>>1; int tmp,ans=tt[p].mas; if(r<=m) tmp=update(p<<1,l,r,d); else if(l>m) tmp=update(p<<1 |1,l,r,d); else { tmp=update(p<<1,l,m,d); ans=max(ans,tmp); tmp=update(p<<1 |1,m+1,r,d); } return tt[p].mas=max(ans,tmp); } int query(int p,int l,int r) { if(tt[p].l==l && tt[p].r==r) return tt[p].mas; int m=(tt[p].l+tt[p].r)>>1; int tmp,ans=0; if(r<=m) tmp=query(p<<1,l,r); else if(l>m) tmp=query(p<<1 |1,l,r); else { tmp=query(p<<1,l,m); ans=max(ans,tmp); tmp=query(p<<1 |1,m+1,r); } return ans=max(ans,tmp); } int main() { int cas=1; int i,j,k; int ans; char str[30]; while(~scanf("%d%d",&N,&M)) { build(1,1,N); for(i=1;i<=N;i++) { scanf("%d",&k); update(1,i,i,k); } for(i=0;i<M;i++) { scanf("%s%d%d",str,&j,&k); if(str[0]=='U') update(1,j,j,k); else {ans=query(1,j,k);printf("%d\n",ans);} } } return 0; }
HDU 1754 I Hate It(线段树,单点更新,线段查询)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。