首页 > 代码库 > hdu 1754 I Hate It 线段树 点改动
hdu 1754 I Hate It 线段树 点改动
// hdu 1754 I Hate It 线段树 点改动 // // 不多说,裸的点改动 // // 继续练 #include <algorithm> #include <bitset> #include <cassert> #include <cctype> #include <cfloat> #include <climits> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <functional> #include <iostream> #include <list> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <vector> #define ceil(a,b) (((a)+(b)-1)/(b)) #define endl ‘\n‘ #define gcd __gcd #define highBit(x) (1ULL<<(63-__builtin_clzll(x))) #define popCount __builtin_popcountll typedef long long ll; using namespace std; const int MOD = 1000000007; const long double PI = acos(-1.L); template<class T> inline T lcm(const T& a, const T& b) { return a/gcd(a, b)*b; } template<class T> inline T lowBit(const T& x) { return x&-x; } template<class T> inline T maximize(T& a, const T& b) { return a=a<b?b:a; } template<class T> inline T minimize(T& a, const T& b) { return a=a<b?a:b; } const int maxn = 8 * 1e5 +8; int maxv[maxn]; int n,m; const int inf = 0x7f7f7f7f; void build(int root,int L,int R){ if (L==R){ scanf("%d",&maxv[root]); return ; } int M = L + ( R - L ) / 2; build(root*2,L,M); build(root*2+1,M+1,R); maxv[root] = max(maxv[root*2],maxv[root*2+1]); } int p,v; void update(int root,int L,int R){ if (L==R){ maxv[root] = v; return ; } int M = L + ( R - L ) / 2; if (p<=M) update(root*2,L,M); else update(root*2+1,M+1,R); maxv[root] = max(maxv[root*2],maxv[root*2+1]); } int query(int root,int ql,int qr,int L,int R){ if (ql<=L && R<=qr){ return maxv[root]; } int M = L + ( R - L) / 2; int ans = 0; if (ql<=M) ans = max(ans,query(root*2,ql,qr,L,M)); if (M<qr) ans = max(ans,query(root*2+1,ql,qr,M+1,R)); return ans; } void init(){ build(1,1,n); char s[3]; for (int i=0;i<m;i++){ int x,y; scanf("%s%d%d",s,&x,&y); if (s[0]==‘Q‘){ printf("%d\n",query(1,x,y,1,n)); }else { p = x; v = y; update(1,1,n); } } } int main() { // freopen("G:\\Code\\1.txt","r",stdin); while(scanf("%d%d",&n,&m)!=EOF){ init(); } return 0; }
hdu 1754 I Hate It 线段树 点改动
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。