rmq（range max/min query）
区间最值查询
-----------------------------------------------------------------------------------------
st(Sparse_Table)算法http://acm.nyist.net/JudgeOnline/problem.php?pid=119
1 #include <iostream> 2 #include <stdio.h> 3 #include <cmath> 4 using namespace std; 5 const int maxn = 100009; 6 int a[25][maxn], b[25][maxn], n, q, k[maxn]; 7 void la(){ 8 for(int i = 1; i <= k[n]; ++i){ 9 for(int j = 1; j <= n; ++j) if(j+(1<<i)-1 <= n){ 10 a[i][j] = min(a[i-1][j], a[i-1][j+(1<<i>>1)]); 11 b[i][j] = max(b[i-1][j], b[i-1][j+(1<<i>>1)]); 12 } 13 } 14 } 15 int r(int x, int y){ 16 int kk = k[y-x+1]; 17 return max(b[kk][x], b[kk][y-(1<<kk)+1]) - min(a[kk][x], a[kk][y-(1<<kk)+1]); 18 } 19 int main(){ 20 scanf("%d%d", &n, &q); 21 k[0] = -1; 22 for(int i = 1; i <= n; ++i){ 23 k[i] = ((i&(i-1)) == 0) ? k[i-1]+1 : k[i-1]; 24 scanf("%d", &a[0][i]); 25 b[0][i] = a[0][i]; 26 } 27 la(); 28 int x, y; 29 for(int i = 0; i < q; ++i){ 30 scanf("%d%d", &x, &y); 31 printf("%d ", r(x, y)); 32 } 33 return 0; 34 }
--------------------------------------------------------------------------------------------
线段树
@单点更新
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 ",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 ", query(b, c, 1, n, 1)); 74 } 75 } 76 return 0; 77 }
--------------------------------------------------------------------------
只有不断学习才能进步！