蒟蒻求卡常

import java.io.*;
import java.util.ArrayList;
import java.util.Random;
import java.util.StringTokenizer;

class Reader {
    BufferedReader br;
    StringTokenizer st;
    public Reader(InputStream is) {
        this.br = new BufferedReader(new InputStreamReader(is));
    }
    public String next() throws IOException {
        while (this.st == null || !this.st.hasMoreElements()) {
            try {
                this.st = new StringTokenizer(this.br.readLine());
            }
            catch (IOException e) {
                e.printStackTrace();
                throw e;
            }
        }
        return this.st.nextToken();
    }
    public int nextInt() throws IOException {
        return Integer.parseInt(this.next());
    }
}

class TreapTree {
    static private class Node {
        int val, weight, size;
        boolean flag;
        Node left, right;
        public Node(int val, int weight, int size) {
            this.val = val;
            this.weight = weight;
            this.size = size;
            this.flag = false;
            this.left = null;
            this.right = null;
        }
    }
    static private class PairOfNodes {
        Node first, second;
        public PairOfNodes(Node first, Node second) {
            this.first = first;
            this.second = second;
        }
    }
    private Node root;
    public TreapTree(int n) {
        this.root = null;
        Random random = new Random();
        for (int i = 1; i <= n; ++i) {
            this.root = merge(this.root, new Node(i, random.nextInt(), 1));
        }
    }
    static private void update(Node node) {
        node.size = 1;
        if (node.left != null) {
            node.size += node.left.size;
        }
        if (node.right != null) {
            node.size += node.right.size;
        }
    }
    static private void push_down(Node node) {
        assert (node != null);
        if (node.flag) {
            node.flag = false;
            if (node.left != null) {
                node.left.flag = !node.left.flag;
            }
            if (node.right != null) {
                node.right.flag = !node.right.flag;
            }
            Node tmp = node.left;
            node.left = node.right;
            node.right = tmp;
        }
    }
    private static PairOfNodes split(Node node, int val) {
        if (node == null) {
            return new PairOfNodes(null, null);
        }
        Node left, right;
        push_down(node);
        if (val <= (node.left == null ? 0 : node.left.size)) {
            right = node;
            PairOfNodes tmp = split(node.left, val);
            left = tmp.first;
            node.left = tmp.second;
        }
        else {
            left = node;
            PairOfNodes tmp = split(node.right, val - (node.left == null ? 0 : node.left.size) - 1);
            node.right = tmp.first;
            right = tmp.second;
        }
        update(node);
        return new PairOfNodes(left, right);
    }
    private static Node merge(Node left, Node right) {
        if (left == null) {
            return right;
        }
        if (right == null) {
            return left;
        }
        Node tmp;
        if (left.weight < right.weight) {
            push_down(left);
            left.right = merge(left.right, right);
            tmp = left;
        }
        else {
            push_down(right);
            right.left = merge(left, right.left);
            tmp = right;
        }
        update(tmp);
        return tmp;
    }
    public void reverse(int l, int r) {
        PairOfNodes tmp1 = split(this.root, l - 1);
        PairOfNodes tmp2 = split(tmp1.second, r - l + 1);
        tmp2.first.flag = !tmp2.first.flag;
        this.root=merge(tmp1.first, merge(tmp2.first, tmp2.second));
    }
    public ArrayList<Integer> get_all() {
        ArrayList<Integer> res = new ArrayList<Integer>();
        traversal(this.root, res);
        return res;
    }
    private static void traversal(Node node, ArrayList<Integer> arr) {
        push_down(node);
        if (node.left != null) {
            traversal(node.left, arr);
        }
        arr.add(node.val);
        if (node.right != null) {
            traversal(node.right, arr);
        }
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        int n, m;
        BufferedWriter cout = new BufferedWriter(new OutputStreamWriter(System.out));
        Reader cin = new Reader(System.in);
        TreapTree tree;
        n = cin.nextInt();
        m = cin.nextInt();
        tree = new TreapTree(n);
        for (int j = 0; j < m; ++j) {
            int l, r;
            l = cin.nextInt();
            r = cin.nextInt();
            tree.reverse(l, r);
        }
        ArrayList<Integer> ans = tree.get_all();
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                cout.write(" ");
            }
            cout.write("" + ans.get(i));
        }
        cout.newLine();
        cout.close();
    }
}

洛谷过了，最大点大概 950\rm ms

但是 loj 上 #8、#9、#10 三个点 TLE 了（传送门），下载了 #8 数据，本地运行只需要 0.6\rm s（答案都是没问题的）

别问我为什么用 Java，问就是我也不知道