1 #include <stdio.h> 2 #define N 1024 3  4 typedef struct { 5     int min_value; 6     int left; 7     int right; 8 } ST; 9 10 int  input[N + 1];11 int father[N + 1];12 ST  st[N * 2 + 1];13 14 15 /* 查询 */16 int query_ST(int i, int left, int right) {17     if(left == right) {18         return st[father[left]].min_value;19     }20     int l = st[i].left;21     int r = st[i].right;22     if(l == left && r == right) {23         return st[i].min_value;24     }25     else if(right <= (r + l) / 2) {26         return query_ST(i * 2, left, right);27     }28     else if(left > (r + l) / 2) {29         return query_ST(i * 2 + 1, left, right);30     }31     else {32         int min_l = query_ST(i * 2, left, (l + r) / 2);33         int min_r = query_ST(i * 2 + 1, (l + r) / 2 + 1, right);34         return  min_l = min_l < min_r ? min_l : min_r;35     }36 }37 38 /* 修改 */39 void modify_ST(int pos, int value) {40     int i = father[pos];41     int min_l, min_r;42     st[i].min_value =http://www.mamicode.com/ value;43     i = i / 2;44     while(i) {45         min_l = st[i * 2].min_value;46         min_r = st[i * 2 + 1].min_value;47         min_l = min_l < min_r ? min_l : min_r;48         if(st[i].min_value =http://www.mamicode.com/= min_l) break;49         st[i].min_value =http://www.mamicode.com/ min_l;50         i = i / 2;51     }52 }53 54 /* 建树 */55 int build_ST(int i, int left, int right) {56     st[i].left = left;57     st[i].right = right;58     if(left == right) {59         father[left] = i;60         st[i].min_value =http://www.mamicode.com/ input[left];61         return input[left];62     }63     int min_l = build_ST(i * 2, left, (left + right) / 2);64     int min_r = build_ST(i * 2 + 1, (left + right) / 2 + 1, right);65     min_l = min_l < min_r ? min_l : min_r;66     return st[i].min_value =http://www.mamicode.com/ min_l;67 }68 69 int main() {70     int m, n;71     int b_mod, left, right;72     scanf("%d", &n);73     for(int i = 0; i < n; i++) {74         scanf("%d", &input[i]);75     }76     scanf("%d", &m);77     build_ST(1, 0, n - 1);78     for(int i = 0; i < m; i++) {79         scanf("%d %d %d", &b_mod, &left, &right);80         if(b_mod) { modify_ST(left - 1, right); }81         else { printf("%d\n", query_ST(1, left - 1, right - 1)); }82     }83     return 0;84 }

  1 #include <stdio.h>  2 #define N 1024 * 1024  3   4 typedef struct {  5     int left;  6     int righ;  7     int lazy;  8     int sum;  9 }st_node; 10  11 st_node st[N + 1]; 12 int  seg[2 * N + 1]; 13  14 int build_st(int i, int left, int righ) { 15     st[i].left = left; 16     st[i].righ = righ; 17     if(left == righ) { 18         st[i].sum = seg[left]; 19         st[i].lazy = -1; 20         return st[i].sum; 21     } 22     int l_sum = build_st(i * 2, left, (left + righ) / 2); 23     int r_sum = build_st(i * 2 + 1, (left + righ) / 2 + 1, righ); 24     st[i].sum = l_sum + r_sum; 25     st[i].lazy = -1; 26     return l_sum + r_sum; 27 } 28 int modify_st(int i, int left, int righ, int value) { 29     if(st[i].left == left && st[i].righ == righ) { 30         st[i].lazy = value; 31         st[i].sum = (righ + 1 - left) * value; 32         return st[i].sum; 33     } 34     else { 35         if(-1 != st[i].lazy) { 36             int l_len = st[i * 2].righ + 1 - st[i * 2].left;  37             st[i * 2].lazy = st[i].lazy; 38             st[i * 2].sum = l_len * st[i * 2].lazy; 39  40             int r_len = st[i * 2 + 1].righ + 1 - st[i * 2 + 1].left; 41             st[i * 2 + 1].lazy = st[i].lazy; 42             st[i * 2 + 1].sum = r_len * st[i * 2 + 1].lazy; 43  44             st[i].lazy = -1;             45         } 46         int l = st[i].left; 47         int r = st[i].righ; 48         int l_sum = st[i * 2].sum; 49         int r_sum = st[i * 2 + 1].sum; 50         if(righ <= (r + l) / 2) { 51             l_sum = modify_st(i * 2, left, righ, value); 52         } 53         else if(left > (r + l) / 2) { 54             r_sum = modify_st(i * 2 + 1, left, righ, value); 55         } 56         else { 57             l_sum = modify_st(i * 2, left, (l + r) / 2, value); 58             r_sum = modify_st(i * 2 + 1, (l + r) / 2 + 1, righ, value); 59         } 60         st[i].sum= l_sum + r_sum; 61         return st[i].sum; 62     } 63 } 64  65 int query_st(int i, int left, int righ) { 66     if(st[i].left == left && st[i].righ == righ) { 67         return st[i].sum; 68     } 69     else { 70         if(-1 != st[i].lazy) { 71             int l_len = st[i * 2].righ - st[i * 2].left + 1;      72             st[i * 2].lazy = st[i].lazy; 73             st[i * 2].sum = l_len * st[i * 2].lazy; 74  75             int r_len = st[i * 2 + 1].righ + 1 - st[i * 2 + 1].left; 76             st[i * 2 + 1].lazy = st[i].lazy; 77             st[i * 2 + 1].sum = r_len * st[i * 2 + 1].lazy; 78  79             st[i].lazy = -1; 80         } 81         int l = st[i].left; 82         int r = st[i].righ; 83         int l_sum = 0; 84         int r_sum = 0; 85         if(righ <= (r + l) / 2) { 86             l_sum = query_st(i * 2, left, righ); 87         }    88         else if(left > (r + l) / 2) { 89             r_sum = query_st(i * 2 + 1, left, righ); 90         }  91         else { 92             l_sum = query_st(i * 2, left, (l + r) / 2); 93             r_sum = query_st(i * 2 + 1, (l + r) / 2 + 1, righ);                                                     94         } 95         return l_sum + r_sum; 96     } 97 } 98  99 int main() {100     int i, n, m;101     scanf("%d", &n);102     for(i = 1; i <= n; i++) {103         scanf("%d", &seg[i]);104     }105     build_st(1, 1, n);106     scanf("%d", &m);107     for(i = 0; i < m; i++) {108         int mode;109         int left;110         int righ;111         int value;112         scanf("%d", &mode);113         if(mode) { 114             scanf("%d %d %d", &left, &righ, &value); 115             modify_st(1, left, righ, value);116         }117         else {118             scanf("%d %d", &left, &righ);119             printf("%d\n", query_st(1, left, righ));120         }121     }122     return 0;123 }