目錄
題目描述
輸入描述
輸出描述
輸入輸出樣例
示例
輸入
輸出
運行限制
原題鏈接
代碼思路
題目描述
在一條 R 河流域，繁衍著一個古老的名族 Z。他們世代沿河而居，也在河邊發展出了璀璨的文明。
Z 族在 R 河沿岸修建了很多建筑，最近，他們熱衷攀比起來。他們總是在比誰的建筑建得最奇特。
幸好 Z 族人對奇特的理解都差不多，他們很快給每棟建筑都打了分，這樣評選誰最奇特就輕而易舉了。
于是，根據分值，大家很快評出了最奇特的建筑，稱為大奇跡。
后來他們又陸續評選了第二奇特、第二奇特、......、第七奇特的建筑，依次稱為第二大奇跡、第三大奇跡、......、第七大奇跡。
最近，他們開始評選第八奇特的建筑，準備命名為第八大奇跡。
在評選中，他們遇到了一些問題。
首先，Z 族一直在發展，有的建筑被拆除又建了新的建筑，新建筑的奇特值和原建筑不一樣，這使得評選不那么容易了。
其次，Z 族的每個人所生活的范圍可能不一樣，他們見過的建筑并不是所有的建筑，他們堅持他們自己所看到的第八奇特的建筑就是第八大奇跡。
Z 族首領最近很頭疼這個問題，他害怕因為意見不一致導致 Z 族發生分歧。他找到你，他想先了解一下，民眾自己認為的奇跡是怎樣的。
現在告訴在 R 河周邊的建筑的變化情況，以及在變化過程中一些人的生活范圍，請編程求出每個人認為的第八大奇跡的奇特值是多少。
輸入描述
輸入的第一行包含兩個整數?𝐿,𝑁L,N，分別表示河流的長度和要你處理的信息的數量。開始時河流沿岸沒有建筑，或者說所有的奇特值為 0。
接下來?𝑁N?行，每行一條你要處理的信息。
如果信息為?𝐶?𝑝?𝑥C?p?x，表示流域中第?𝑝?(1≤𝑝≤𝐿)p?(1≤p≤L)?個位置建立了一個建筑，其奇特值為?𝑥x。如果這個位置原來有建筑，原來的建筑會被拆除。
如果信息為?𝑄?𝑎?𝑏Q?a?b，表示有個人生活的范圍是河流的第?𝑎a?到?𝑏b?個位置（包含?𝑎a?和?𝑏b，𝑎≤𝑏a≤b），這時你要算出這個區間的第八大奇跡的奇特值，并輸出。如果找不到第八大奇跡，輸出 0。
其中，1≤𝐿≤105，1≤𝑁≤1051≤L≤105，1≤N≤105。所有奇特值為 不超過?109109?的非負整數。
輸出描述
對于每個為 Q 的信息，你需要輸出一個整數，表示區間中第八大奇跡的奇特值。
輸入輸出樣例
示例
輸入
10 15
C 1 10
C 2 20
C 3 30
C 4 40
C 5 50
C 6 60
C 7 70
C 8 80
C 9 90
C 10 100
Q 1 2
Q 1 10
Q 1 8
C 10 1
Q 1 10輸出
0
30
10
20運行限制
- 最大運行時間：1s
- 最大運行內存: 256M
原題鏈接
第八大奇跡
https://www.lanqiao.cn/problems/242/learning/?page=1&first_category_id=1&name=%E7%AC%AC%E5%85%AB%E5%A4%A7%E5%A5%87%E8%BF%B9
代碼思路
import java.util.Scanner;public class Main {static Tree[] trees;public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int L = scanner.nextInt();int N = scanner.nextInt();// 注意線段樹的長度要是存入長度(L)的四倍;trees = new Tree[L << 2];// 構建線段樹structure(1, 1, L);while (N-- > 0) {String temp1 = scanner.next();int temp2 = scanner.nextInt();int temp3 = scanner.nextInt();if (temp1.equals("C")) {renew(1, temp2, temp3);} else {System.out.println(query(1, temp2, temp3)[7]);}}}// 構建線段樹static void structure(int k, int left, int right) {trees[k] = new Tree(left, right);if (left == right) {return;}int mid = (left + right) >> 1;structure(k << 1, left, mid);structure(k << 1 | 1, mid + 1, right);}// 修改線段樹里的數組static int[] modify(int num1[], int num2[]) {int num3[] = new int[8];int a = 0;int b = 0;for (int i = 0; i < num3.length; i++) {// 從兩個子節點的數組中賦較大的值給父節點if (num1[a] > num2[b]) {num3[i] = num1[a++];} else {num3[i] = num2[b++];}}return num3;}// 更新線段樹static void renew(int k, int i, int value) {if (trees[k].left == trees[k].right) {trees[k].num[0] = value;return;}int mid = (trees[k].left + trees[k].right) >> 1;if (mid >= i) {renew(k << 1, i, value);} else {renew(k << 1 | 1, i, value);}// 更新父親節點的數組trees[k].num = modify(trees[k << 1].num, trees[k << 1 | 1].num);}// 查詢線段樹static int[] query(int k, int left, int right) {if (trees[k].left >= left && trees[k].right <= right) {return trees[k].num;}int mid = (trees[k].left + trees[k].right) >> 1;int num[] = new int[8];if (mid >= left) {num = modify(num, query(k << 1, left, right));}if (mid < right) {num = modify(num, query(k << 1 | 1, left, right));}return num;}}class Tree {int left;int right;// 每個節點存一個數組int num[] = new int[8];public Tree(int left, int right) {super();this.left = left;this.right = right;}}
)
)
)