单调栈、单调队列（模板）、子矩阵（模板）

单调栈问题描述给定一个长度为 NN的序列 aa。第一行输出每个数字其左边第一个比其大的数字不存在则输出-1。第二行输出每个数字其右边第一个比其大的数字不存在则输出-1。第三行输出每个数字其左边第一个比其小的数字不存在则输出-1。第四行输出每个数字其右边第一个比其小的数字不存在则输出-1。update本题数据于 2025-01-13 加强至 2×1052×105以杜绝暴力通过。输入格式第一行输入一个正整数 NN。(1≤N≤2×105)(1≤N≤2×105)第二行输入 NN个正整数表示序列 aa。(1≤ai≤105,1≤i≤N)(1≤ai​≤105,1≤i≤N)输出格式第一行输出每个数字其左边第一个比其大的数字不存在则输出-1。第二行输出每个数字其右边第一个比其大的数字不存在则输出-1。第三行输出每个数字其左边第一个比其小的数字不存在则输出-1。第四行输出每个数字其右边第一个比其小的数字不存在则输出-1。样例输入5 4 3 2 1 5样例输出-1 4 3 2 -1 5 5 5 5 -1 -1 -1 -1 -1 1 3 2 1 -1 -1import 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,mod998244353; static int a[]new 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()); int nInteger.parseInt(st.nextToken()); stnew StringTokenizer(br.readLine()); for (int i 0; i n; i) { a[i]Integer.parseInt(st.nextToken()); } //输出每个数字其左边第一个比其大的数字 StackInteger stacknew StackInteger();//维护一个单调递减的栈 存 int r1[]new int[n]; Arrays.fill(r1, -1); for (int i 0; i n; i) { int ua[i]; while(!stack.isEmpty() stack.peek()u){ stack.pop(); } if(!stack.isEmpty())r1[i]stack.peek(); stack.add(u); } for (int i 0; i n ; i) { bw.write(r1[i] ); } bw.write(\n); //输出每个数字其右边第一个比其大的数字 StackInteger stack1new StackInteger();//维护一个单调递减的栈 int r2[]new int[n]; Arrays.fill(r2, -1); for (int i n-1; i 0; i--) { int ua[i]; while(!stack1.isEmpty() stack1.peek()u){ stack1.pop(); } if(!stack1.isEmpty())r2[i]stack1.peek(); stack1.add(u); } for (int i 0; i n ; i) { bw.write(r2[i] ); } bw.write(\n); //输出每个数字其左边第一个比其小的数字 StackInteger stack2new StackInteger();//维护一个单调递增的栈 int r3[]new int[n]; Arrays.fill(r3, -1); for (int i 0; i n; i) { int ua[i]; while(!stack2.isEmpty() stack2.peek()u){ stack2.pop(); } if(!stack2.isEmpty())r3[i]stack2.peek(); stack2.add(u); } for (int i 0; i n ; i) { bw.write(r3[i] ); } bw.write(\n); //输出每个数字其右边第一个比其小的数字 StackInteger stack3new StackInteger();//维护一个单调递增的栈 int r4[]new int[n]; Arrays.fill(r4, -1); for (int i n-1; i 0; i--) { int ua[i]; while(!stack3.isEmpty() stack3.peek()u){ stack3.pop(); } if(!stack3.isEmpty())r4[i]stack3.peek(); stack3.add(u); } for (int i 0; i n ; i) { bw.write(r4[i] ); } bw.write(\n); br.close(); bw.flush(); bw.close(); } }单调队列模板问题描述给定一个长度为 NN 的序列 aa 与一个长度为 KK 的窗口。(1≤K≤N)(1≤K≤N)该窗口会从序列的最左端滑动到最右端你需要输出 22 行每行 N−K1N−K1 个数字。第 11 行为每个窗口的最小值。第 22 行为每个窗口的最大值。输入格式第一行输入两个正整数 N,KN,K。(1≤K≤N≤105)(1≤K≤N≤105)第二行输入 NN 个正整数表示序列 aa。(1≤ai≤105)(1≤ai​≤105)输出格式输出 22 行每行 N−K1N−K1 个数字。第 11 行为每个窗口的最小值。第 22 行为每个窗口的最大值。样例输入8 3 1 3 1 3 5 3 6 7样例输出1 1 1 3 3 3 3 3 5 5 6 7import 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 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()); int nInteger.parseInt(st.nextToken()),kInteger.parseInt(st.nextToken()); stnew StringTokenizer(br.readLine()); for (int i 0; i n; i) { a[i]Integer.parseInt(st.nextToken()); } //求每个窗口的最小值 DequeInteger dequenew LinkedListInteger();//维护一个单调递增的队列 存下标 for (int i 0; i n; i) { int ua[i]; //清除过期数据 while(!deque.isEmpty() i-deque.getFirst()k)deque.pop(); //维护单调性 while(!deque.isEmpty() a[deque.getLast()]u){ deque.pollLast(); } deque.add(i); if(ik-1){//数量不够不可输出 bw.write(a[deque.peekFirst()] ); } } bw.write(\n); //求每个窗口的最大值 DequeInteger deque1new LinkedListInteger();//维护一个单调递减的队列 存下标 for (int i 0; i n; i) { int ua[i]; //清除过期数据 while(!deque1.isEmpty() i-deque1.getFirst()k)deque1.pop(); //维护单调性 while(!deque1.isEmpty() a[deque1.getLast()]u){ deque1.pollLast(); } deque1.add(i); if(ik-1){//数量不够不可输出 bw.write(a[deque1.peekFirst()] ); } } bw.write(\n); br.close(); bw.flush(); bw.close(); } }子矩阵模板问题描述给定一个 n×mn×m nn 行 mm 列的矩阵。设一个矩阵的价值为其所有数中的最大值和最小值的乘积。求给定矩阵的所有大小为 a×ba×b aa 行 bb 列的子矩阵的价值的和。答案可能很大你只需要输出答案对 998244353998244353 取模后的结果。输入格式输入的第一行包含四个整数分别表示 nnmmaabb相邻整数之间使用一个空格分隔。接下来nn 行每行包含 mm 个整数相邻整数之间使用一个空格分隔表示矩阵中的每个数 Ai,jAi,j​。输出格式输出一行包含一个整数表示答案。样例输入2 3 1 2 1 2 3 4 5 6样例输出样例说明1×22×34×55×6581×22×34×55×658。评测用例规模与约定对于 4040% 的评测用例1≤n,m≤1001≤n,m≤100对于 7070% 的评测用例1≤n,m≤5001≤n,m≤500对于所有评测用例1≤a≤n≤10001≤a≤n≤10001≤b≤m≤10001≤b≤m≤10001≤Ai,j≤1091≤Ai,j​≤109。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 N1010,mod998244353; static int u[][]new int[N][N]; static int rowWindowMax[][]new int[N][N]; static int rowWindowMin[][]new int[N][N]; static int WindowMax[][]new int[N][N]; static int WindowMin[][]new int[N][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()); int nInteger.parseInt(st.nextToken()),mInteger.parseInt(st.nextToken()); int aInteger.parseInt(st.nextToken()),bInteger.parseInt(st.nextToken()); for (int i 0; i n; i) { stnew StringTokenizer(br.readLine()); for (int j 0; j m; j) { u[i][j]Integer.parseInt(st.nextToken()); } } //求最大值 for (int i 0; i n; i) { //对于每一行 维护一个长度为b的滑动窗口 DequeInteger dequenew LinkedListInteger(); for (int j 0; j m; j) { int gu[i][j]; //清除过期数据 while(!deque.isEmpty() j-deque.peek()b)deque.poll(); //维护单调队列 while(!deque.isEmpty() u[i][deque.getLast()]g)deque.pollLast(); deque.add(j); if(!deque.isEmpty())rowWindowMax[i][j]u[i][deque.peek()]; } } //求最小值 for (int i 0; i n; i) { //对于每一行 维护一个长度为b的滑动窗口 DequeInteger dequenew LinkedListInteger(); for (int j 0; j m; j) { int gu[i][j]; //清除过期数据 while(!deque.isEmpty() j-deque.peek()b)deque.poll(); //维护单调队列 while(!deque.isEmpty() u[i][deque.getLast()]g)deque.pollLast(); deque.add(j); if(!deque.isEmpty())rowWindowMin[i][j]u[i][deque.peek()]; } } for (int i 0; i m; i) { //对于每一列 维护一个长度为a的滑动窗口 DequeInteger dequenew LinkedListInteger(); for (int j 0; j n; j) { int growWindowMax[j][i]; //清除过期数据 while(!deque.isEmpty() j-deque.peek()a)deque.poll(); //维护单调队列 while(!deque.isEmpty() rowWindowMax[deque.getLast()][i]g)deque.pollLast(); deque.add(j); if(!deque.isEmpty())WindowMax[j][i]rowWindowMax[deque.peek()][i]; } } for (int i 0; i m; i) { //对于每一列 维护一个长度为a的滑动窗口 DequeInteger dequenew LinkedListInteger(); for (int j 0; j n; j) { int growWindowMin[j][i]; //清除过期数据 while(!deque.isEmpty() j-deque.peek()a)deque.poll(); //维护单调队列 while(!deque.isEmpty() rowWindowMin[deque.getLast()][i]g)deque.pollLast(); deque.add(j); if(!deque.isEmpty())WindowMin[j][i]rowWindowMin[deque.peek()][i]; } } long res0; for (int i a-1; i n; i) { for (int j b-1; j m; j) { res(res(long)WindowMax[i][j]*WindowMin[i][j]%mod)%mod; } } bw.write(res); br.close(); bw.flush(); bw.close(); } }