首页 > 代码库 > wenbao与RMP(线段树)
wenbao与RMP(线段树)
rmq
就是在变化的前提下在一定范围内查询最值
@单点更新
http://hihocoder.com/problemset/problem/1077
在大神面前这就是水题????
自愧不如
1 #include <cstdio> 2 #include <iostream> 3 using namespace std; 4 const int maxn = 1e6+10; 5 #define INF 0x3f3f3f3f; 6 struct Node{ 7 int lx, rx, mi; 8 } Tree[maxn<<2]; 9 10 void build(int lx, int rx, int node){11 Tree[node].lx = lx;12 Tree[node].rx = rx;13 if(lx == rx){14 scanf("%d", &Tree[node].mi);15 return ;16 }17 int mid = (lx + rx) >> 1;18 build(lx, mid, node<<1);19 build(mid+1, rx, node<<1|1);20 Tree[node].mi = min(Tree[node<<1].mi, Tree[node<<1|1].mi);21 }22 23 void update(int point, int v, int node){24 if(Tree[node].lx == Tree[node].rx){25 Tree[node].mi = v;26 return ;27 }28 if(point >= Tree[node<<1|1].lx) update(point, v, node<<1|1);29 if(point <= Tree[node<<1].rx) update(point, v, node<<1);30 Tree[node].mi = min(Tree[node<<1].mi, Tree[node<<1|1].mi);31 }32 33 int query(int lx, int rx, int node){34 if(Tree[node].lx >= lx && Tree[node].rx <= rx){35 return Tree[node].mi;36 }37 int a = INF;38 int b = INF;39 if(lx <= Tree[node<<1].rx) a = query(lx, rx, node<<1);40 if(rx >= Tree[node<<1|1].lx) b = query(lx, rx, node<<1|1);41 return min(a, b);42 }43 44 int main(){45 int n, m, a, b, c;46 scanf("%d", &n);47 build(1, n, 1);48 cin>>m;49 for(int i = 0; i < m; i++){50 scanf("%d %d %d", &a, &b, &c);51 if(a){52 update(b, c, 1);53 }54 else{55 printf("%d\n",query(b, c, 1));56 }57 }58 return 0;59 }
@区间更新
http://hihocoder.com/problemset/problem/1078
学习到了。。。。。
1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4 const int maxn = 1e5 + 10; 5 int sum[maxn << 2], lazy[maxn << 2]; 6 #define lson lx, mid, node << 1 7 #define rson mid + 1, rx, node << 1 | 1 8 9 void pushup(int node){10 sum[node] = sum[node << 1] + sum[node << 1 | 1]; 11 }12 13 void pushdown(int node, int rangl, int rangr){14 if(lazy[node]){15 sum[node << 1] = rangl * lazy[node]; //。。。。。。。。。。。。。。。16 sum[node << 1 | 1] = rangr * lazy[node]; //此处写错了,調了半天17 lazy[node << 1] = lazy[node];18 lazy[node << 1 | 1] = lazy[node];19 lazy[node] = 0;20 }21 }22 23 void build(int lx, int rx, int node){24 lazy[node] = 0;25 if(lx == rx){26 scanf("%d", &sum[node]);27 return ;28 }29 int mid = (lx + rx) >>1;30 build(lson);31 build(rson);32 pushup(node);33 }34 35 void update(int xl, int xr, int val, int lx, int rx, int node){36 if(xl <= lx && rx <= xr){37 sum[node] = (rx - lx + 1) *val;38 lazy[node] = val;39 return ;40 }41 int mid = (lx + rx) >> 1;42 pushdown(node, mid - lx + 1, rx - mid);43 if(xl <= mid) update(xl, xr, val, lson);44 if(mid < xr) update(xl, xr, val, rson);45 pushup(node);46 }47 48 int query(int xl, int xr, int lx, int rx, int node){49 if(xl <= lx && rx <= xr){50 return sum[node];51 }52 int ans = 0;53 int mid = (lx + rx) >>1;54 pushdown(node, mid - lx + 1, rx - mid);55 if(xl <= mid) ans += query(xl, xr, lson);56 if(mid < xr) ans += query(xl, xr, rson);57 return ans;58 }59 60 int main(){61 int n, m, a, b, c, d;62 scanf("%d", &n);63 build(1, n, 1);64 scanf("%d", &m);65 while(m--){66 scanf("%d", &a);67 if(a){68 scanf("%d %d %d", &b, &c, &d);69 update(b, c, d, 1, n, 1);70 }71 else{72 scanf("%d %d", &b, &c);73 printf("%d\n", query(b, c, 1, n, 1));74 }75 }76 return 0;77 }
wenbao与RMP(线段树)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。