package 蓝桥杯第九次;import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;public class 百亿富翁 {
/*
5
3 1 2 5 4*/public static void main(String[] args) throws IOException {// TODO Auto-generated method stubStreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));sc.nextToken();int n = (int)sc.nval;long a[] = new long[n+1];for(int i=1;i<=n;i++) {sc.nextToken();a[i]=(long)sc.nval;}int num1[] = new int[n+1];int num2[] = new int[n+1];Arrays.fill(num1, -1);Arrays.fill(num2, -1);Deque<Integer> q = new ArrayDeque<>();//按顺序遍历for(int i=1;i<=n;i++) {while(!q.isEmpty()&&a[q.peekLast()]<a[i]) q.pollLast();if(!q.isEmpty()) {num1[i]=q.peekLast();}q.add(i);}q.clear();//倒过来遍历就是右边第一栋比自己高for(int i=n;i>=1;i--) {while(!q.isEmpty()&&a[q.peekLast()]<a[i]) q.pollLast();if(!q.isEmpty()) {num2[i]=q.peekLast();}q.add(i);}for(int i=1;i<=n;i++) {System.out.print(num1[i]+" ");}System.out.println();for(int i=1;i<=n;i++) {System.out.print(num2[i]+" ");}}}

package 蓝桥杯第九次;import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayDeque;
import java.util.Deque;public class MAX最值差 {public static void main(String[] args) throws IOException {// TODO Auto-generated method stubStreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));sc.nextToken();int n = (int)sc.nval;sc.nextToken();int k= (int)sc.nval;int a[] = new int[n+1];for(int i=1;i<=n;i++) {sc.nextToken();a[i] = (int)sc.nval;}Deque<Integer> q = new ArrayDeque<>();int num1[] = new int[n+1];int num2[] = new int[n+1];for(int i=1;i<=n;i++) {while(!q.isEmpty()&&i-k>=q.peekFirst()) q.pollFirst();while(!q.isEmpty()&&a[i]<a[q.peekLast()]) q.pollLast();q.addLast(i);num1[i]=q.peekFirst();}q.clear();for(int i=1;i<=n;i++) {while(!q.isEmpty()&&i-k>=q.peekFirst()) q.pollFirst();while(!q.isEmpty()&&a[i]>a[q.peekLast()]) q.pollLast();q.addLast(i);num2[i]=q.peekFirst();}int max = Integer.MIN_VALUE;for(int i=1;i<=n;i++) {max = Math.max(a[num2[i]]-a[num1[i]], max);}System.out.println(max);}
/*
6 3 
4 6 5 2 3 1*/
}

package 蓝桥杯第九次;import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;public class 左移右移2 {static class Node{int val;;Node pre;Node next;public Node(int val,Node pre,Node next) {this.val = val;this.pre = pre;this.next = next;}}public static void main(String[] args) {// TODO Auto-generated method stubScanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();Map<Integer, Node> map = new HashMap<>();Node head = new Node(-1, null, null);Node tail = new Node(-1, null, null);Node pre = head;for(int i=1;i<=n;i++) {pre.next = new Node(i, pre, null);pre = pre.next;map.put(i, pre);}pre.next = tail;tail.pre = pre;while(m-->0) {char c = sc.next().charAt(0);int k = sc.nextInt();Node node = map.get(k);node.next.pre = node.pre;node.pre.next = node.next;if(c=='L') {head.next.pre = node;node.next = head.next;head.next = node;node.pre = head;}else {node.pre = tail.pre;tail.pre.next = node;node.next = tail;tail.pre = node;}}Node cur = head.next;while(cur!=tail) {System.out.print(cur.val+" ");cur = cur.next;}}}