龙骑士军团【算法赛】问题描述龙骑士军团是蓝桥王国战斗力最强的军团该军团总共有 nn 位龙骑士其中第 ii 位龙骑士的战斗力为 aiai​。国王想考察一下军团长小蓝对于军团的掌控能力。具体来说国王会提出 qq 个询问每次询问给定四个整数 a,b,c,da,b,c,d并要求小蓝从区间 [a,b][a,b] 中选择一个点 LL从区间 [c,d][c,d] 中选择一个点 RR使得 ∑iLRai∑iLR​ai​ 的值最大化。这些问题难倒了小蓝。作为小蓝的助手请你帮他解决这些问题。针对每个询问你无需找出具体的 LL 和 RR只需给出 ∑iLRai∑iLR​ai​ 的最大值即可。输入格式第一行输入两个整数 n,q(1≤n,q≤2×105)n,q(1≤n,q≤2×105)表示龙骑士数量和国王的询问数量。第二行输入 nn 个整数 a1,a2,a3,⋯,an(−109≤ai≤109)a1​,a2​,a3​,⋯,an​(−109≤ai​≤109)依稀表示每位龙骑士的战斗力。接下来 qq 行每行四个整数 a,b,c,d(1≤a≤bc≤d≤n)a,b,c,d(1≤a≤bc≤d≤n)表示一次询问。输出格式输出 qq 行每行一个整数表示答案。样例输入8 3 -1 2 -3 4 -5 6 -7 8 1 2 3 4 1 1 2 2 1 3 5 8样例输出3 1 5样例说明对于第一个查询LL 我们可以选择 22RR 选择 44区间 [2,4][2,4] 的和为 33。1.暴力版本超时import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static int N2*100010; static int g[]new int[N]; static long s[]new long[N]; static int n; static BufferedReader br new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); nInteger.parseInt(st.nextToken()); int qInteger.parseInt(st.nextToken()); stnew StringTokenizer(br.readLine()); for (int i 1; i n; i) { g[i]Integer.parseInt(st.nextToken()); s[i]s[i-1]g[i]; } for (int i 0; i q; i) { stnew StringTokenizer(br.readLine()); int aInteger.parseInt(st.nextToken()),bInteger.parseInt(st.nextToken()); int cInteger.parseInt(st.nextToken()),dInteger.parseInt(st.nextToken()); long res0; int lMath.max(a, b),rMath.min(c, d); ress[r]-s[l-1]; long left0; for (int j Math.min(a, b); j l; j) { leftMath.max(left, s[l-1]-s[j-1]); } resleft; long right0; for (int j r1; j Math.max(c,d); j) { rightMath.max(right, s[j]-s[r]); } resright; bw.write(res\n); } br.close(); bw.flush(); bw.close(); } }2优化版本 ST表import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static int N2*100010; static int g[]new int[N]; static long s[]new long[N];//long 防止溢出 static int log2[]new int[N]; static int n; static BufferedReader br new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); nInteger.parseInt(st.nextToken()); int qInteger.parseInt(st.nextToken()); stnew StringTokenizer(br.readLine()); for (int i 1; i n; i) { g[i]Integer.parseInt(st.nextToken()); s[i]s[i-1]g[i]; } log2[1]0; for (int i 2; i N; i) { log2[i]log2[i1]1; } //题目可以理解为s[j]-s[i]的最大值 i属于[a,b] j属于[c,d] //只需要使得s[j]最大 s[i]最小 //构造ST表 倍增表 最大值 long f[][]new long[n1][log2[n]1]; for (int j 0; j log2[n]; j) { for (int i 0; i(1j)-1 n; i) {//要从0开始 并且要保证右边界合法 if(j0)f[i][j]s[i]; else f[i][j]Math.max(f[i][j-1],f[i(1(j-1))][j-1]); } } //构造ST表 倍增表 最小值 long f1[][]new long[n1][log2[n]1]; for (int j 0; j log2[n]; j) { for (int i 0; i(1j)-1 n; i) { if(j0)f1[i][j]s[i]; else f1[i][j]Math.min(f1[i][j-1], f1[i(1(j-1))][j-1]); } } for (int i 0; i q; i) { stnew StringTokenizer(br.readLine()); int aInteger.parseInt(st.nextToken()),bInteger.parseInt(st.nextToken()); int cInteger.parseInt(st.nextToken()),dInteger.parseInt(st.nextToken()); //找到a-1到b-1中的最小s值 int klog2[b-a1]; long leftMath.min(f1[a-1][k],f1[b-1-(1k)1][k]); //找到c到d中的最大s值 int kklog2[d-c1]; long rightMath.max(f[c][kk],f[d-(1kk)1][kk]); bw.write((right-left)\n ); } br.close(); bw.flush(); bw.close(); } }