首页 > 代码库 > 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(线段树)