单调栈

问题描述

给定一个长度为 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 -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 N=2*100010,mod=998244353; static int a[]=new int[N]; static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer st=new StringTokenizer(br.readLine()); int n=Integer.parseInt(st.nextToken()); st=new StringTokenizer(br.readLine()); for (int i = 0; i < n; i++) { a[i]=Integer.parseInt(st.nextToken()); } //输出每个数字其左边第一个比其大的数字 Stack<Integer> stack=new Stack<Integer>();//维护一个单调递减的栈 存 int r1[]=new int[n]; Arrays.fill(r1, -1); for (int i = 0; i < n; i++) { int u=a[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"); //输出每个数字其右边第一个比其大的数字 Stack<Integer> stack1=new Stack<Integer>();//维护一个单调递减的栈 int r2[]=new int[n]; Arrays.fill(r2, -1); for (int i = n-1; i >=0; i--) { int u=a[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"); //输出每个数字其左边第一个比其小的数字 Stack<Integer> stack2=new Stack<Integer>();//维护一个单调递增的栈 int r3[]=new int[n]; Arrays.fill(r3, -1); for (int i = 0; i < n; i++) { int u=a[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"); //输出每个数字其右边第一个比其小的数字 Stack<Integer> stack3=new Stack<Integer>();//维护一个单调递增的栈 int r4[]=new int[n]; Arrays.fill(r4, -1); for (int i = n-1; i >=0; i--) { int u=a[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−K+1N−K+1 个数字。

第 11 行为每个窗口的最小值。

第 22 行为每个窗口的最大值。

输入格式

第一行输入两个正整数 N,KN,K。(1≤K≤N≤105)(1≤K≤N≤105)

第二行输入 NN 个正整数，表示序列 aa。(1≤ai≤105)(1≤ai​≤105)

输出格式

输出 22 行，每行 N−K+1N−K+1 个数字。

第 11 行为每个窗口的最小值。

第 22 行为每个窗口的最大值。

样例输入

8 3 1 3 1 3 5 3 6 7

样例输出

1 1 1 3 3 3 3 3 5 5 6 7

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 N=100010; static int a[]=new int[N]; static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer st=new StringTokenizer(br.readLine()); int n=Integer.parseInt(st.nextToken()),k=Integer.parseInt(st.nextToken()); st=new StringTokenizer(br.readLine()); for (int i = 0; i < n; i++) { a[i]=Integer.parseInt(st.nextToken()); } //求每个窗口的最小值 Deque<Integer> deque=new LinkedList<Integer>();//维护一个单调递增的队列 存下标 for (int i = 0; i < n; i++) { int u=a[i]; //清除过期数据 while(!deque.isEmpty() && i-deque.getFirst()>=k)deque.pop(); //维护单调性 while(!deque.isEmpty() && a[deque.getLast()]>=u){ deque.pollLast(); } deque.add(i); if(i>=k-1){//数量不够不可输出 bw.write(a[deque.peekFirst()]+" "); } } bw.write("\n"); //求每个窗口的最大值 Deque<Integer> deque1=new LinkedList<Integer>();//维护一个单调递减的队列 存下标 for (int i = 0; i < n; i++) { int u=a[i]; //清除过期数据 while(!deque1.isEmpty() && i-deque1.getFirst()>=k)deque1.pop(); //维护单调性 while(!deque1.isEmpty() && a[deque1.getLast()]<=u){ deque1.pollLast(); } deque1.add(i); if(i>=k-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 取模后的结果。

输入格式

输入的第一行包含四个整数分别表示 nn，mm，aa，bb，相邻整数之间使用一个空格分隔。接下来

nn 行每行包含 mm 个整数，相邻整数之间使用一个空格分隔，表示矩阵中的每个数 Ai,jAi,j​。

输出格式

输出一行包含一个整数表示答案。

样例输入

2 3 1 2 1 2 3 4 5 6

样例输出

样例说明

1×2+2×3+4×5+5×6=581×2+2×3+4×5+5×6=58。

评测用例规模与约定

对于 4040% 的评测用例，1≤n,m≤1001≤n,m≤100；

对于 7070% 的评测用例，1≤n,m≤5001≤n,m≤500；

对于所有评测用例，1≤a≤n≤10001≤a≤n≤1000，1≤b≤m≤10001≤b≤m≤1000，1≤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 N=1010,mod=998244353; 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 bw=new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer st=new StringTokenizer(br.readLine()); int n=Integer.parseInt(st.nextToken()),m=Integer.parseInt(st.nextToken()); int a=Integer.parseInt(st.nextToken()),b=Integer.parseInt(st.nextToken()); for (int i = 0; i < n; i++) { st=new 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的滑动窗口 Deque<Integer> deque=new LinkedList<Integer>(); for (int j = 0; j < m; j++) { int g=u[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的滑动窗口 Deque<Integer> deque=new LinkedList<Integer>(); for (int j = 0; j < m; j++) { int g=u[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的滑动窗口 Deque<Integer> deque=new LinkedList<Integer>(); for (int j = 0; j < n; j++) { int g=rowWindowMax[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的滑动窗口 Deque<Integer> deque=new LinkedList<Integer>(); for (int j = 0; j < n; j++) { int g=rowWindowMin[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 res=0; 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(); } }