题解 | #[SDOI2009]HH的项链#

java代码

莫队 + 类排序 + 双指针 + 快读

板题

O（n*sqrt(n)）

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.io.PrintWriter; import java.io.StreamTokenizer; import java.util.Arrays; import java.util.Scanner;

public class query { static int n, m, a[]; static int cnt[], ans[], bein[], l = 1, r, now;

static class Node {
    int l, r, id;

    Node(int l, int r, int id) {
        this.l = l;
        this.r = r;
        this.id = id;
    }
}

static int ceil(double num) {
    return (int) Math.ceil(num);
}

static int[] createBein(int n) {
    int sqrtN = (int) Math.sqrt(n);
    int size = (sqrtN + 1) * sqrtN; // 保证足够的容量来存储划分的区块
    int[] bein = new int[size + 1]; // 多加1以防止n是完全平方数时边界问题
    for (int i = 1; i <= sqrtN; i++) {
        for (int j = (i - 1) * sqrtN + 1; j <= Math.min(i * sqrtN, n); j++) { // 需要确保j不超过n
            bein[j] = i;
        }
    }
    return bein;
}

static int compare(Node a, Node b) {
    return bein[a.l] == bein[b.l] ? a.r - b.r : bein[a.l] - bein[b.l];
}

static void add(int x) {
    if (cnt[a[x]] == 0)
        ++now;
    ++cnt[a[x]];
}

static void del(int x) {
    --cnt[a[x]];
    if (cnt[a[x]] == 0)
        --now;
}

static void print(int x) {
    if (x / 10 != 0)
        print(x / 10);
    System.out.print((char) ('0' + x % 10));
}

public static void main (String[] args) throws IOException{
    Scanner sc = new Scanner(System.in);
    StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
    in.nextToken();
    n = (int) in.nval;
    a = new int[n + 1];
    cnt = new int[1000010];
    ans = new int[m + 1];
    bein = createBein(n);

    for (int i = 1; i <= n; ++i) {
    	in.nextToken();
    	a[i] = (int) in.nval;
    }
        
    in.nextToken();
    m = (int) in.nval;
    Node[] q = new Node[m + 1];
    for (int i = 1; i <= m; ++i) {
    	in.nextToken();
        q[i] = new Node((int)in.nval, (int)in.nval, i);
    }
    Arrays.sort(q, 1, m + 1, (o1, o2) -> compare(o1, o2));

    for (int i = 1; i <= m; ++i) {
        while (l < q[i].l)
            del(l++);
        while (l > q[i].l)
            add(--l);
        while (r < q[i].r)
            add(++r);
        while (r > q[i].r)
            del(r--);
        ans[q[i].id] = now;
    }

    for (int i = 1; i <= m; ++i) {
       
       cout.println(ans[i]);
       
    }
    cout.flush();
}

}