天才的记忆

天才的记忆从前有个人名叫 WNB他有着天才般的记忆力他珍藏了许多许多的宝藏。在他离世之后留给后人一个难题专门考验记忆力的啊如果谁能轻松回答出这个问题便可以继承他的宝藏。题目是这样的给你一大串数字编号为 1 到 N大小可不一定哦在你看过一遍之后它便消失在你面前随后问题就出现了给你 M 个询问每次询问就给你两个数字 A,B要求你瞬间就说出属于 A 到 B 这段区间内的最大数。一天一位美丽的姐姐从天上飞过看到这个问题感到很有意思主要是据说那个宝藏里面藏着一种美容水喝了可以让这美丽的姐姐更加迷人于是她就竭尽全力想解决这个问题。但是她每次都以失败告终因为这数字的个数是在太多了于是她请天才的你帮他解决。如果你帮她解决了这个问题可是会得到很多甜头的哦输入格式第一行一个整数 N 表示数字的个数。接下来一行为 N 个数表示数字序列。第三行读入一个 M表示你看完那串数后需要被提问的次数。接下来 M 行每行都有两个整数 A,B。输出格式输出共 M 行每行输出一个数表示对一个问题的回答。数据范围1≤N≤2×105,1≤M≤104,1≤A≤B≤N。输入样例6 34 1 8 123 3 2 4 1 2 1 5 3 4 2 3输出样例34 123 123 8代码1ST表import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer; public class Main { static int N2*100010; static int n,m; // static int dx[]{-1,0,1,0}; // static int dy[]{0,1,0,-1}; static int a[]new int[N]; static int f[][]; public static void main(String[] args) throws IOException { BufferedReader brnew BufferedReader(new InputStreamReader(System.in)); BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); StringTokenizer stnew StringTokenizer(br.readLine()); nInteger.parseInt(st.nextToken()); //mInteger.parseInt(st.nextToken()); stnew StringTokenizer(br.readLine()); for (int i 1; i n; i) { a[i]Integer.parseInt(st.nextToken()); } //ST表 int log2[]new int[n1]; for (int i 2; i n; i) { log2[i]log2[i/2]1; } fnew int[n1][log2[n]1]; //f[i][j]表示起点为i 区间长度为2^j的 区间的最大值 for (int j 0; j log2[n] ; j) { for (int i 1; i n i(1j)-1n; i) { if(j0)f[i][0]a[i]; //这里相等于把j分成两半 先求每一半的最值 再最后求一个均值 else f[i][j]Math.max(f[i][j-1], f[i(1(j-1))][j-1]); } } stnew StringTokenizer(br.readLine()); mInteger.parseInt(st.nextToken()); for (int i 0; i m; i) { stnew StringTokenizer(br.readLine()); int lInteger.parseInt(st.nextToken()),rInteger.parseInt(st.nextToken()); int klog2[r-l1]; int resMath.max(f[l][k], f[r-(1k)1][k]); bw.write(res\n); } br.close(); bw.flush(); bw.close(); } }代码2线段树import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer; public class Main { static int N2*100010; static int n,m; // static int dx[]{-1,0,1,0}; // static int dy[]{0,1,0,-1}; static int tree[]new int[4*N]; static int a[]new int[N]; //static int f[][]; public static void main(String[] args) throws IOException { BufferedReader brnew BufferedReader(new InputStreamReader(System.in)); BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); StringTokenizer stnew StringTokenizer(br.readLine()); nInteger.parseInt(st.nextToken()); //mInteger.parseInt(st.nextToken()); stnew StringTokenizer(br.readLine()); for (int i 1; i n; i) { a[i]Integer.parseInt(st.nextToken()); } build(1,1,n); stnew StringTokenizer(br.readLine()); mInteger.parseInt(st.nextToken()); for (int i 0; i m; i) { stnew StringTokenizer(br.readLine()); int lInteger.parseInt(st.nextToken()),rInteger.parseInt(st.nextToken()); bw.write(query(1,1,n,l,r)\n);; } br.close(); bw.flush(); bw.close(); } static int query(int id,int curl,int curr,int l,int r){ if(curll currr)return tree[id]; int mid(curlcurr)1; int resInteger.MIN_VALUE; if(lmid)resMath.max(res, query(2*id, curl, mid, l, r)); if(rmid1)resMath.max(res, query(2*id1, mid1, curr, l, r)); return res; } static void pushup(int id){ tree[id]Math.max(tree[2*id], tree[2*id1]); } static void build(int id,int l,int r){ if(lr){ tree[id]a[l]; return; } int mid(lr)1; build(2*id, l, mid); build(2*id1, mid1, r); pushup(id); } }