Submission #74707161

---

Source Code Expand

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.IOException;
import java.io.PrintWriter;

@SuppressWarnings("DuplicatedCode")
public class Main {
    static int MAX_STRING_LENGTH = (int) 1e6; // 字符串最大长度
    static int MAX_DIGIT_LENGTH = (int) 1e6; // 数位最大长度
    static int MOD7 = (int) 1e9 + 7, MOD8 = 80112002, MOD9 = 998244353, inf = Integer.MAX_VALUE;

    /***** 检查 T *****/
    static class Solution {

        void solve() {
            int n = io.nextInt();
            long k = io.nextLong();
            int[] a = io.nextIntArray(n);
            long ans = 0;
            long cntl = 0, cntr = 0;
            Fenwick ltree = new Fenwick(n + 1), rtree = new Fenwick(n + 1);
            int l = 0, r = 0;
            for (int i = 0; i < n; i++) {
                int x = a[i];
                cntl += ltree.query(x + 1, n);
                ltree.add(x, 1);
                while (l < i && cntl > k) {
                    int v = a[l];
                    cntl -= ltree.pre(v - 1);
                    ltree.add(v, -1);
                    l++;
                }

                cntr += rtree.query(x + 1, n);
                rtree.add(x, 1);
                while (r <= i && cntr >= k) {
                    int v = a[r];
                    cntr -= rtree.pre(v - 1);
                    rtree.add(v, -1);
                    r++;
                }

                if (cntl == k) ans += r - l;
            }
            io.println(ans);
        }

        static class Fenwick {
            int[] tree;
            int n;

            Fenwick(int n) {
                tree = new int[n + 1];
                this.n = n + 1;
            }

            void add(int i, int v) {
                for (i++; i < n; i += i & -i) {
                    tree[i] += v;
                }
            }

            int query(int l, int r) {
                return pre(r) - pre(l - 1);
            }

            int pre(int i) {
                int s = 0;
                for (i++; i > 0; i &= i - 1) {
                    s += tree[i];
                }
                return s;
            }
        }


    }


    public static void main(String[] args) {
        io = new IO();
        int T = 1;
        // T = io.nextInt();
        for (; T > 0; T--) {
            new Solution().solve();
        }
        io.close();
    }

    static IO io;
    static class IO {
        BufferedInputStream bis = new BufferedInputStream(System.in);
        PrintWriter pw = new PrintWriter(new BufferedOutputStream(System.out));

        int nextInt() {
            return (int) nextLong();
        }

        long nextLong() {
            try {
                long sign = 1, x = 0;
                int c = bis.read();
                while (c < '0' || c > '9') {
                    if (c == '-') sign = -1;
                    c = bis.read();
                }
                while (c >= '0' && c <= '9') {
                    x = x * 10 + (c - '0');
                    c = bis.read();
                }
                return sign * x;
            } catch (IOException e) {
                throw new RuntimeException(e.getMessage());
            }
        }

        int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                try {
                    int sign = 1, x = 0;
                    int c = bis.read();
                    while (c < '0' || c > '9') {
                        if (c == '-') sign = -1;
                        c = bis.read();
                    }
                    while (c >= '0' && c <= '9') {
                        x = x * 10 + (c - '0');
                        c = bis.read();
                    }
                    a[i] = sign * x;
                } catch (IOException e) {
                    throw new RuntimeException(e.getMessage());
                }
            }
            return a;
        }

        long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                try {
                    long sign = 1, x = 0;
                    int c = bis.read();
                    while (c < '0' || c > '9') {
                        if (c == '-') sign = -1;
                        c = bis.read();
                    }
                    while (c >= '0' && c <= '9') {
                        x = x * 10 + (c - '0');
                        c = bis.read();
                    }
                    a[i] = sign * x;
                } catch (IOException e) {
                    throw new RuntimeException(e.getMessage());
                }
            }
            return a;
        }

        int[] nextDigitArray(int n) {
            try {
                int[] a = new int[n];
                int x = bis.read();
                while (ignore(x)) {
                    x = bis.read();
                }
                int i = 0;
                while (!ignore(x)) {
                    a[i++] = x - '0';
                    x = bis.read();
                }
                return a;
            } catch (Exception e) {
                throw new RuntimeException(e.getMessage());
            }
        }

        private int[] DIGIT_ARRAY;

        int[] nextDigitArray() {
            try {
                if (DIGIT_ARRAY == null) {
                    DIGIT_ARRAY = new int[MAX_DIGIT_LENGTH];
                }
                int x = bis.read();
                while (ignore(x)) {
                    x = bis.read();
                }
                int m = 0;
                while (!ignore(x)) {
                    DIGIT_ARRAY[m++] = x - '0';
                    x = bis.read();
                }
                int[] a = new int[m];
                System.arraycopy(DIGIT_ARRAY, 0, a, 0, m);
                return a;
            } catch (Exception e) {
                throw new RuntimeException(e.getMessage());
            }
        }

        char nextChar() {
            try {
                int x = bis.read();
                while (ignore(x)) {
                    x = bis.read();
                }
                return (char) x;
            } catch (Exception e) {
                throw new RuntimeException(e.getMessage());
            }
        }

        String[] nextStringArray(int n) {
            String[] a = new String[n];
            for (int i = 0; i < n; i++) {
                try {
                    if (CHAR_ARRAY == null) {
                        CHAR_ARRAY = new char[MAX_STRING_LENGTH];
                    }
                    int x = bis.read();
                    while (ignore(x)) {
                        x = bis.read();
                    }
                    int m = 0;
                    while (x != ' ' && x != ',' && !ignore(x)) {
                        CHAR_ARRAY[m++] = (char) x;
                        x = bis.read();
                    }
                    a[i] = new String(CHAR_ARRAY, 0, m);
                } catch (IOException e) {
                    throw new RuntimeException(e.getMessage());
                }
            }
            return a;
        }

        private char[] CHAR_ARRAY;

        char[] nextCharArray(boolean line) {
            try {
                if (CHAR_ARRAY == null) {
                    CHAR_ARRAY = new char[MAX_STRING_LENGTH];
                }
                int x = bis.read();
                while (ignore(x)) {
                    x = bis.read();
                }
                int m = 0;
                while (line ? (x == ' ' || x == ',' || !ignore(x)) : !ignore(x)) {
                    CHAR_ARRAY[m++] = (char) x;
                    x = bis.read();
                }
                char[] a = new char[m];
                System.arraycopy(CHAR_ARRAY, 0, a, 0, m);
                return a;
            } catch (Exception e) {
                throw new RuntimeException(e.getMessage());
            }
        }

        char[] nextCharArray(int n) {
            try {
                char[] a = new char[n];
                int x = bis.read();
                while (ignore(x)) {
                    x = bis.read();
                }
                int i = 0;
                while (!ignore(x)) {
                    a[i++] = (char) x;
                    x = bis.read();
                }
                return a;
            } catch (Exception e) {
                throw new RuntimeException(e.getMessage());
            }
        }

        private boolean ignore(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        String nextString(boolean line) {
            return new String(nextCharArray(line));
        }

        String nextString() {
            return nextString(false);
        }

        boolean nextBoolean() {
            return "true".equalsIgnoreCase(nextString());
        }

        double nextDouble() {
            return Double.parseDouble(nextString());
        }

        void println(Object obj) {
            print(obj);
            print("\n");
        }

        void println() {
            print('\n');
        }

        void print(Object obj) {
            pw.print(obj);
        }

        void printf(String format, Object... obj) {
            pw.printf(format, obj);
        }

        void close() {
            try {
                if (bis != null) bis.close();
                if (pw != null) {
                    pw.flush();
                    pw.close();
                }
                bis = null;
                pw = null;
            } catch (Exception ignore) {
            }
        }
    }
}

Submission Info

Judge Result