Distinct Values Queries

import java.io.*;
import java.util.*;

public class RangeDistinctValuesQueries {

    static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

    static class SuperQuickReader {
        final int BUFFER_SIZE = 4096;
        Reader in;

        char[] buf = new char[BUFFER_SIZE];
        int bufL, bufR;

        public SuperQuickReader(InputStream ins) {
            in = new InputStreamReader(ins);
        }

        public char nextChar() {
            try {
                while (bufR >= 0) {
                    if (bufL < bufR) {
                        char x = buf[bufL++];
                        return x;
                    } else {
                        bufR = in.read(buf);
                        bufL = 0;
                    }
                }
            } catch (IOException e) {
                bufL = bufR = -1;
            }
            return 0;
        }

        public char nextNonSpaceChar() {
            char c;
            do {
                c = nextChar();
            } while (c == ' ' || c == '\n');
            return c;
        }

        public int nextInt() {
            int res = 0;
            char c;
            boolean neg = false;
            do {
                c = nextChar();
            } while (c == ' ' || c == '\n');
            if (c == '-') {
                neg = true;
                c = nextChar();
            }

            do {
                res = res * 10 + (c - '0');
                c = nextChar();
            } while (c != ' ' && c != '\n' && c != 0);
            if (neg) res = -res;
            return res;
        }

        public int[] nextInts(int n) {
            int[] res = new int[n];
            for (int i = 0; i < n; i++) res[i] = nextInt();
            return res;
        }
    }

    static class Node {
        long tag_add;
        long sum;

        public Node(long tag_add, long sum) {
            this.tag_add = tag_add;
            this.sum = sum;
        }
    }

    static final int MAXN = 200000 + 5;

    static Node seg[] = new Node[4 * MAXN];

    private static void update(int u, int l, int r, int qL, int qR, int val) {
        if (qL <= l && r <= qR) {
            seg[u].sum += val * (r - l + 1);
            seg[u].tag_add += val;
            return;
        }

        int mid = (l + r) / 2;
        int lc = 2 * u;
        int rc = 2 * u + 1;
        push(seg[u], seg[lc], seg[rc], l, r);

        if (qL <= mid) update(lc, l, mid, qL, qR, val);
        if (mid + 1 <= qR) update(rc, mid + 1, r, qL, qR, val);

        pull(seg[u], seg[lc], seg[rc]);
    }


    public static Node range_query(int u, int l, int r, int qL, int qR) {
        if (l > qR || r < qL) {
            return new Node(0, 0);
        }

        if (qL <= l && r <= qR)
            return seg[u];

        int lc = 2 * u;
        int rc = 2 * u + 1;
        int mid = (l + r) / 2;

        push(seg[u], seg[lc], seg[rc], l, r);

        Node left = range_query(lc, l, mid, qL, qR);
        Node right = range_query(rc, mid + 1, r, qL, qR);

        pull(seg[u], left, right);

        return seg[u];

    }

    private static void pull(Node u, Node l, Node r) {
        u.sum = l.sum + r.sum;
        u.tag_add = 0;
    }

    private static void push(Node u, Node L, Node R, int l, int r) {
        if (u.tag_add != 0) {
            int mid = (l + r) / 2;

            L.tag_add += u.tag_add;
            L.sum += u.tag_add * (mid - l + 1);

            R.tag_add += u.tag_add;
            R.sum += u.tag_add * (r - mid);

            u.tag_add = 0;
        }
    }


    public static void main(String[] args) {
        SuperQuickReader reader = new SuperQuickReader(System.in);

        int n = reader.nextInt();
        int m = reader.nextInt();

        int[] input = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            input[i] = reader.nextInt();
        }

        for (int i = 0; i < seg.length; i++) {
            seg[i] = new Node(0, 0);
        }

        // 離線 query
        Map<Integer, TreeSet<int[]>> queries = new TreeMap<>();

        for (int i = 0; i < m; i++) {
            int a = reader.nextInt();
            int b = reader.nextInt();
            queries.putIfAbsent(b, new TreeSet<>(
                    (x, y) -> y[1] == x[1] ? x[0] - y[0] : y[1] - x[1]
            ));
            queries.get(b).add(new int[]{i, a});
        }
        // 1. treeMap 是 sort 右邊界
        // 2. TreeSet 是 sort 左邊界, 越短的先
        // 3. ex: [ 3 1 4 1 5 9 2 5 3 5 8 9 7 9 3 2 ]
        //        [ 5 4 4 3 2 1]
        //        [ 6 5 5 4 3 2 1]
        //        [ 6 5 5 4 3 3 2 1]

        long printOrder[] = new long[m + 1];
        
        Map<Integer, Integer> val2Pos = new HashMap<>();

        for (int i = 1; i <= n; i++) {
            int right = i;
            
            // 先修改 array
            int p = 0;
            if (val2Pos.containsKey(input[i])) {
                p = val2Pos.get(input[i]);
            }
            update(1, 1, n, p + 1, i, 1); // 把 array [p + 1:i] 都加上 1
            val2Pos.put(input[i], i);
            
            // 回答右界在 right 的 query
            for (int[] query : queries.getODefault(right, new int[]{} ) {
                int index = query[0];
                int left = query[1];
                printOrder[index] = range_query(1, 1, n, left, left).sum; // (線段樹的 arr[left]);
            }
            
            
            
            
            
            
            /*
            for (int i = 0; i < seg.length; i++) {
                seg[i] = new Node(0, 0);
            }


            Map<Integer, Integer> val2Pos = new HashMap<>();

            boolean first = true;
            int prev = -1;
            for (int[] a : queries.get(b)) {
                if (first) { // 3. 先算第ㄧ次 [1 2 3 3 4 5 6 6 6 7]
                    for (int i = a[1]; i <= b; i++) {
                        if (!val2Pos.containsKey(input[i])) {
                            val2Pos.put(input[i], i);
                            // 第ㄧ次出現就加上 distinct value
                            update(1, 1, n, i, i, 1);
                        }
                    }
                    first = false;
                    prev = a[1];

                } else {
                    // 4. 再算 range + 1 -> [1 2 3 4 4 5 6 7 7 7 7]
                    for (int i = a[1]; i < prev; i++) {
                        if (val2Pos.containsKey(input[i])) {
                            // 更新到重複數字出現前面 1 個
                            update(1, 1, n, i, val2Pos.get(input[i]) - 1, 1);
                        } else {
                            // 如果都沒有出現重複數字全部都 + 1
                            update(1, 1, n, i, n, 1);
                            val2Pos.put(input[i], i);
                        }

                    }
                    prev = a[1];
                }
                printOrder[a[0]] = range_query(1, 1, n, a[1], b).sum;
            }
            */
        }

        for (long p : printOrder) {
            if (p != 0L)
                out.println(p);
        }

        out.flush();
    }


}