y总的思路还是超出常人的， 用正常人的思路写出来的代码如下：
顺时针时， 队列是从前往后遍历， 前缀和也是从前往后
逆时针时， 队列是从后往前遍历， 后缀和也是从后往前

import java.io.*;
class Main{
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static int N = 3000010;
    static long[] s = new long[2 * N];
    static int[] o = new int[2 * N], d = new int[2 * N], h = new int[2 * N];
    static boolean[] st = new boolean[N];
    public static void main(String[] args) throws Exception{
        int n = Integer.valueOf(read.readLine());
        for(int i = 1; i <= n; i++){
            String[] ss = read.readLine().split(" ");
            o[i] = o[i + n] = Integer.valueOf(ss[0]);
            d[i] = d[i + n] = Integer.valueOf(ss[1]);
        }
        //长度为n , 顺时针
        for(int i = 1; i <= n * 2; i++) s[i] = s[i - 1] + o[i] - d[i];
        int hh = 0, tt = -1;
        for(int i = 1; i < n * 2; i++){
            if(hh <= tt && i - h[hh] + 1 > n) hh++;
            while( hh <= tt && s[h[tt]] >= s[i]) tt--;
            h[++tt] = i;
            if(i >= n){
                if(s[h[hh]] - s[i - n] >= 0) st[i - n + 1] = true;
            }
        }

        //逆时针
        hh = 0; tt = -1;
        for(int i = 2 * n; i >= 1; i--) s[i] = s[i + 1] + o[i] - d[i - 1];
        for(int i = 2 * n; i > 1; i--){
            if(hh <= tt && h[hh] - i + 1 > n) hh++;
            while(hh <= tt && s[h[tt]] >= s[i]) tt--;
            h[++tt] = i;
            if(i <= n + 1){
                if(s[h[hh]] - s[i + n] >= 0) st[i - 1] = true;
            }
        }

        for(int i = 1; i <= n; i++){
            if(st[i]) System.out.println("TAK");
            else System.out.println("NIE");
        }

    }
}

y总的思路还是超出常人的， 用正常人的思路写出来的代码如下：
顺时针时， 队列是从前往后遍历， 前缀和也是从前往后
逆时针时， 队列是从后往前遍历， 后缀和也是从后往前

import java.io.*;
class Main{
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter log  = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N = 3000010;
    static long[] s = new long[2 * N];
    static int[] o = new int[2 * N], d = new int[2 * N], h = new int[2 * N];
    static boolean[] st = new boolean[N];
    public static void main(String[] args) throws Exception{
        int n = Integer.valueOf(read.readLine());
        for(int i = 1; i <= n; i++){
            String[] ss = read.readLine().split(" ");
            o[i] = o[i + n] = Integer.valueOf(ss[0]);
            d[i] = d[i + n] = Integer.valueOf(ss[1]);
        }
        //长度为n , 顺时针
        for(int i = 1; i <= n * 2; i++) s[i] = s[i - 1] + o[i] - d[i];
        int hh = 0, tt = -1;
        for(int i = 1; i < n * 2; i++){
            if(hh <= tt && i - h[hh] + 1 > n) hh++;
            while( hh <= tt && s[h[tt]] >= s[i]) tt--;
            h[++tt] = i;
            if(i >= n){
                if(s[h[hh]] - s[i - n] >= 0) st[i - n + 1] = true;
            }
        }

        //逆时针
        hh = 0; tt = -1;
        for(int i = 2 * n; i >= 1; i--) s[i] = s[i + 1] + o[i] - d[i - 1];
        for(int i = 2 * n; i > 1; i--){
            if(hh <= tt && h[hh] - i + 1 > n) hh++;
            while(hh <= tt && s[h[tt]] >= s[i]) tt--;
            h[++tt] = i;
            if(i <= n + 1){
                if(s[h[hh]] - s[i + n] >= 0) st[i - 1] = true;
            }
        }

        for(int i = 1; i <= n; i++){
            if(st[i]) log.write("TAK\n");
            else log.write("NIE\n");
        }
        log.flush();

    }
}

import java.io.*;
class Main{
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static int N = 300010;
    static int[] a = new int[N], s = new int[N], h = new int[N];
    public static void main(String[] args) throws Exception{
        String[] ss = read.readLine().split(" ");
        int n = Integer.valueOf(ss[0]);
        int m = Integer.valueOf(ss[1]);
        ss = read.readLine().split(" ");

        for(int i = 1; i <= n; i++){
            a[i] = Integer.valueOf(ss[i - 1]);
            s[i] = s[i - 1] + a[i];
        }

        int hh = 0, tt = -1, max = Integer.MIN_VALUE;
        // 滑动窗口是从i - 1开始, 初始化h[++tt] = 0
        h[++tt] = 0;
        for(int i = 1; i <= n; i++){
            //这里的滑动窗口是从i - 1开始，长度为m的窗口
            if(i - 1 - h[hh] + 1 > m ) hh++;
            max = Math.max(s[i] - s[h[hh]], max);
            while(tt >= hh && s[h[tt]] >= s[i]) tt--;
            h[++tt] = i;
        }
        System.out.println(max);
    }
}

import java.io.*;
class Main{
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static int N = 300010;
    static int[] a = new int[N], s = new int[N], h = new int[N];
    public static void main(String[] args) throws Exception{
        String[] ss = read.readLine().split(" ");
        int n = Integer.valueOf(ss[0]);
        int m = Integer.valueOf(ss[1]);
        ss = read.readLine().split(" ");

        for(int i = 1; i <= n; i++){
            a[i] = Integer.valueOf(ss[i - 1]);
            s[i] = s[i - 1] + a[i];
        }

        int hh = 0, tt = -1, max = Integer.MIN_VALUE;
        // 滑动窗口是从i - 1开始, tt 不是从-1开始
        h[++tt] = 0;
        for(int i = 1; i <= n; i++){
            //这里的滑动窗口是从i - 1开始，长度为m的窗口
            if(i - 1 - h[hh] + 1 > m ) hh++;
            max = Math.max(s[i] - s[h[hh]], max);
            while(tt >= hh && s[h[tt]] >= s[i]) tt--;
            h[++tt] = i;
        }
        System.out.println(max);
    }
}

import java.io.*;

class Main{
    static int N = 200010, M = 18, n;
    static int[][] dp = new int[N][M];
    static int[] a;
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    public static void init(){
        for(int len = 0; len < M; len++){   
            for(int i = 1; i + (1 << len) - 1 <= n; i++){     //这里的右边界是i + (1 << len) - 1
                int j = len;
                if(len == 0) dp[i][j] = a[i];  //当2^0 = 1， 长度为1时， 最大值就是它本身
                else dp[i][j] = Math.max(dp[i][j - 1], dp[i + (1 << j - 1)][j - 1]);
            }
        }
    }

    public static int query(int L, int R){
        int len = R - L + 1;
        int k =(int)( Math.log(len) / Math.log(2) );
        int res = Math.max(dp[L][k], dp[R - (1 << k) + 1][k]);
        return res;
    }

    public static void main(String[] args) throws Exception{
         n = Integer.valueOf(read.readLine());
         a = new int[n + 1];
         String[] ss = read.readLine().split(" ");
         for(int i = 1; i <= n; i++){
             a[i] = Integer.valueOf(ss[i - 1]);
         }
         int m = Integer.valueOf(read.readLine());
         init();
         while( m -- > 0){
             ss = read.readLine().split(" ");
             int L = Integer.valueOf(ss[0]);
             int R = Integer.valueOf(ss[1]);
             System.out.println(query(L, R));
         }

    }
}

import java.io.*;

class Main{
    static int N = 200010, M = 18, n;
    static int[][] dp = new int[N][M];
    static int[] a;
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    public static void init(){
        for(int len = 0; len < M; len++){   
            for(int i = 1; i + (1 << len) - 1 <= n; i++){     //这里的右边界是i + (1 << len) - 1
                int j = len;
                if(len == 0) dp[i][j] = a[i];  //当2^0 = 1， 长度为1时， 最大值就是它本身
                else dp[i][j] = Math.max(dp[i][j - 1], dp[i + (1 << j - 1)][j - 1]);
            }
        }
    }

    public static int query(int L, int R){
        int len = R - L + 1;
        int k =(int)( Math.log(len) / Math.log(2) );
        int res = Math.max(dp[L][k], dp[R - (1 << k) + 1][k]);
        return res;
    }

    public static void main(String[] args) throws Exception{
         n = Integer.valueOf(read.readLine());
         a = new int[n + 1];
         String[] ss = read.readLine().split(" ");
         for(int i = 1; i <= n; i++){
             a[i] = Integer.valueOf(ss[i - 1]);
         }
         int m = Integer.valueOf(read.readLine());
         init();
         while( m -- > 0){
             ss = read.readLine().split(" ");
             int L = Integer.valueOf(ss[0]);
             int R = Integer.valueOf(ss[1]);
             System.out.println(query(L, R));
         }

    }
}

题目描述

Windy 定义了一种 Windy 数：不含前导零且相邻两个数字之差至少为 22 的正整数被称为 Windy 数。

Windy 想知道，在 A 和 B 之间，包括 A 和 B，总共有多少个 Windy 数？

输入格式
共一行，包含两个整数 A 和 B。

输出格式
输出一个整数，表示答案。

数据范围
1≤A≤B≤2×10^9
输入样例1：
1 10
输出样例1：
9

import java.util.*;
class Main{
    static int N = 11;
    static int[][] dp = new int[N][N];
    public static void init(){
        //总共1位， 最高位为i的个数为1
        for(int i = 0; i <= 9; i++) dp[1][i] = 1;
        for(int i = 2; i < N; i++){
            for(int j = 0; j <= 9; j++){
                for(int k = 0; k <= 9; k++){
                    if(Math.abs(j - k) >= 2)  dp[i][j] += dp[i - 1][k];
                }
            }
        }
    }

    public static int dp(int n){
        if(n == 0) return 0;
        List<Integer> list = new ArrayList();
        while(n > 0){
            list.add(n % 10);
            n /= 10;
        }
        int res = 0;
        int last = -2;
        //答案是a.size()位的
        for(int i = list.size() - 1; i >= 0; i--){
            int x = list.get(i);
            for(int j = i == list.size() - 1 ? 1: 0; j < x; j++){
                if(Math.abs(j - last) >= 2) res += dp[i + 1][j];
            }
            if(Math.abs(x - last) < 2) break;
            last = x;
            if(i == 0) res++;
        }
        //答案小于a.size()位的
        for(int i = 1; i < list.size(); i++) {
            for (int j = 1; j <= 9; j++) {
                res += dp[i][j];
            }
        }
        return res;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        init();
        int X = sc.nextInt(), Y = sc.nextInt();
        System.out.println(dp(Y) - dp(X - 1));
    }

}

import java.util.*;
class Main{
    static int N = 11;
    static int[][] dp = new int[N][N];
    public static void init(){
        //总共1位， 最高位为i的个数为1
        for(int i = 0; i <= 9; i++) dp[1][i] = 1;
        for(int i = 2; i < N; i++){
            for(int j = 0; j <= 9; j++){
                for(int k = 0; k <= 9; k++){
                    if(Math.abs(j - k) >= 2)  dp[i][j] += dp[i - 1][k];
                }
            }
        }
    }

    public static int dp(int n){
        if(n == 0) return 0;
        List<Integer> list = new ArrayList();
        while(n > 0){
            list.add(n % 10);
            n /= 10;
        }
        int res = 0;
        int last = -2;
        //答案是a.size()位的
        for(int i = list.size() - 1; i >= 0; i--){
            int x = list.get(i);
            for(int j = i == list.size() - 1 ? 1: 0; j < x; j++){
                if(Math.abs(j - last) >= 2) res += dp[i + 1][j];
            }
            if(Math.abs(x - last) < 2) break;
            last = x;
            if(i == 0) res++;
        }
        //答案小于a.size()位的
        for(int i = 1; i < list.size(); i++) {
            for (int j = 1; j <= 9; j++) {
                res += dp[i][j];
            }
        }
        return res;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        init();
        int X = sc.nextInt(), Y = sc.nextInt();
        System.out.println(dp(Y) - dp(X - 1));
    }

}

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 12;

int f[N][N];

void init(){
    for(int i = 0; i <= 9; i++) f[1][i] = 1;
    for(int i = 2; i <= N; i++){
        for(int j = 0; j <= N; j++){
            for(int k = j; k <= 9; k++){
                f[i][j] += f[i - 1][k];
            }
        }
    }
}

int dp(int n){
    if( n == 0) return 1;
    int res = 0, last = 0;
    vector<int> a;
    while(n != 0){
        a.push_back(n % 10);
        n /= 10;
    }
    for(int i = a.size() - 1; i >= 0; i--){
        int x = a[i];
        if(x < last) break;
        for(int j = last; j < x; j++){
            res += f[i + 1][j];
        }
        last = x;
        if(i == 0) res++;
    }
    return res;
}

int main(){
    init();
    int l, r;
    while(cin>>l>>r) cout<< dp(r) - dp(l - 1) << endl;
    return 0;
}

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 12;

int f[N][N];

void init(){
    for(int i = 0; i <= 9; i++) f[1][i] = 1;
    for(int i = 2; i <= N; i++){
        for(int j = 0; j <= N; j++){
            for(int k = j; k <= 9; k++){
                f[i][j] += f[i - 1][k];
            }
        }
    }
}

int dp(int n){
    if( n == 0) return 1;
    int res = 0, last = 0;
    vector<int> a;
    while(n != 0){
        a.push_back(n % 10);
        n /= 10;
    }
    for(int i = a.size() - 1; i >= 0; i--){
        int x = a[i];
        if(x < last) break;
        for(int j = last; j < x; j++){
            res += f[i + 1][j];
        }
        last = x;
        if(i == 0) res++;
    }
    return res;
}

int main(){
    init();
    int l, r;
    while(cin>>l>>r) cout<< dp(r) - dp(l - 1) << endl;
    return 0;
}