线段树，最大值查询位子：
1 #include2 #include 3 #include 4 5 using namespace std; 6 7 #define lson l, m, rt<<1 8 #define rson m+1, r, (rt<<1)|1 9 10 int tree[111111<<2]; 11 int posn[111111<<2]; 12 void pushup(int rt) 13 { 14 if (tree[rt<<1] > tree[rt<<1|1]) 15 { 16 tree[rt] = tree[rt<<1]; 17 posn[rt] = posn[rt<<1]; 18 } 19 else 20 { 21 tree[rt] = tree[rt<<1|1]; 22 posn[rt] = posn[rt<<1|1]; 23 } 24 } 25 void build(int l, int r, int rt) 26 { 27 if (l == r) 28 { 29 scanf("%d", &tree[rt]); 30 posn[rt] = l; 31 } 32 else 33 { 34 int m = (l + r) >> 1; 35 build(lson); 36 build(rson); 37 pushup(rt); 38 } 39 } 40 void update(int p, int val, int l, int r, int rt) 41 { 42 if (l == r) 43 { 44 tree[rt] = val; 45 } 46 else 47 { 48 int m = (l + r) >> 1; 49 if (p <= m) 50 { 51 update(p, val, lson); 52 } 53 else 54 { 55 update(p, val, rson); 56 } 57 pushup(rt); 58 } 59 } 60 int query(int L, int R, int l, int r, int rt, int *pos) 61 { 62 if (L <= l && r <= R) 63 { 64 *pos = posn[rt]; 65 return tree[rt]; 66 } 67 else 68 { 69 int m = (l + r) >> 1; 70 int ret1 = INT_MIN; 71 int ret2 = INT_MIN; 72 int pa, pb; 73 int *pos1 = &pa; 74 int *pos2 = &pb; 75 if (L <= m) 76 { 77 ret1 = query(L, R, lson, pos1); 78 } 79 if (R > m) 80 { 81 ret2 = query(L, R, rson, pos2); 82 } 83 if (ret1 > ret2) 84 { 85 *pos = pa; 86 } 87 else 88 { 89 *pos = pb; 90 ret1 = ret2; 91 } 92 return ret1; 93 } 94 } 95 int main(void) 96 { 97 int n, m; 98 99 while (scanf("%d", &n) != EOF)100 {101 build(1, n, 1);102 103 scanf("%d", &m);104 char op[2];105 int a, b;106 while (m--)107 {108 scanf("%s", op);109 if (op[0] == 'Q')110 {111 int pos;112 printf("%d %d\n", pos, query(1, n, 1, n, 1, &pos));113 }114 else115 {116 scanf("%d%d", &a, &b);117 update(a, b, 1, n, 1);118 }119 }120 printf("\n");121 }122 123 return 0;124 }