Description

Little Ming很喜欢训练自己的快速读能力，他最近找到一种新的考验并训练快速读能力的方法，在一行具有很多数的数列里任意指定某一段长度，从左往右扫视一遍后说出这段数列中的最大值，但他不想一直只使用一个数列，所以他请了他的好朋友，一位非常喜欢编程的学生，Little Little来帮忙在原数列上时不时的做一些修改，给他出题并检验他的答案是否正确。Little Little在做修改操作时会选取某个点修改它的值，在做出题操作时给出某一段的左右端点。

Input

本题目包含多组测试，请处理到文件结束。

在每个测试的第一行，有两个正整数 N 和 M (  0<N<=200000,0<M<5000 )

第二行包含N个整数，代表初始时数列中的数据。

接下来有M行。每一行有一个字符 C (只取'Q'或'S') ，和两个正整数A，B。

当C为'Q'的时候，表示这是一条出题操作，A,B为端点下标值，有可能A比B大。

当C为'S'的时候，表示这是一条修改操作，要求把第A个数修改为B。

Output

对于每一次出题操作，在一行里面输出最大的数。

相邻2组测试之间要有一个空行。

Sample Input

5 6

1 2 3 4 5

Q 1 5

S 3 6

Q 3 4

Q 4 5

S 2 9

Q 1 5

Sample Output

5
6
5
9



这是一道再基础不过的线段树题了，不多赘述，相见代码及注释。可先参阅：http://www.cppblog.com/hoolee/archive/2012/07/29/185531.html
细节：题目中说A可能大于B，要注意交换A、B。

  1#include<stdio.h>
  2#include<stdlib.h>
  3#include<string.h>
  4#define LEN 2000000
  5int N, M;
  6typedef struct MyNode
  7{
  8    int bg, ed;
  9    int max;
 10    int lf, rt;
 11}MyNode;
 12MyNode A[LEN];//动态分配空间很耗时，先用数组A[]申请足够大的空间。
 13int count = 0;//记录A[]数组的使用情况，指向最后一个使用节点
 14int num[LEN];
 15int max(int a, int b)
 16{
 17    if(a > b)
 18        return a;
 19    return b;
 20}
 21void makeTree(int t)
 22{
 23    /**//*
 24    * t指向A[]节点的位置。
 25    * 建树过程为： 1.先有根节点，2.再建左右子树，3.然后修改根节点的子树指针
 26    */
 27    if(A[t].bg == A[t].ed)
 28    {
 29        A[t].max = num[A[t].bg];
 30        //A[t].lf = A[t].rt = 1;
 31        return;
 32    }
 33    int mid = (A[t].bg + A[t].ed) / 2;
 34    int lf = ++count;//开辟空间
 35    int rt = ++count;
 36    A[lf].bg = A[t].bg;
 37    A[lf].ed = mid;
 38    A[rt].bg = mid + 1;
 39    A[rt].ed = A[t].ed;
 40    makeTree(lf);
 41    makeTree(rt);
 42    A[t].lf = lf;
 43    A[t].rt = rt;
 44    A[t].max = max(A[lf].max, A[rt].max);
 45}
 46int query(int t, int bg, int ed)
 47{
 48    /**//*
 49        给定区间[bg, ed]，查询区间的最大值，
 50        [bg, ed]区间与t节点代表的区间有四种关系：（令(A[t].bg + A[t].ed) / 2）
 51        1.他俩是同一个区间，查询成功，返回A[t].max
 52        2.bg <= mid, 接着查询t的左子树
 53        3.ed > min，接着查询t的右子树
 54        4.否认则，同时查询t的左右子树
 55    */
 56    if(A[t].bg == bg && A[t].ed == ed)
 57    {
 58        return A[t].max;
 59    }
 60    int mid = (A[t].bg + A[t].ed) / 2;
 61    if(ed <= mid)
 62    {
 63        return query(A[t].lf, bg, ed);
 64    }
 65    else if(bg > mid)
 66    {
 67        return query(A[t].rt, bg, ed);
 68    }
 69    else
 70    {
 71        return max(query(A[t].lf, bg, mid), query(A[t].rt, mid + 1, ed));
 72    }
 73        
 74}
 75void change(int ap, int p, int b)
 76{
 77    /**//*
 78        ap指向当前节点，p是要修改的位置，b为值
 79        分为3中情况：
 80        1.A[ap]为叶子节点，修改A[ap].max为b
 81        2.p在ap的左子树上，去左子树上查询
 82        3.p在ap的右子树上，去右子树上查询
 83    */
 84    if(A[ap].bg == A[ap].ed)
 85    {
 86        A[ap].max = b;
 87        return;
 88    }
 89    int mid = (A[ap].bg + A[ap].ed) / 2;
 90    if(p <= mid)
 91    {
 92        change(A[ap].lf, p, b);
 93    }
 94    else// p > mid
 95    {
 96        change(A[ap].rt, p, b);
 97    }
 98    A[ap].max = max(A[A[ap].lf].max, A[A[ap].rt].max);//子树的max改变了，也要修改父节点的max值
 99}
100int main()
101{
102    int i, j;
103    int spaceline = 0;
104    while(scanf("%d%d", &N, &M) == 2)
105    {
106        if(spaceline)
107        {
108            putchar(10);
109        }
110        else{
111            spaceline = 1;
112        }
113        
114        for(int i = 0; i < N; i++)
115            scanf("%d", &num[i]);
116        count = 0;
117        int t = ++count;
118        A[t].bg = 0;
119        A[t].ed = N - 1;
120        makeTree(t);
121        for(int i = 0; i < M; i++)
122        {
123            getchar();
124            char c = getchar();
125            int a, b;
126            scanf("%d%d", &a, &b);
127            if(c == 'Q')
128            {
129                if(a > b)
130                {
131                    int t2 = a;
132                    a = b;
133                    b = t2;
134                }
135                int rs = query(1, a - 1, b - 1);
136                printf("%d\n", rs);
137            }
138            else 
139            {
140                change(1, a - 1, b);
141            }
142            //printf("c=%c a=%d b=%d\n", c, a, b);
143        }
144    }
145    
146    //system("pause");
147    return 0;
148}
149

 其实这道题我先是用java写的，TLE，同样的思想，用C++写，410MS AC。下面是超时的java代码，可能是new太耗时了。

TLE的java代码
  1import java.util.*;
  2import java.util.Scanner;
  3
  4class Main {
  5    
  6    static ArrayList<Integer> numary = new ArrayList<Integer>();
  7
  8    public static void main(String[] args) {
  9        ////
 10        //System.out.println("hello!");
 11        //
 12        Scanner sc = new Scanner(System.in);
 13        boolean spaceline = false;
 14        while(sc.hasNext()){
 15            int N = sc.nextInt();
 16            int M = sc.nextInt();
 17            numary.clear();
 18            for(int i = 0; i < N; i++){//read number
 19                int t = sc.nextInt();
 20                numary.add(t);
 21            }
 22            MyNode tree = new MyNode(0, N - 1, 0);
 23            makeTree(tree);
 24            
 25            sc.nextLine();
 26            if(spaceline){
 27                System.out.println();
 28            }
 29            else
 30                spaceline = true;
 31            for(int i = 0; i < M; i++){
 32                String instr = sc.nextLine();
 33                String[] strs = instr.split(" ");
 34                if(strs[0].equals("Q")){//query
 35                    int a = Integer.parseInt(strs[1]);
 36                    int b = Integer.parseInt(strs[2]);
 37                    if(a > b){
 38                        int t2 = a;
 39                        a = b;
 40                        b = t2;
 41                    }
 42                    int rs = query(tree, a - 1, b - 1);
 43                    System.out.println(rs);
 44                }
 45                else{//change
 46                    int p = Integer.parseInt(strs[1]);
 47                    int v = Integer.parseInt(strs[2]);
 48                    change(tree, p - 1, v);
 49                }
 50            }
 51        }//while sc.hasNext()
 52
 53    }
 54    static void change(MyNode nd, int p, int v){
 55        if(nd.bg == nd.ed){
 56            
 57            nd.max = v;
 58            return;
 59        }
 60        int mid = (nd.bg + nd.ed) / 2;
 61        
 62        if(p <= mid){
 63            change(nd.lf, p, v);
 64        }
 65        else{
 66            change(nd.rt, p, v);
 67            
 68        }
 69        nd.max = max(nd.lf.max, nd.rt.max);
 70    }
 71    
 72    static int query(MyNode nd, int bg, int ed){
 73        if(nd.bg == bg && nd.ed == ed)
 74            return nd.max;
 75        int mid = (nd.bg + nd.ed) / 2;
 76        if(ed <= mid){
 77            return query(nd.lf, bg, ed);
 78        }
 79        else if(bg > mid){
 80            return query(nd.rt, bg, ed);
 81        }
 82        else{
 83            return max(query(nd.lf, bg, mid), query(nd.rt, mid + 1, ed));
 84        }
 85    }
 86    
 87    static int max(int a, int b){
 88        if(a > b)
 89            return a;
 90        return b;
 91    }
 92    
 93    static void makeTree(MyNode nd){
 94        if(nd.bg == nd.ed){
 95            nd.max = numary.get(nd.bg);
 96            return;
 97        }
 98        int mid = (nd.bg + nd.ed) / 2;
 99        MyNode lf = new MyNode(nd.bg, mid, 0);
100        MyNode rt = new MyNode(mid + 1, nd.ed, 0);
101        
102        makeTree(lf);
103        makeTree(rt);
104        nd.lf = lf;
105        nd.rt = rt;
106        nd.max = max(lf.max, rt.max);
107        
108    }
109}
110class MyNode{
111    int bg;
112    int ed;
113    int max = Integer.MIN_VALUE;
114    MyNode lf;
115    MyNode rt;
116    MyNode(int bg, int ed, int max){
117        this.bg = bg;
118        this.ed = ed;
119        this.max = max;
120    }
121}