单调栈+倍增思想 皇家守卫【算法赛】、单调队列 附近最小

皇家守卫【算法赛】问题描述在蓝桥王国的边疆有 NN​ 座高塔每座高塔上均有一个士兵他们被称之为皇家守卫。每座高塔均有一个高度第 ii 座高塔的高度为 hihi​。对于第 ii 座塔若其右边存在某座塔 jj满足max⁡(hi,hi1,hi2,⋯,hj−1)hjmax(hi​,hi1​,hi2​,⋯,hj−1​)hj​则称第 jj 座塔为第 ii 座塔 暸望塔。现在王国传来 QQ 个任务每个任务会给定两个编号 x,yx,y需要你求解第 xx 座高塔和 第 yy 座高塔的公共 暸望塔 数量。x,yx,y 的公共 暸望塔 定义为两者同时拥有的 暸望塔。输入格式第一行输入两个整数 N,Q(1≤N,Q≤105)N,Q(1≤N,Q≤105) 表示高塔个数和任务数。第二行输入 NN 个整数 h1,h2,h3,⋯,hn(1≤hi≤109)h1​,h2​,h3​,⋯,hn​(1≤hi​≤109) 表示高塔的高度。接下来 QQ 行每行输入两个整数 x,y(1≤x≤y≤N)x,y(1≤x≤y≤N) 表示一次任务询问。输出格式输出 QQ 行每行一个整数表示答案输入样例5 3 1 3 4 5 7 1 3 2 4 3 5输出样例2 1 0说明对于第一个询问第 11 座高塔和第 33 座高塔的公共暸望塔有 4,54,5 号塔。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 N100010; static int a[]new int[N]; static int next[]new int[N];//表示右边第一个比我高的高塔的索引 static int len[]new int[N];//表示 右边严格大于我的高塔的数量 static int log2[]new int[N]; static int go[][]; 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) { a[i]Integer.parseInt(st.nextToken()); } a[n1]Integer.MAX_VALUE; findMax(n); for (int i n-1; i 0 ; i--) {//从后往前遍历 if(next[i]!n1)len[i]len[next[i]]1;//要加判断语句 } log2[1]0; for (int i 2; i N; i) { log2[i]log2[i1]1; } gonew int[n2][log2[n]1];//go(i,j)表示从i出发跳2^j步得到的下标 for (int j 0; j log2[n]; j) { for (int i 1; i n; i) { if(j0)go[i][j]next[i]; else { go[i][j]go[go[i][j-1]][j-1]; } } } for (int i 0; i q; i) { stnew StringTokenizer(br.readLine()); int xInteger.parseInt(st.nextToken()),yInteger.parseInt(st.nextToken()); //题目可以理解为求x位置的瞭望塔中索引大于y塔的数量 是x的瞭望塔一定是y的 //我们可以利用倍增思想去遍历塔 int nxx; for (int k log2[n]; k 0; k--) {//这里一定要从最大步长不断递减 //当前位置能跳的最大幅度再微调能走到极限 //先挪一小步把原本能跳的大步机会直接废掉走不到最远 int nxtgo[nx][k]; if(nxty nxt!0){ nxnxt; } } bw.write(len[nx]\n); } br.close(); bw.flush(); bw.close(); } static void findMax(int n){//维护next for (int i 1; i n; i) { next[i]n1; } StackInteger stacknew Stack();//维护一个单调递减栈 for (int i n; i 1; i--) { int ua[i]; while(!stack.isEmpty() a[stack.peek()]u)stack.pop(); if(!stack.isEmpty())next[i]stack.peek(); stack.add(i); } } }附近最小问题描述小蓝有一个序列 a[1],a[2],...,a[n]a[1],a[2],...,a[n]。给定一个正整数 kk请问对于每一个 11 到 nn 之间的序号 iia[i−k],a[i−k1],...,a[ik]a[i−k],a[i−k1],...,a[ik] 这 2k12k1 个数中的最小值是多少当某个下标超过 11 到 nn 的范围时数不存在求最小值时只取存在的那些值。输入格式输入的第一行包含一整数 nn。第二行包含 nn 个整数分别表示 a[1],a[2],...,a[n]a[1],a[2],...,a[n]。第三行包含一个整数 kk 。输出格式输出一行包含 nn 个整数分别表示对于每个序号求得的最小值。样例输入5 5 2 7 4 3 1样例输出2 2 2 3 3评测用例规模与约定对于 30% 的评测用例1n10001a[i]10001n10001a[i]1000。对于 50% 的评测用例1n100001a[i]100001n100001a[i]10000。对于所有评测用例1n10000001a[i]10000001n10000001a[i]1000000。法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 N1000010; static int a[]new int[N]; static int c[]new int[2*N]; static int res[]new int[2*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()); stnew StringTokenizer(br.readLine()); for (int i 1; i n; i) { a[i]Integer.parseInt(st.nextToken()); } stnew StringTokenizer(br.readLine()); int kInteger.parseInt(st.nextToken()); int ii 1; for (; ii k; ii) { c[ii]Integer.MAX_VALUE; } for (int j1; jn; ii,j) { c[ii]a[j]; } for (int j1; j k; j,ii) { c[ii]Integer.MAX_VALUE; } for (int i 1; i ii; i) { res[i]Integer.MAX_VALUE; } DequeInteger dequenew LinkedListInteger();//维护一个单调递增的队列 for (int i 1; i ii; i) { int uc[i]; //清除过期数据 while(!deque.isEmpty() i-deque.getFirst()2*k1)deque.pollFirst(); //维护队列 while(!deque.isEmpty() c[deque.peekLast()]u)deque.pollLast(); deque.add(i); res[i]deque.peek(); } for (int i 2*k1,j1; jn; j,i) {//注意开始下标 bw.write(c[res[i]] ); } 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.*; public class Main { static int N1000010; static int a[]new int[N]; static int res[]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()); stnew StringTokenizer(br.readLine()); for (int i 1; i n; i) { a[i]Integer.parseInt(st.nextToken()); } stnew StringTokenizer(br.readLine()); int kInteger.parseInt(st.nextToken()); DequeInteger dequenew LinkedListInteger();//维护一个单调递增的队列 int right0;//当前已经处理过的右边界 for (int i 1; i n; i) {//枚举每个中心点 int lMath.max(1, i-k),rMath.min(n, ik);//保证合法索引 //清除过期数据 if(!deque.isEmpty() deque.getFirst()l)deque.pollFirst();//每次左移一个单位 不用写成循环 //把属于l到r范围的数据添加进去 while(rightr){ right; while(!deque.isEmpty() a[deque.peekLast()]a[right])deque.pollLast(); deque.add(right); } res[i]deque.peekFirst(); } for (int i 1; i n; i) { bw.write(a[res[i]] ); } br.close(); bw.flush(); bw.close(); } }