Description

Little Ming很喜歡訓(xùn)練自己的快速讀能力，他最近找到一種新的考驗(yàn)并訓(xùn)練快速讀能力的方法，在一行具有很多數(shù)的數(shù)列里任意指定某一段長(zhǎng)度，從左往右掃視一遍后說(shuō)出這段數(shù)列中的最大值，但他不想一直只使用一個(gè)數(shù)列，所以他請(qǐng)了他的好朋友，一位非常喜歡編程的學(xué)生，Little Little來(lái)幫忙在原數(shù)列上時(shí)不時(shí)的做一些修改，給他出題并檢驗(yàn)他的答案是否正確。Little Little在做修改操作時(shí)會(huì)選取某個(gè)點(diǎn)修改它的值，在做出題操作時(shí)給出某一段的左右端點(diǎn)。

Input

本題目包含多組測(cè)試，請(qǐng)?zhí)幚淼轿募Y(jié)束。

在每個(gè)測(cè)試的第一行，有兩個(gè)正整數(shù) N 和 M (  0<N<=200000,0<M<5000 )

第二行包含N個(gè)整數(shù)，代表初始時(shí)數(shù)列中的數(shù)據(jù)。

接下來(lái)有M行。每一行有一個(gè)字符 C (只取'Q'或'S') ，和兩個(gè)正整數(shù)A，B。

當(dāng)C為'Q'的時(shí)候，表示這是一條出題操作，A,B為端點(diǎn)下標(biāo)值，有可能A比B大。

當(dāng)C為'S'的時(shí)候，表示這是一條修改操作，要求把第A個(gè)數(shù)修改為B。

Output

對(duì)于每一次出題操作，在一行里面輸出最大的數(shù)。

相鄰2組測(cè)試之間要有一個(gè)空行。

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



這是一道再基礎(chǔ)不過(guò)的線段樹(shù)題了，不多贅述，相見(jiàn)代碼及注釋。可先參閱：http://www.shnenglu.com/hoolee/archive/2012/07/29/185531.html
細(xì)節(jié)：題目中說(shuō)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];//動(dòng)態(tài)分配空間很耗時(shí)，先用數(shù)組A[]申請(qǐng)足夠大的空間。
 13int count = 0;//記錄A[]數(shù)組的使用情況，指向最后一個(gè)使用節(jié)點(diǎn)
 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[]節(jié)點(diǎn)的位置。
 25    * 建樹(shù)過(guò)程為： 1.先有根節(jié)點(diǎn)，2.再建左右子樹(shù)，3.然后修改根節(jié)點(diǎn)的子樹(shù)指針
 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;//開(kāi)辟空間
 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        給定區(qū)間[bg, ed]，查詢區(qū)間的最大值，
 50        [bg, ed]區(qū)間與t節(jié)點(diǎn)代表的區(qū)間有四種關(guān)系：（令(A[t].bg + A[t].ed) / 2）
 51        1.他倆是同一個(gè)區(qū)間，查詢成功，返回A[t].max
 52        2.bg <= mid, 接著查詢t的左子樹(shù)
 53        3.ed > min，接著查詢t的右子樹(shù)
 54        4.否認(rèn)則，同時(shí)查詢t的左右子樹(shù)
 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指向當(dāng)前節(jié)點(diǎn)，p是要修改的位置，b為值
 79        分為3中情況：
 80        1.A[ap]為葉子節(jié)點(diǎn)，修改A[ap].max為b
 81        2.p在ap的左子樹(shù)上，去左子樹(shù)上查詢
 82        3.p在ap的右子樹(shù)上，去右子樹(shù)上查詢
 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);//子樹(shù)的max改變了，也要修改父節(jié)點(diǎn)的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

 其實(shí)這道題我先是用java寫(xiě)的，TLE，同樣的思想，用C++寫(xiě)，410MS AC。下面是超時(shí)的java代碼，可能是new太耗時(shí)了。

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}