每個測試點（輸入文件）有且僅有一組測試數據。
每組測試數據的第1行為一個整數N，意義如前文所述。
每組測試數據的第2行為N個整數，分別描述每種商品的重量，其中第i個整數表示標號為i的商品的重量weight_i。
每組測試數據的第3行為一個整數Q，表示小Hi總共詢問的次數與商品的重量被更改的次數之和。
每組測試數據的第N+4~N+Q+3行，每行分別描述一次操作，每行的開頭均為一個屬於0或1的數字，分別表示該行描述一個詢問和描述一次商品的重 量的更改兩種情況。對於第N+i+3行，如果該行描述一個詢問，則接下來為兩個整數Li, Ri，表示小Hi詢問的一個區間[Li, Ri]；如果該行描述一次商品的重量的更改，則接下來為兩個整數Pi，Wi，表示位置編號為Pi的商品的重量變更為Wi
對於100%的數據，滿足N<=10^6，Q<=10^6, 1<=Li<=Ri<=N，1<=Pi<=N, 0<weight_i, Wi<=10^4。
對於每組測試數據，對於每個小Hi的詢問，按照在輸入中出現的順序，各輸出一行，表示查詢的結果：標號在區間[Li, Ri]中的所有商品中重量最輕的商品的重量。
1 #include <cstdio>
2
3 const int NM = 1<<21;
4 int a[NM] = {0};
5 int _min(int x,int y) {return (x<y)?x:y;}
6
7 int aa;char ch;
8
9 int _getNumber()
10 {
11 while(ch=getchar(),ch<48||ch>57);
12 aa=ch-48;
13 while(ch=getchar(),ch>47&&ch<58)
14 aa=(aa<<1)*5+ch-48;
15 return aa;
16 }
17
18
19
20 int _query(int l,int r)
21 {
22 int res = NM;
23 while(1)
24 {
25 if(l>r) break;
26 if(l==r) {res = _min(res,a[l]); break;}
27 if((l&1)==1) {res = _min(res,a[l]); l++;}
28 if((r&1)==0) {res = _min(res,a[r]); r--;}
29 l>>=1; r>>=1;
30 }
31 return res;
32 }
33
34 void _update(int p,int v)
35 {
36 a[p] = v;
37 while(1)
38 {
39 p>>=1;
40 if(p==0)
41 break;
42 a[p] = _min(a[p<<1],a[(p<<1)|1]);
43 }
44 }
45
46 int main()
47 {
48 int N,Q,A,B,C;
49 N = _getNumber();
50 for(A=1;A<N;A<<=1); B = A+N; C = A<<1;
51 for(int i = A; i < B; i++) a[i] = _getNumber();
52 for(int i = B; i < C; i++) a[i] = NM;
53 for(int i = A-1; i; i--) a[i] = _min(a[i<<1],a[(i<<1)|1]);
54
55 Q = _getNumber();
56 for(int i = 0; i < Q; i++)
57 {
58 int x,y,z;
59 x = _getNumber(); y = _getNumber(); z = _getNumber();
60 if(x==0)
61 printf("%d\n",_query(--y+A,--z+A));
62 else
63 _update(--y+A,z);
64 }
65 return 0;
66 }
